作者:zhanhailiang 日期:2012-12-17
1.首先需要引入合并两个已排序的表的算法 假设有一个数组A[1…m],p,q,r为它的三个索引,并有1?p?q<r?m。两子数组A[p…q],A[q+1…r]各按升序排列,我们需要重新安排A中的元素的位置,使得子数组A[p…r]也按升序排列。这就是合并A[p…q]和A[q+1…r]的过程。合并算法是如下工作,使用两个指针s和t,初始化时分别指向A[p]和A[q+1],再用空数组B[p…r]做暂存器。每一次比较元素A[s]和A[t],将小的元素添加到B,若相同则把A[s]添加进去。然后更新指针,若A[s]?A[t],则s++;反之则t++,当条件s=q+1或t=r+1成立时结束。在第一种情况下将数组A[t…r]中剩余的元素添加到B,而另一种情况则将数组A[s…q]中剩余的元素添加到B。最后把数组B[p…r]复制加A[p…r]。如下给出伪代码:
/***************************************************************************** 算法:merge 输入:数组A[1...m],p,q,r为它的三个索引,并有1<=p<=q<r<=m。两子数组A[p...q],A[q+1...r]各按升序排列 输出:合并两个子数组A[p...q],A[q+1...r]的新数组A[1...m] ******************************************************************************/ s = p; t = q + 1; k = p; while(s <= q && t <= r) { if(A[s] <= A[t]) { B[k] = A[s]; s++; } else { B[k] = A[t]; t++; } k++; } if(s === q + 1) { B[k...r] = A[t...r]; } else { B[k...r] = A[s...q]; } A[p...r] = B[p...r];
2.合并排序
/***************************************************************************** 算法:mergesort 输入:A[1...n] 输出:按非降序排列的数组A[1...n] mergesort(A, 1, n); ******************************************************************************/ 过程 mergesort(A, low, high) if(low < high) { mid = parseInt((low + high) / 2); mergesort(A, low, mid); mergesort(A, mid + 1, high); merge(A, low, mid, high); }
按上述合并排序的伪代码给出合并排序的 JS实现版本:
function merge(arr, p, q, r) { var crr = []; var a = p, b = q + 1, k = p; while(a <= q && b <= r) { if(arr[a] <= arr[b]) { crr.push(arr[a]); a ++; } else { crr.push(arr[b]); b ++; } k ++; } if(a === q + 1) { while(b <= r) { crr.push(arr[b]); b ++; } } else { while(a <= q) { crr.push(arr[a]); a ++; } } var i = 0, cl = crr.length; while(i < cl) { arr[p++] = crr[i++]; } return arr; } function mergesort(arr, low, high) { if(low === high) { return arr; } else if(high - low === 1) { if(arr[low] > arr[high]) { var temp = arr[low]; arr[low] = arr[high]; arr[high] = temp; } return arr; } else { var mid = parseInt((low+high)/2); arr = mergesort(arr, low, mid); arr = mergesort(arr, mid+1, high); return merge(arr, low, mid, high); } } // 示例 var test = [88, 32, 22, 32, 87, 88]; console.log(mergesort(test, 0, test.length - 1));