归并排序最吸引人的性质就是能够保证将任意长度为 N 的数组排序所需时间和 NLogN 成正比，它的主要缺点是所需的额外空间和 N 成正比。
其实归并排序的思想非常简单，直接了当的说就是将两个不同的有序数组归并到第三个数组当中去。那么怎么才能够从一个无序的数组获取到两个有序的数组呢？这就需要借助递归的思想，我们可以递归切割数组，直到子数组中只有一个元素，这个时候我们自然而然的就得到了有序的数组。比如我们要排序数组 [5, 4, 3, 2, 1, 0], 归并排序会按照下图切割数组。
demo.png
当切割的只剩下一个元素时，返回并与自己同级的兄弟节点两两整合，最后返回的就是一个有序的大数组，可以明显看出，这是非常典型的分治思想。
首先，我们来看看将两个有序数组整合成一个有序大数组的代码。
var merge = function(ltr, rtr) {
var ltrLength = ltr.length,
rtrLength = rtr.length,
li = 0,
rj = 0,
result = [];
while (li < ltrLength && rj < rtrLength) {
if (ltr[li] < rtr[rj]) {
result.push(ltr[li++]);
} else {
result.push(rtr[rj++]);
}
}
while (li < ltrLength) {
result.push(ltr[li++]);
}
while (rj < rtrLength) {
result.push(rtr[rj++]);
}
return result;
};
代码的逻辑主要分为三步：
-
当左数组和右数组都还有元素的时候，比较两数组元素的大小，将其中较小的元素推进辅助数组(为了合并两数组而创建的数组)。
-
当左数组中尚有元素剩余而右数组已经没有元素了，这个时候将左数组中的元素依次推进辅助数组。
-
当右数组中尚有元素剩余而左数组已经没有元素了，这个时候将右数组中的元素依次推进辅助数组。
现在已经有了合并的方法，那么还需要一个能够将数组切割成小数组的方法，下面来看看实现代码。
var mergeSortRec = function(arr) {
var length = arr.length;
if (length === 1) {
return arr;
}
var mid = Math.floor(length / 2),
ltr = arr.slice(0, mid),
rtr = arr.slice(mid, length);
return merge(mergeSortRec(ltr), mergeSortRec(rtr));
};
这个函数使用了递归切割的方法，它可以保证将一个大数组一步步切割成只剩一个元素的数组，并且返回提供给 merge() 函数令其归并。
这个时候，归并排序就已经完成了，现在可以去测试以下归并排序排序百万数量级的数据所需时间，我用以下代码进行了测试。
console.time();
array.mergeSort();
console.timeEnd();
注意，上面只是核心代码，在这之前我已经在数组中存放了一百万个元素，并且已经随机打乱。我们来看看浏览器返回给我的结果。
sort.png
我尝试了好几次，大概都在 550ms 左右。按理来说，这已经很快了，但是仍然存在一些优化可以让归并排序更快。我在上一篇文章介绍插入排序算法的时候曾经说过，当插入排序面临基本有序的数组时可能比任何排序算法都要快。根据这一思想，我们可以在归并排序中使上一些手段，比如当数组的长度比较小时，改用插入排序进行排序。
修改后的代码像下面这样。
var mergeSortRec = function(arr) {
var length = arr.length;
if (length === 1) {
return arr;
}
if(length <= 10) {
return insertionSort(arr);
}
var mid = Math.floor(length / 2),
ltr = arr.slice(0, mid),
rtr = arr.slice(mid, length);
return merge(mergeSortRec(ltr), mergeSortRec(rtr));
};
现在再来看看排序同样的数组需要多长时间。
sort-2.png
我运行了很多次，其值一直在 270ms 左右浮动。非常令人惊讶，只是这么一个小小的改动，归并排序的性能竟获得如此大的提升！
不过，这个程序还是有一点不完美，比如对于一个已经有序的数组，它排序话费的时间和排序无序的数组是差不多的，所以我们还是有必要在排序前对数组进行检测，如果其确实是个无序数组，我们再调用算法进行排序也不迟。
var isSorted = function() {
var length = array.length;
for(var i = 1; i < length; i++) {
if(array[i] < array[i - 1]) {
return false;
}
return true;
}
}
这样一来，对于一个有序的大数组，我们只需要花 1-2 ms 的时间就可以确定是否需要调用排序算法，相比于不检测就直接调用归并排序省了大把时间。
我在写 isSorted() 函数的时候突然冒出一个想法，我能不能在检测是否排序的时候记录一个数组中到底有多少逆序呢？这样我就可以择机使用插入排序替代希尔排序，这对于基本有序数组又是一个性能优化。最终我没有记录有多少个逆序，但我声明了一个变量，用于记录有多少个元素不在其最终位置上，当其值小于 100 时，我选择用插入排序替代了归并排序，像下面这样。
this.isSorted = function() {
var length = array.length,
reverse = 0;
for (var i = 1; i < length; i++) {
if (array[i] < array[i - 1]) {
reverse++;
}
}
if (reverse === 0) {
return true;
} else {
if (reverse < 100) {
insertionSort(array);
return true;
}
return false;
}
}
我测试了让前一百万个数据中的前几十个元素随机打乱，然后再把最后的几十个元素随机打乱，其性能仍然优于归并排序！
如果你想查看源码，可以打开 我的 Github
网友评论