数据结构与算法之ACM Fellow-算法 2.2 归并排序

数据结构与算法之ACM Fellow-算法 2.2 归并排序

在本节中我们所讨论的算法都基于 归并 这个简单的操作，即将两个有序的数组归并成一个更大的有序数组。很快人们就根据这个操作发明了一种简单的递归排序算法： 归并排序。要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。你将会看到，归并排序最吸引人的性质是它能够保证将任意长度为

的数组排序所需时间和

成正比；它的主要缺点则是它所需的额外空间和

成正比。简单的归并排序如图 2.2.1 所示。
图 2.2.1　归并排序示意图
2.2.1　原地归并的抽象方法

实现归并的一种直截了当的办法是将两个不同的有序数组归并到第三个数组中，两个数组中的元素应该都实现了 Comparable 接口。实现的方法很简单，创建一个适当大小的数组然后将两个输入数组中的元素一个个从小到大放入这个数组中。
但是，当用归并将一个大数组排序时，我们需要进行很多次归并，因此在每次归并时都创建一个新数组来存储排序结果会带来问题。我们更希望有一种能够在原地归并的方法，这样就可以先将前半部分排序，再将后半部分排序，然后在数组中移动元素而不需要使用额外的空间。你可以先停下来想想应该如何实现这一点，乍一看很容易做到，但实际上已有的实现都非常复杂，尤其是和使用额外空间的方法相比。
尽管如此，将原地归并 抽象化 仍然是有帮助的。与之对应的是我们的方法签名 merge(a, lo, mid, hi)，它会将子数组 a[lo..mid] 和 a[mid+1..hi] 归并成一个有序的数组并将结果存放在 a[lo..hi] 中。下面的代码只用几行就实现了这种归并。它将涉及的所有元素复制到一个辅助数组中，再把归并的结果放回原数组中。实现的另一种方法请见练习 2.2.10。

原地归并的抽象方法

1. public static void merge(Comparable[] a, int lo, int mid, int hi)
2. {  // 将a[lo..mid] 和 a[mid+1..hi] 归并
3. int i = lo, j = mid+1;
5. for (int k = lo; k <= hi; k++)  // 将a[lo..hi]复制到aux[lo..hi]
6.    aux[k] = a[k];
8. for (int k = lo; k <= hi; k++)  // 归并回到a[lo..hi]
9.    if      (i > mid)              a[k] = aux[j++];
10.    else if (j > hi )              a[k] = aux[i++];
11.    else if (less(aux[j], aux[i])) a[k] = aux[j++];
12.    else a[k] =                    aux[i++];
13. }

复制代码

该方法先将所有元素复制到 aux[] 中，然后再归并回 a[] 中。方法在归并时（第二个 for 循环）进行了 4 个条件判断：左半边用尽（取右半边的元素）、右半边用尽（取左半边的元素）、右半边的当前元素小于左半边的当前元素（取右半边的元素）以及右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。
原地归并的抽象方法的轨迹

2.2.2　自顶向下的归并排序

对应视频资源地址：资源网盘分享
更多资源资源群 资源群
群满加新共享群：备份群
算法 2.4 基于原地归并的抽象实现了另一种递归归并，这也是应用高效算法设计中 分治思想 的最典型的一个例子。这段递归代码是归纳证明算法能够正确地将数组排序的基础：如果它能将两个子数组排序，它就能够通过归并两个子数组来将整个数组排序。

算法 2.4　自顶向下的归并排序

1. public class Merge
2. {
3. private static Comparable[] aux;      // 归并所需的辅助数组
5. public static void sort(Comparable[] a)
7. {
8.    aux = new Comparable[a.length];    // 一次性分配空间
9.    sort(a, 0, a.length - 1);
10. }
12. private static void sort(Comparable[] a, int lo, int hi)
13. {  // 将数组a[lo..hi]排序
14.    if (hi <= lo) return;
15.    int mid = lo + (hi - lo)/2;
16.    sort(a, lo, mid);       // 将左半边排序
17.    sort(a, mid+1, hi);     // 将右半边排序
18.    merge(a, lo, mid, hi);  // 归并结果（代码见“原地归并的抽象方法”）
19. }
20. }

复制代码

自底向上的归并排序会多次遍历整个数组，根据子数组大小进行两两归并。子数组的大小 sz 的初始值为 1，每次加倍。最后一个子数组的大小只有在数组大小是 sz 的偶数倍的时候才会等于 sz（否则它会比 sz 小）。
自底向上的归并排序的归并结果

命题 H。对于长度为

的任意数组，自底向上的归并排序需要

至

次比较，最多访问数组

次。
证明。处理一个数组的遍数正好是

。每一遍会访问数组

次，比较次数在

和

之间。

当数组长度为 2 的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同。其他时候，两种方法的比较和数组访问的次序会有所不同（请见练习 2.2.5）。
自底向上的归并排序比较适合 用链表 组织的数据。想象一下将链表先按大小为 1 的子链表进行排序，然后是大小为 2 的子链表，然后是大小为 4 的子链表等。这种方法只需要重新组织链表链接就能将链表 原地 排序（不需要创建任何新的链表结点）。
用自顶向下或是自底向上的方式实现任何分治类的算法都很自然。归并排序告诉我们，当能够用其中一种方法解决一个问题时，你都应该试试另一种。你是希望像 Merge.sort() 中那样化整为零（然后递归地解决它们）的方式解决问题，还是希望像 MergeBU.sort() 中那样循序渐进地解决问题呢？
2.2.4　排序算法的复杂度

学习归并排序的一个重要原因是它是证明计算复杂性领域的一个重要结论的基础，而计算复杂性能够帮助我们理解排序自身固有的难易程度。计算复杂性在算法设计中扮演着非常重要的角色，而这个结论正是和排序算法的设计直接相关的，因此接下来我们就要详细地讨论它。
研究复杂度的第一步是建立一个计算模型。一般来说，研究者会尽量寻找一个和问题相关的最简单的模型。对排序来说，我们的研究对象是基于比较的算法，它们对数组元素的操作方式是由主键的比较决定的。一个基于比较的算法在两次比较之间可能会进行任意规模的计算，但它只能通过主键之间的比较得到关于某个主键的信息。因为我们局限于实现了 Comparable 接口的对象，本章中的所有算法都属于这一类（注意，我们忽略了访问数组的开销）。在第 5 章中，我们会讨论不局限于 Comparable 元素的算法。

命题 I。没有任何基于比较的算法能够保证使用少于

次比较将长度为

的数组排序。
证明。首先，假设没有重复的主键，因为任何排序算法都必须能够处理这种情况。我们使用二叉树来表示所有的比较。树中的 结点 要么是一片 叶子

，表示排序完成且原输入的排列顺序是 a[i0], a[i1], ..., a[iN-1]，要么是一个 内部结点

，表示 a 和 a[j] 之间的一次比较操作，它的左子树表示 a 小于 a[j] 时进行的其他比较，右子树表示 a 大于 a[j] 时进行的其他比较。从根结点到叶子结点每一条路径都对应着算法在建立叶子结点所示的顺序时进行的所有比较。例如，这是一棵

时的比较树：
我们从来没有明确地构造这棵树——它只是用来描述算法中的比较的一个数学工具。
从比较树观察得到的第一个重要结论是这棵树应该至少有

个叶子结点，因为

个不同的主键会有

种不同的排列。如果叶子结点少于

，那肯定有一些排列顺序被遗漏了。算法对于那些被遗漏的输入肯定会失败。
从根结点到叶子结点的一条路径上的内部结点的数量即是某种输入下算法进行比较的次数。我们感兴趣的是这种路径能有多长（也就是树的 高度），因为这也就是算法比较次数的最坏情况。二叉树的一个基本的组合学性质就是高度为

的树最多只可能有

个叶子结点，拥有

个结点的树是完美平衡的，或称为 完全树。下图所示的就是一个

的例子。
结合前两段的分析可知，任意基于比较的排序算法都对应着一棵高

的比较树（如下图所示），其中：

叶子结点的数量

的值就是最坏情况下的比较次数，因此对不等式的两边取对数即可得到任意算法的比较次数至少是

。根据斯特灵公式对阶乘函数的近似（见表 1.4.6）可得

。

这个结论告诉了我们在设计排序算法的时候能够达到的最佳效果。例如，如果没有这个结论，我们可能会去尝试设计一个在最坏情况下比较次数只有归并排序的一半的基于比较的算法。命题 I 中的下限告诉我们这种努力是没有意义的——这样的算法不存在。这是一个重要结论，适用于任何我们能够想到的基于比较的算法。
命题 H 表明归并排序在最坏情况下的比较次数为

。这是其他排序算法复杂度的 上限，也就是说更好的算法需要保证使用的比较次数更少。命题 I 说明没有任何排序算法能够用少于

次比较将数组排序，这是其他排序算法复杂度的 下限。也就是说，即使是最好的算法在最坏的情况下也至少需要这么多次比较。将两者结合起来也就意味着：

命题 J。归并排序是一种渐进最优的基于比较排序的算法。
证明。更准确地说，这句话的意思是，归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是

。命题 H 和命题 I 证明了这些结论。

需要强调的是，和计算模型一样，我们需要精确地定义最优算法。例如，我们可以 严格地 认为仅仅只需要

次比较的算法才是最优的排序算法。我们不这么做的原因是，即使对于很大的

，这种算法和（比如说）归并排序之间的差异也并不明显。或者我们也可以放宽最优的定义，使之包含任意在最坏情况下的比较次数都在

的某个常数因子范围之内的排序算法。我们不这么做的原因是对于很大的

，这种算法和归并排序之间的差距还是很明显的。
计算复杂度的概念可能会让人觉得很抽象，但解决可计算问题内在困难的基础性研究则不管怎么说都是非常必要的。而且，在适用的情况下，关键在于计算复杂度会影响优秀软件的开发。首先，准确的上界为软件工程师保证性能提供了空间。很多例子表明，平方级别排序的性能低于线性排序。其次，准确的下界可以为我们节省很多时间，避免因不可能的性能改进而投入资源。
但归并排序的最优性并不是结束，也不代表在实际应用中我们不会考虑其他的方法了，因为本节中的理论还是有许多局限性的，例如：

• 归并排序的空间复杂度不是最优的；
  
• 在实践中不一定会遇到最坏情况；
  
• 除了比较，算法的其他操作（例如访问数组）也可能很重要；
  
• 不进行 比较也能将某些数据排序。
  

因此在本书中我们还将继续学习其他一些排序算法。
如果您想了解更多技术资源，课件对应视频地址。欢迎点击这里1查看
如果您想了解更多技术资源，欢迎点击这里2查看

本文由博客一文多发平台 OpenWrite 发布！

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！