第28章：归并排序

归并排序是最有效的排序算法之一。它的时间复杂度为O(n log n)，是所有通用排序算法中最快的算法之一。归并排序背后的理念是分而治之--将一个大问题分解成几个更小的、更容易解决的问题，然后将这些解决方案归并为一个最终结果。归并排序的口号是先分割，后归并。在本章中，你将从头开始实现归并排序。让我们从一个例子开始。

例子

假设你有一堆没有分类的扑克牌。

归并排序算法的工作原理如下。

  1. 首先，把这堆牌分成两半。你现在有两堆没有分类的扑克牌。

  1. 现在，继续拆分这两堆牌，直到你不能再拆分为止。最后，你将在每一堆中拥有一张（已分类的！）卡片。

  1. 最后，按照你分裂它们的相反顺序归并这些堆积物。在每次归并过程中，你要把内容按分类顺序排列。这个过程很简单，因为每一堆都已经分类了。



实现

打开启动器的playground，开始实施。

分割

在playground的Source文件夹中，创建一个名为MergeSort.swift的新文件。在该文件中写下以下内容。

这里，你把数组分成了两半。分割一次是不够的。然而，你必须不断地递归分割，直到你不能再分割为止，也就是每个细分部分只包含一个元素的时候。

要做到这一点，请更新mergeSort如下。

你在这里做了两个改变。

  1. 递归需要一个基例，你也可以把它看作是一个 "退出条件"。

在这种情况下，基本情况是当数组只有一个元素时。

  1. 你现在在原数组的左右两半上调用mergeSort。只要你把数组分成两半，你就会尝试再次分割。

在你的代码编译之前，还有更多的工作要做。现在你已经完成了分割的部分，是时候关注归并了。

归并

你的最后一步是归并左边和右边的数组。为了保持干净，你将为此创建一个单独的归并函数。

归并函数的唯一职责是接收两个排序的数组，并在保留排序顺序的情况下将其归并。在mergeSort函数的下面添加以下内容。


以下是发生的情况。

  1. leftIndex和rightIndex变量在你解析这两个数组时跟踪你的进度。

  2. 结果数组将容纳归并后的数组。

  3. 从头开始，你依次比较左右两个数组中的元素。如果你已经到了两个数组的末尾，就没有其他东西可以比较了。

  4. 两个元素中较小的那个进入结果数组。如果这两个元素相等，就可以把它们都加起来。

  5. 第一个循环保证左边或右边是空的。由于两个数组都是排序的，这就保证了剩下的元素大于或等于当前结果中的元素。在这种情况下，你可以不通过比较来追加其余的元素。

收尾工作

通过调用merge来完成mergeSort函数。因为你以递归方式调用mergeSort，算法会在归并前对两半进行分割和排序。

这段代码是归并排序算法的最终版本。下面是对归并排序的关键程序的总结。

  1. 归并排序的策略是分而治之，这样你就能解决很多小问题，而不是一个大问题。

  2. 它有两个核心职责：一个是递归地分割初始数组的方法，一个是归并两个数组的方法。

  3. 归并函数应该接收两个排序的数组并产生一个单一的排序数组。

最后--是时候看看这个动作了。回到playground的主页面，用下面的方法测试你的归并排序。

example(of: "merge sort") {
  let array = [7, 2, 6, 3, 9]
  print("Original: \(array)") 
  print("Merge sorted: \(mergeSort(array))")
}

会得到这样的输出。

---Example of merge sort--
Original: [7, 2, 6, 3, 9] 
Merge sorted: [2, 3, 6, 7, 9]

性能

归并排序的最佳、最差和平均时间复杂度都是O(n log n)，这还不算太糟。如果你很难理解n log n是怎么来的，可以想想递归是怎么工作的。

这使得总成本达到O(log n) × O(n) = O(n log n)。

前一章的排序算法是就地的，并使用swapAt来移动元素。相比之下，归并排序需要分配额外的内存来完成其工作。有多大？有log2(n)级的递归，每一级都要使用n个元素。这使得总的空间复杂性为O(n log n)。归并排序是标志性的排序算法之一。它相对简单易懂，可以作为分而治之算法工作原理的一个很好的介绍。归并排序是O(n log n)，而这个实现需要O(n log n)的空间。如果你巧妙地记账，你可以通过丢弃没有被积极使用的内存，将所需的内存减少到O(n)。

关键点

上一章 目录 下一章