假定我们有一个mxn的矩阵,它的每一行以及每一列都是排好序的。我们可以称这个矩阵为Young tableaus(杨氏矩阵)。
可以利用一个n*n的Young(杨氏)矩阵在O(n^3)时间内将n^2个数进行排序。
实现代码:
var a = [9, 6, 3, 2, 4, 8, 5, 14, 12]; console.log(a.join("\t")); youngSort(a); console.log(a.join("\t")); /*var m = initYoung(4, 4); for(var i = 0; i < a.length; i ++){ youngInsert(m, a[i]); } console.log(a); console.log(m);*/ function youngSort(a){ var len = a.length; var n = Math.ceil(Math.sqrt(len)); var m = initYoung(n, n); for(var i = 0; i < a.length; i ++){ youngInsert(m, a[i]); } for(var i = 0; i < a.length; i++){ a[i] = youngExtractMin(m); } } function youngExtractMin(m){ if(m[0][0] == Infinity){ throw(new Error("young underflow")); } var min = m[0][0]; youngDelete(m, 0, 0); return min; } function youngFind(m, key){ var i = 0; var j = m.size.y - 1; while(i < a.size.x && j >= 0){ if(a[i][j] > key){ j--; } else if(a[i][j] < key){ i++; } else { return {x: i, y: j}; } } return null; } function youngIsFull(m){ return m[m.size.x - 1][m.size.y - 1] < Infinity; } function youngInsert(m, key){ if(youngIsFull(m)){ throw(new Error("young matrix is full")); } var i = m.size.x - 1; var j = m.size.y - 1; decreaseKey(m, i, j, key); } function decreaseKey(m, i, j, key){ if(m[i][j] < key){ throw(new Error("Invalid key")); } m[i][j] = key; var largestI = i; var largestJ = j; if(i > 0 && m[i - 1][j] > m[i][j]){ largestI = i - 1; largestJ = j; } if(j > 0 && m[i][j - 1] > m[largestI][largestJ]){ largestI = i; largestJ = j - 1; } if(largestI != i || largestJ != j){ exchange(m, i, j, largestI, largestJ); decreaseKey(m, largestI, largestJ, key); } } function youngDelete(m, i, j){ m[i][j] = Infinity; youngify(m, i, j); } function youngify(m, i, j){ var minI = i; var minJ = j; if(i < m.size.x - 1 && m[i + 1][j] < m[i][j]){ minI = i + 1; minJ = j; } if(j < m.size.y - 1 && m[i][j + 1] < m[minI][minJ]){ minI = i; minJ = j + 1; } if(i != minI || j != minJ){ exchange(m,i,j,minI,minJ); youngify(m, minI,minJ); } } function minYoung(m){ return m[0][0]; } function initYoung(m, n){ var arr = []; for(var i = 0; i < m; i++){ arr[i] = []; for(var j = 0; j < n; j++){ arr[i][j] = Infinity; } } arr.size = {x : m, y: n}; return arr; } function exchange(m,i0,j0,i1,j1){ var temp = m[i0][j0]; m[i0][j0] = m[i1][j1]; m[i1][j1] = temp; }
发表评论:
◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。