归并排序

归并排序是一种以分治（Divide and Conquer）概念为基础的排序算法。

分治 Divide and Conquer

分治指的是，把一个大的问题递归的分解成若干个较小的子问题，直到它们变得简单到可以直接解决。

归并排序原理

归并排序利用分治思想，大体上的算法实现步骤是这样的：

1. 把数组分成两半。如果是奇数个，那么可以把多余的元素放到任意一边。
2. 用相同的方式划分子数组，直到子数组只包含一个元素。
3. 从这些包含单个元素的数组开始，进行合并。并对每个进行合并的数组元素进行排序。
4. 重复步骤 3，直到合并完成，就得到了排序好的数组。

归并排序 JavaScript 实现代码

归并排序是效率比较高的一种排序算法，掌握它对于面试算法，或者实现排序功能都很有帮助。接下来我们看一下如何使用 JavaScript 来实现归并排序。

function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());
  return result;
}

function mergeSort(items) {
  if (items.length < 2) {
    return items;
  }
  const middle = Math.floor(items.length / 2);
  const left = items.slice(0, middle);
  const right = items.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

这个代码是一个比较简单的归并排序算法实现，大体上有这样几个部分：

• mergeSort 函数是用来递归的把原数组划分成子数组，每次分成左右两部分，直到子数组中只有一个元素。
  • 里边计算数组的中间元素索引，然后使用数组的 slice 方法把它们分成两半，奇数个元素会把多余的元素分到右边。
  • 之后调用 merge 函数，合并左右两个子数组。
• merge 函数是用来把子数组排序后，合并成一个大数组，最终合并为和原始数组长度一样的结果数组。
  • 在 merge 中，因为左右两个子数组已经是基本有序的，所以只要比对两个数组中的第一个元素，较小的放到结果数组前边，较大的放到右边。
  • 放到结果数组中的元素，会从 left 或者 right 数组中删除，这里使用了 shift() 方法。
  • 如果有的数组元素多，剩余的元素会一次性添加到结果数组中。

完成之后，就会得到排好序的数组。 现在，我们用一个测试数组来看一下代码的执行过程：

const testArr = [3, 1, 6, 7, 2, 4, 5];
const result = mergeSort(testArr);

console.log(result);

测试归并排序代码

假设我们的数组有这样的元素：3, 1, 6, 7, 2, 4, 5。

归并排序就像是遍历树一样，在第一次调用 mergeSort() 函数的时候，数组分成了[3, 1, 6] 和 [7, 2, 4, 5] 两部分。

之后 [3, 1, 6] 分成 [3] 和 [1, 6]。

[3] 不能再分了，最左侧的节点遍历完成，开始遍历右半边。

[1, 6] 再分成 [1] 和 [6]，这样左子树遍历完毕，开始合并。

[1] 和 [6] 因为都只有一个元素，1 比 6 小，把 1 放前边，合并成 [1, 6]。并且没有剩余的元素，merge 函数会返回结果。

[3] 这里只有一个节点，它本身不用合并。

之后 返回上一层，[3] 和 [1, 6] 合并，判断 3 比 1 大，先把 1 放到结果数组中，然后 3 比 6 小，把 3 放到结果数组中，最后把剩余的 6 放到结果数组，形成 [1, 3, 6]。

接下来继续分割右面的 [7, 2, 4, 5]，变成 [7, 2] 和 [4, 5]。

[7, 2]，分成 [7] 和 [2]。

之后进行合并，7 比 2 大，合并成** [2, 7]**。

再分割 [4, 5] 为 [4] 和 [5]，之后合并成** [4, 5]**。

合并 [2, 7] 和 [4, 5]，2 比 4 小，先放 2，然后 7 比 4 大，放 4，7 比 5 大，放 5，最后放 7，形成 [2, 4, 5, 7]。

最后 [1, 3, 6] 和 [2, 4, 5, 7] 合并，用同样的比对方法，形成 [1, 2, 3, 4, 5, 6, 7]。

这样排序就完成了。

算法复杂度

归并排序的算法复杂度在最坏情况下是 O(Nlog(N))。

小结

好了，这个就是归并排序的原理和 JavaScript 实现代码，当然，归并排序的实现方式不止一种，例如还有更省空间的原地排序，不过理解起来可能会更复杂，有兴趣的小伙伴有时间可以自己研究一下。这节课你学会了吗？如果有帮助请三连并关注，想学更多的开发知识，可以在评论区留言，感谢观看！