一天一算法 - 归并排序

归并排序最吸引人的性质就是能够保证将任意长度为 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

一天一算法 - 归并排序

推荐阅读更多精彩内容