//打印输出(调试用) function println(msg) { document.write(msg + "<br/>"); } //数组中i,j位置的元素交换(辅助函数) function swap(A, i, j) { var t = A[i]; A[i] = A[j]; A[j] = t; } //寻找数组A中的最大、最小值(分治法实现) function findMinMaxDiv(A, low, high) { //最小规模子问题的解 if (high - low == 1) { if (A[low] < A[high]) { return [A[low], A[high]]; } else { return [A[high], A[low]]; } } var mid = Math.floor((low + high) / 2); //在前一半元素中寻找子问题的解 var r1 = findMinMaxDiv(A, low, mid); //在后一半元素中寻找子问题的解 var r2 = findMinMaxDiv(A, mid + 1, high); //把二部分的解合并 var x = r1[0] > r2[0] ? r2[0] : r1[0]; var y = r1[1] > r2[1] ? r1[1] : r2[1]; return [x, y]; } var r = findMinMaxDiv([1, 2, 3, 4, 5, 6, 7, 8], 0, 7); println(r); //1,8 //二分搜索(分治法实现) //输入：A为已按非降序排列的数组 //x 为要搜索的值 //low,high搜索的起、止索引范围 //返回：如果找到，返回下标，否则返回-1 function binarySearchDiv(A, x, low, high) { if (low > high) { return -1; } var mid = Math.floor((low + high) / 2); if (x == A[mid]) { return mid; } else if (x < A[mid]) { return binarySearchDiv(A, x, low, mid - 1); } else { return binarySearchDiv(A, x, mid + 1, high); } } var f = binarySearchDiv([1, 2, 3, 4, 5, 6, 7], 4, 0, 6); println(f); //3 //将数组A，以low位置的元素为界，划分为前后二半 //n为待处理的索引范围上限 function split(A, low, n) { if (n >= A.length - 1) { n = A.length - 1; } var i = low; var x = A[low]; //二个指针一前一后“跟随”， //最前面的指针发现有元素比分界元素小时，换到前半部 //后面的指针再紧跟上，“夫唱妇随”一路到头 for (var j = low + 1; j <= n; j++) { if (A[j] <= x) { i++; if (i != j) { swap(A, i, j); } } } //经过上面的折腾后，除low元素外，其它的元素均以就位 //最后需要把low与最后一个比low位置小的元素交换， //以便把low放在分水岭位置上 swap(A, low, i); return [A, i]; } var A = [5, 1, 2, 6, 3]; var b = split(A, 0, A.length - 1); println(b[0]); //3,1,2,5,6 //快速排序 function quickSort(A, low, high) { var w = high; if (low < high) { var t = split(A, low, w); //分治思路，先分成二半 w = t[1]; //在前一半求解 quickSort(A, low, w - 1); //在后一半求解 quickSort(A, w + 1, high); } } var A = [5, 6, 4, 7, 3]; quickSort(A, 0, A.length - 1); println(A); //3,4,5,6,7
split算法的思想应用：
设A[1..n]是一个整数集，给出一算法重排数组A中元素，使得所有的负整数放到所有非负整数的左边，你的算法的运行时间应当为Θ(n)
function sort1(A) { var i = 0, j = A.length - 1; while (i < j) { if (A[i] >= 0 && A[j] >= 0) { j--; } else if (A[i] < 0 && A[j] < 0) { i++; } else if (A[i] > 0 && A[j] < 0) { swap(A, i, j); i++; j--; } else { i++; j--; } } } function sort2(A) { if (A.length <= 1) { return; } var i = 0; for (var j = i + 1; j < A.length; j++) { if (A[j] < 0 && A[i] >= 0) { swap(A, i, j); i++; } } } var a = [1, -2, 3, -4, 5, -6, 0]; sort1(a); println(a);//-6,-2,-4,3,5,1,0 var b = [1, -2, 3, -4, 5, -6, 0]; sort2(b); println(b);//-2,-4,-6,1,5,3,0