JavaScript算法之归并排序算法（详解）-木庄网络博客

本文摘自PHP中文网，作者青灯夜游，侵删。

在本文中，我们学习 Merge Sort 背后的逻辑，并用 JavaScript 实现。最后，在空间和时间复杂度方面将归并排序与其他算法进行比较。

归并排序背后的逻辑

归并排序使用分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题，直到它们变得足够简单以至可以直接解决为止。

以下是归并排序的步骤：

1、将给定的列表分为两半（如果列表中的元素数为奇数，则使其大致相等）。

2、以相同的方式继续划分子数组，直到只剩下单个元素数组。

3、从单个元素数组开始，合并子数组，以便对每个合并的子数组进行排序。

4、重复第 3 步单元，直到最后得到一个排好序的数组。

以数组 [4, 8, 7, 2, 11, 1, 3] 为例，让我们看一下归并排序是如何工作的：

用 JavaScript 实现归并排序

首先实现一个将两个已排序子数组合并为一个已排序数组的函数 merge() 。要注意着两个子数组是已经被排好序的，这一点非常重要， merge() 函数只用于其进行合并。【推荐教程：《JavaScript视频教程》】

可以通过遍历这两个子数组来实现：

function merge(left, right) {
    let arr = []
    // 如果任何一个数组为空，就退出循环
    while (left.length && right.length) {
        // 从左右子数组的最小元素中选择较小的元素
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
     
    // 连接剩余的元素，防止没有把两个数组遍历完整
    return [ ...arr, ...left, ...right ]
}

在这个函数中，通过把两个排好序的子数组（left、right）合并来获得一个排好序的大数组。首先，创建一个空数组。之后在 left 和 right 两个子数组中最小元素中的较小的一个，并将其添加到空数组。我们只需要检查 left 和 right 子数组中的第一个元素，因为它们是已排好序的。

阅读剩余部分