//堆中的节点下移 //(约定有效元素从下标1开始) //i为要调整的元素索引 //n为待处理的有效元素下标范围上限值 //时间复杂度O(logN) function siftDown(H, i, n) { if (n >= H.length) { n = H.length; } if (2 * i > n) { //叶子节点，就不用再向下移了 return; } for (var j = 2 * i; j < n; j = 2 * j) { //将j定位到 二个子节点中较大的那个上(很巧妙的做法) if (H[j + 1] > H[j]) { j++; } var k = Math.floor(j / 2); if (H[k] < H[j]) { var t = H[k]; H[k] = H[j]; H[j] = t; } else { return; } } } //对数组的前n个元素进行创建堆的操作 function makeHeap(A, n) { if (n >= A.length) { n = A.length; } for (var i = Math.floor(n / 2); i >= 1; i--) { siftDown(A, i, n); } } //堆排序(非降序排列) //时间复杂度O(nlogN) function heapSort(H) { //先建堆 makeHeap(H, H.length); for (var j = H.length - 1; j >= 2; j--) { //首元素必然是最大的 //将最大元素与最后一个元素互换， //即将最大元素沉底，下一轮不再考虑 var x = H[1]; H[1] = H[j]; H[j] = x; //互换后，剩下的元素不再满足堆定义， //把新的首元素下调(以便继续维持堆的"形状") //调整完后，剩下元素中的最大值必须又浮到了第一位 //进入下一轮循环 siftDown(H, 1, j - 1); } return H; }
关于建堆，如果明白其中的原理后，也可以逆向思路，反过来做
function makeHeap2(A, n) { if (n >= A.length) { n = A.length; } for (var i = Math.floor(n / 2); i <= n; i++) { siftUp(A, i); } }
不相交集合查找、合并
//定义节点Node类 var Node = function (v, p) { this.value = v; //节点的值 this.parent = p; //节点的父节点 this.rank = 0; //节点的秩(默认为0) } //查找包含节点x的树根节点 var find = function (x) { var y = x; while (y.parent != null) { y = y.parent; } var root = y; y = x; //沿x到根进行“路径压缩” while (y.parent != null) { //先把父节点保存起来，否则下一行调整后，就弄丢了 var w = y.parent; //将目标节点挂到根下 y.parent = root; //再将工作指针，还原到 目标节点原来的父节点上， //继续向上逐层压缩 y = w } return root; } //合并节点x，y对应的两个树 //时间复杂度O(m) - m为待合并的子集合数量 var union = function (x, y) { //先找到x所属集合的根 var u = find(x); //再找到y所属集合的根 var v = find(y); //把rank小的集合挂到rank大的集合上 if (u.rank <= v.rank) { u.parent = v; if (u.rank == v.rank) { //二个集合的rank不分伯仲时 //给"胜"出方一点奖励，rank+1 v.rank += 1; } } else { v.parent = u; } }
归纳法：
先来看二个排序的递归实现
//选择排序的递归实现 //调用示例: selectionSort([3,2,1],0) function selectionSortRec(A, i) { var n = A.length - 1; if (i < n) { var k = i; for (var j = i + 1; j <= n; j++) { if (A[j] < A[k]) { k = j } } if (k != i) { var t = A[k]; A[k] = A[i]; A[i] = t; } selectionSortRec(A, i + 1); } } //插入排序递归实现 //调用示例:insertSortRec([4,3,2,1],3); function insertSortRec(A, i) { if (i > 0) { var x = A[i]; insertSortRec(A, i - 1); var j = i - 1; while (j >= 0 && A[j] > x) { A[j + 1] = A[j]; j--; } A[j + 1] = x; } }
递归的程序通常易于理解，代码也容易实现，再来看二个小例子：
从数组中，找出最大值
//在数组中找最大值(递归实现) function findMax(A, i) { if (i == 0) { return A[0]; } var y = findMax(A, i - 1); var x = A[i - 1]; return y > x ? y : x; } var A = [1,2,3,4,5,6,7,8,9]; var test = findMax(A,A.length); alert(test);//返回9
有一个已经升序排序好的数组，检查数组中是否存在二个数，它们的和正好为x ？
//5.33 递归实现 //A为[1..n]已经排好序的数组 //x为要测试的和 //如果存在二个数的和为x，则返回true，否则返回false function sumX(A, i, j, x) { if (i >= j) { return false; } if (A[i] + A[j] == x) { return true; } else if (A[i] + A[j] < x) { //i后移 return sumX(A, i + 1, j, x); } else { //j前移 return sumX(A, i, j - 1, x); } } var A = [1, 2, 3, 4, 5, 6, 7, 8]; var test1 = sumX(A,0,A.length-1,9); alert(test1); //返回true
递归程序虽然思路清晰，但通常效率不高，一般来讲，递归实现，都可以改写成非递归实现，上面的代码也可以写成：
//5.33 非递归实现 function sumX2(A, x) { var i = 0, j = A.length - 1; while (i < j) { if (A[i] + A[j] == x) { return true; } else if (A[i] + A[j] < x) { //i后移 i++; } else { //j前移 j--; } } return false; } var A = [1, 2, 3, 4, 5, 6, 7, 8]; var test2 = sumX2(A,9); alert(test2);//返回true