Javascript和归并排序
这里以递归为例，参考自慕课网刘波波老师的C++版本实现
普通归并(自上而下)
普通的归并排序，是把数据自上而下地分成若干个小块，然后在小块里进行合并排序的操作，最后不断重复这个过程，得到最终的结果。
代码就是这样的：
var mergeSort = function (arr) {
__mergeSort(arr, 0, arr.length - 1);
return arr;
}
function __mergeSort(arr, start, end) {
//健壮性
if (start >= end) {
return;
}
var mid = ~~((start + end) / 2);
//递归
__mergeSort(arr, start, mid);
__mergeSort(arr, mid + 1, end);
//处理
__merge(arr, start, mid, end);
}
function __merge(arr, start, mid, end) {
//数组副本
var aux = arr.slice(start, end + 1);
var i = start;
var j = mid + 1;
for (var k = start; k <= end; k++) {
//这里可以合并代码
// 左边的归并完了，右边的没有归并完
if (i > mid) {
arr[k] = aux[j - start];
j++;
}
//右边的归并完了，左边的没有归并完
else if (j > end) {
arr[k] = aux[i - start];
i++;
}
// 左边小
else if (aux[i - start] < aux[j - start]) {
arr[k] = aux[i - start];
i++;
}
// 右边小
else {
arr[k] = aux[j - start];
j++;
}
}
return arr;
}
优化归并(自下而上)
我们经过观察就会发现，其实可以省略分块的步骤，直接最开始的时候把它们看做一个个小的数据块，从而自下而上的一步步合并得到最终的结果。
代码就变成了这样：
var mergeSortBU = function (arr) {
var len = arr.length;
for (var sz = 1; sz <= len; sz += sz) {
for (var i = 0; i + sz < len; i += sz + sz) {
__merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, len - 1));
}
}
return arr;
}
function __merge(arr, start, mid, end) {
//数组副本
var aux = arr.slice(start, end + 1);
var i = start;
var j = mid + 1;
for (var k = start; k <= end; k++) {
// 左边的归并完了，右边的没有归并完或者左边大
if (i > mid || (aux[i - start] >= aux[j - start])) {
arr[k] = aux[j - start];
j++;
}
else {
arr[k] = aux[i - start];
i++;
}
}
return arr;
}
同时排序一百万个数据时的性能对比：
归并排序耗时.png
可以看出，第二个方案总体上来说是比第一个方案好的。
JS特色归并
这种写法当然是使用了大量JS原生API的，在这里我给出我的写法和阮一峰先生的写法：
//我的写法
function mergeSort(arr) {
var len = arr.length;
for (var sz = 1; sz <= len; sz += sz) {
for (var i = 0; i + sz < len; i += sz + sz) {
var left = arr.slice(i, i + sz);
var right = arr.slice(i + sz, Math.min(i + sz + sz, len));
arr.splice(i, Math.min(sz + sz,len ), ...merge(left, right));
}
}
return arr;
}
// 有性能损失
function merge(left, right) {
var tmp = [];
while (left.length && right.length) {
//左小出右
if (left[0] < right[0]) {
tmp.push(left.shift());
}
//右小出右
else {
tmp.push(right.shift());
}
}
return tmp.concat(left, right);
}
//阮一峰老师的实现
function merge(left, right){
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length){
if (left[il] < right[ir]){
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
function mergeSort(myArray){
if (myArray.length < 2) {
return myArray;
}
var middle = Math.floor(myArray.length / 2),
left = myArray.slice(0, middle),
right = myArray.slice(middle),
params = merge(mergeSort(left), mergeSort(right));
// 在返回的数组头部，添加两个元素，第一个是0，第二个是返回的数组长度
params.unshift(0, myArray.length);
// splice用来替换数组元素，它接受多个参数，
// 第一个是开始替换的位置，第二个是需要替换的个数，后面就是所有新加入的元素。
// 因为splice不接受数组作为参数，所以采用apply的写法。
// 这一句的意思就是原来的myArray数组替换成排序后的myArray
myArray.splice.apply(myArray, params);
// 返回排序后的数组
return myArray;
}
这两个算法，性能上都差之前实现的很多，并且数据量到一百万的时候还是导致溢出，有兴趣的朋友可以自己去试试。
总结
归并算法和排序算法一样是利用了分治法来解决问题：即先解决若干个小问题就等于解决了一个大问题。
