排序 (三): 归并排序

[S-T-D]

• 简介
• 实现
  • 实现归并
  • 完成排序
• 复杂度
  • 时间复杂度
  • 空间复杂度
• 遍历实现

 

简介

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。——《算法（第四版）》

举例：

截图来自于《算法（第四版）》，想要将输入数组排序，可以将数组分成左右两部分分别进行排序，然后将左右两部分合并在一起。

那么如何对左右部分的数组进行排序呢？

同样也是对左右部分的数组进行相同的操作，对半划分，分别排序再合并，直到数组不能再划分的时候，也就是数组长度为 1 的时候。所以归并排序同时应用到了递归和分治的四思想。

稳定性：稳定。

 

实现

实现归并

我们将实现分成两部分，首先来实现归并部分。

/**
 * @param {number[]} arr 输入数组，mid 将数组分成前后两部分，并且两部分都是排好序的
 * @param {number} low 输入数组的起始索引
 * @param {number} mid 输入数组的中间索引
 * @param {number} high 输入数组的末尾索引
 */
function merge(arr, low, mid, high) {
    // 1. 声明一个辅助数组
    const aux = [];
    // 2. 将输入数组复制 到 辅助数组中
    for (let i = low; i <= high; i++) {
        aux[i] = arr[i];
    }
    // 3. j 指向前半部分数组的起始索引，mid 是其末尾的索引
    let j = low;
    // 4. k 指向后半部分数组的起始索引，high 是其末尾的索引
    let k = mid + 1;
    // 5. 遍历，原地更新输入数组
    for (let i = low; i <= high; i++) {
        if (j > mid) {                  // 6. j 大于 mid 的时候，说明前半部分数组已经遍历完了 
            arr[i] = aux[k++];          // 那么，直接取辅助数组的 后 半部分数组更新 arr
        } else if (k > high) {          // 7. k 大于 high 的时候，说明后半部分数组已经遍历完了 
            arr[i] = aux[j++];          // 那么，直接取辅助数组的 前 半部分数组更新 arr
        } else if (aux[j] < aux[k]) {   // 8. 根据大小对比，更新 arr
            arr[i] = aux[j++];
        } else {
            arr[i] = aux[k++];
        }
    }
}

这里实现的是输入数组的原地归并，后面会说到为什么这样实现。同时，对输入数组的要求是前后两部分是有序的。

所以，有了这个归并函数，我们只需要结合递归不断将输入数组对半划分，直到划分到子数组只剩两个元素时对子元素调用 merge 方法，两个元素的数组满足前后两部分有序的要求，调用之后这个子数组就是有序的了。

总体思路就是对输入数组不断向下拆分成子数组，对子数组进行归并操作使其有序，然后递归一层一层退出的时候，将子数组不断归并成原始长度的数组。

完成排序

下面看看完整的代码实现。

function mergeSort(arr) {
    // 一次性分配辅助数组，防止多次调用 merge 函数带来的创建辅助函数的开销
    const aux = new Array(arr.length);

    dfs(arr, 0, arr.length - 1, aux);

    /**
    * @param {number[]} arr 输入数组，
    * @param {number} low 输入数组的起始索引
    * @param {number} high 输入数组的末尾索引
    * @param {number[]} aux 辅助数组
    */
    function dfs(arr, low, high, aux) {
        if (low >= high) return;
        // 二分数组
        const mid = low + Math.floor((high - low) / 2);
        dfs(arr, low, mid, aux);
        dfs(arr, mid + 1, high, aux);
        merge(arr, low, mid, high, aux);
    }

    /**
    * @param {number[]} arr 输入数组，mid 将数组分成前后两部分，并且两部分都是排好序的
    * @param {number} low 输入数组的起始索引
    * @param {number} mid 输入数组的中间索引
    * @param {number} high 输入数组的末尾索引
    * @param {number[]} aux 辅助数组
    * @return void 原地修改输入数组，防止多次调用 merge 带来的创建新数组的开销
    */
    function merge(arr, low, mid, high, aux) {
        // 1. 将输入数组复制 到 辅助数组中
        for (let i = low; i <= high; i++) {
            aux[i] = arr[i];
        }
        // 2. j 指向前半部分数组的起始索引，mid 是其末尾的索引
        let j = low;
        // 3. k 指向后半部分数组的起始索引，high 是其末尾的索引
        let k = mid + 1;
        // 4. 遍历，原地更新输入数组
        for (let i = low; i <= high; i++) {
            if (j > mid) {                  // 5. j 大于 mid 的时候，说明前半部分数组已经遍历完了 
                arr[i] = aux[k++];          // 那么，直接取辅助数组的 后 半部分数组更新 arr
            } else if (k > high) {          // 6. k 大于 high 的时候，说明后半部分数组已经遍历完了 
                arr[i] = aux[j++];          // 那么，直接取辅助数组的 前 半部分数组更新 arr
            } else if (aux[j] < aux[k]) {   // 7. 根据大小对比，更新 arr
                arr[i] = aux[j++];
            } else {
                arr[i] = aux[k++];
            }
        }
    }
}

 

复杂度

时间复杂度

从代码实现可以看出，时间消耗主要在对 merge 函数的调用，所以我们只需要知道一共调用了多少次 merge 函数，以及 merge 函数内的时间复杂度即可知道总的时间复杂度。

这里还是截取《算法（第四版）》里的一张图来说明。

这张图表示的是对一个长度为 16 的数组进行归并排序，这里假定数组的长度为 N，每个节点表示一次对 merge 函数的调用。所以，只要求出有多少个 merge 节点，以及每个 merge 节点的时间复杂度就可以了。

假定这棵树有 n 层，根据二分的时间复杂度可以知道 n = logN。

第 0 层有 1 个节点
第 1 层有 2 个节点
第 2 层有 4 个节点
第 k 层有 2^k 个节点。

第 0 层每个节点的数组长度是 16
第 1 层每个节点的数组长度是 8
第 2 层每个节点的数组长度是 4
第 3 层每个节点的数组长度是 2
每个节点的数组长度是 2^n-k，k 指层数，从 0 开始。

所以总的时间复杂度为 层数 * 每层节点数 * 每个节点的数组长度 = n * 2^k * 2^n-k = n * 2^n = logN * 2 ^ logN = NlogN。

归并排序的时间复杂度为线性对数 NlogN，只比线性时间复杂度稍差一点，要远远优于平方级别的插入排序和选择排序。

可以用归并排序处理数百万甚至更大规模的数组，这是插入排序或者选择排序做不到的。——《算法（第四版）》

空间复杂度

O(N)，N 指数组长度，空间消耗主要在于辅助数组，这也是归并排序的主要缺点。

 

遍历实现

上面的代码实现可以描述为自顶向下的实现，也就是从一个整体出发，不断将问题拆分为小问题，通过不断解决小问题来完成大问题。

还有一种方式就是自底向上的实现，也就是直接从小问题着手，从局部到整体逐步解决。

function mergeSort(arr) {
    const aux = Array.from(arr);
    const len = arr.length;

    for (let size = 1; size < len; size += size) {
        for (let i = 0; i < len - size; i += size * 2) {
            merge(arr, i, i + size - 1, Math.min(i + size * 2 - 1, len - 1), aux);
        }
    }
   
    function merge(arr, low, mid, high, aux) {
        for (let i = low; i <= high; i++) {
            aux[i] = arr[i];
        }
        let j = low;
        let k = mid + 1;
        for (let i = low; i <= high; i++) {
            if (j > mid) {                  
                arr[i] = aux[k++];          
            } else if (k > high) {          
                arr[i] = aux[j++];          
            } else if (aux[j] < aux[k]) {   
                arr[i] = aux[j++];
            } else {
                arr[i] = aux[k++];
            }
        }
    }
}