《算法基础：打开算法之门》一3.4 归并排序

3.4 归并排序

我们的下一个排序算法是归并排序，对于所有情况，它有一个仅仅Θ（nlgn）的运行时间。当将它的运行时间和选择排序与插入排序的最坏运行时间Θ（n2）进行比较时，我们仅仅是将n这个因子替换成了lgn这个因子。正如我们在第1章中所指出的那样，这是一个非常划算的交易。

归并排序与我们已经看到的两种排序算法相比有一些不足。首先，隐含在渐近符号前面的常量因子比另外两个算法的渐近符号前面的常量因子的值大。当然，一旦数组规模n变得非常大，那个常量因子也变得没有那么重要了。第二，归并排序不是原址的（in place）:它必须将整个输入数组进行完全的拷贝。而选择排序和插入排在任何时间仅仅拷贝一个数组项而不是对所有数组项都进行拷贝。如果空间非常宝贵，那么你可能并不会使用归并排序。

我们在归并排序中使用一个被称为分治法的通用模式。在分治法中，我们将原问题分解为类似于原问题的子问题，并递归地求解这些子问题，然后再合并这些子问题的解来得出原问题的解。回忆一下，在第2章中，为了执行递归操作，每次递归调用必须在同样问题的一个更小的实例上进行，最终会抵达一个基础情况。下面是分治算法的一般概述。1分解：把一个问题分解为多个子问题，这些子问题是更小实例上的原问题。2解决：递归地求解子问题。当子问题足够小时，按照基础情况来求解。403合并：把子问题的解合并成原问题的解。当使用归并排序对书架上的书进行排序时，每个子问题包括对书架上连续位置的书籍的排序。初始时，我们想要对n本书进行排序，即从位置1到位置n，但在一般子问题中，我们想要对从位置p到位置r的书进行排序。下面讲解我们如何应用分治法。1分解：通过找到位于p和r中间位置的数字q对问题进行分解。正如在二分查找中查找中间点一样，我们进行同样的操作，将p和r加起来，将该和除以2，并向下取整。2解决：对分解步骤得出的两个子问题的书进行递归排序，对从位置p到位置q的书籍进行递归排序，且对从位置q+1到位置r的书籍进行递归排序。3合并：将从位置p到q的排序好的书籍和从位置q+1到r的排序好的书籍进行合并，使得从位置p到位置r的书籍排好序。我们将马上介绍如何合并书籍。当少于两本书籍需要排序（也就是p≥r）时，基础情况会发生，因为不包含书的书集或者只拥有一本书的书集已经是排好序的。为了将这个观点转换成对数组进行排序，从位置p到位置r的书对应于子数组A［pr］。下面是归并排序程序，它会调用一个程序MERGE(A,p,q,r)，该程序会将排好序的子数组A［pq］和A［q+1r］合并为单一的排好序的子数组A［pr］。

尽管还不清楚MERGE程序是如何运行的，我们先看看MERGESORT程序运行的一个例子。我们以下面这个数组为例：

初始调用是MERGESORT(A,1,10)。第2A步计算出q为5，因此第2B步和第2C步的递归调用是MERGESORT(A,1,5)和MERGESORT(A,6,10)。

经过两次递归调用后，这两个子数组排序如下：

最终，在第2D步中调用MERGE(A,1,5,10)将两个排好序的子数组归并为一个单一的有序子数组，以下是这种情况下的整个数组：

如果展开递归，我们会得到以下图像。分叉箭头表明分解步骤，汇聚箭头表明归并步骤。出现在每个子数组上方的变量p、q和r指每次递归调用过程中对应的索引。斜体数字给出了经过初始调用MERGESORT(A,1,10)后程序调用发生的次序。例如，MERGE(A,1,3,5)是经过初始调用后的第13步的调用，MERGESORT(A,6,7)是第16步的调用。真正的工作发生在MERGE程序中。因此，MERGE程序不仅必须正确地运行，而且它必须运行很快。如果要归并一个总数为n的数组，由于每个元素必须调整至适当位置上，因此我们能设想的最好情况是Θ（n）时间，并且确实能够实现线性时间的归并。

继续参考书架那个例子，让我们只观察位于位置9～位置14的那部分书籍。假设已经排列好位置9～11的那部分书籍和位置12～14的那部分书籍。

我们将位置9～11的书籍组成一个堆，把按照字母排序作者名字排在最前面的书籍放在顶侧，并且对位置12～14的书籍按照相同的规则进行操作，制作成另外一个堆：

因为这两个堆都已经排好序了，因此那本应该放置在位置9的书籍一定是这两个堆顶侧书籍中的一个：Gustave Flaubert或者Charles Dickens写的书籍。根据作者名字的字典序，Dickens写的书籍应该排在Flaubert写的书籍的前面，因此我们将Dickens写的书籍移动到位置9处：

把Dickens所写的书籍放置在位置9后，放置在位置10处的书籍或者是置于第一个堆顶侧的书籍（即由Flaubert所写的书籍），或者是当前第二个堆的顶侧的书籍（即由Jack London所写的书籍）。同理，我们将由Flaubert所写的书籍移动至位置10处：

下一步，我们比较位于当前两个堆顶侧的书籍，即由Jonathan Swift和London所写的书籍，并且将London所写的书籍移动至位置11处。这导致Sir Walter Scott所写的书籍位于右边堆的顶侧，将它与Swift所写的书籍进行比较，我们将Scott所写的书籍移动到位置12处。此时，右边那个堆便为空：

剩下的操作是将位于左侧堆的书籍按序放到余下的位置处。现在位于位置9～14的所有书籍是有序的：

这个归并程序的效率如何呢？我们对每本书籍均进行了两次移动：一次是从书架上取下来并且将它放入一个堆上，另一次是将它从堆的顶侧移回到书架上。而且，每当决定将哪本书移回书架上时，我们仅仅需要比较两本书：那些在堆顶侧的书籍。因此，为了合并n本书籍，我们移动了2n次并且对成对的书籍至多比较n次。为什么要将书籍从书架上移动下来呢？要是将书籍保留在书架上，仅仅记录下哪本书已经放置在了书架上的正确位置上，45哪本书并没有放置在正确的位置上呢？那可能会导致更多的工作。例如，假定右半侧的每本书都应该出现在左半侧的每本书之前。在将右半侧的第一本书籍移动到左半侧的第一个位置之前时，我们必须将左半侧的每本书籍依次向右移动一个位置以腾出空间。并且之后对于出现在右半侧的下一个书籍，在将它移动到左半侧书籍的第二个位置之前，我们也必须进行同样的操作。针对右半侧的其余书籍也必须进行同样的操作。因此，每次想要将右半侧的一本书籍放置在它的正确位置上时，我们将必须移动一半的书籍——所有左半侧的书籍。上述论据证明了我们为什么不进行原址归并。实际上，可以在线性时间内实现原址归并，但是实现该程序相当复杂。下面回到如何将排好序的子数组A［pq］和A［q+1r］归并为A［pr］的问题上。我们首先将数组A中要归并的元素拷贝到临时数组中，随后将临时数组中的元素再归并到数组A中。令n1=q-p+1是数组A［pq］中的元素数目，且n2=r-q是数组A［q+1r］中的元素数目。我们创建包含n1个元素的临时数组B和包含n2个元素的数组C，并且按序将数组A［pq］中的元素拷贝至B中，同样地，我们按序将数组A［q+1r］中的元素拷贝至C中。现在重新将这些元素归并到A［pr］中而不用担心覆盖它们仅有的备份。我们像归并书籍一样归并数组元素。将数组B和数组C中的元素重新拷贝至子数组A［pr］中，记录当前数组B和C中还没有被拷贝到A的值的最小元素的索引，然后将其中较小的元素拷贝到数组A。我们能够在常量时间内断定两个元素中哪个元素较小，并将它拷贝至A［pr］中的正确位置上，并更新元素的索引。最终，其中一个数组的所有元素均拷贝至A［pr］中。这也意味着只剩下一个书堆。为了避免每次检查是否其中一个数组已经为空，我们使用以下技巧：在数组B和C的最右侧放置一个大于任意元素的值。想起我们在第2章的SENTINELLINEARSEARCH中所使用的标记技巧了吗？是的，这一思路是类似的。这里，我们使用∞(无穷)作为标记的排序关键字，46以便当一个带有∞的关键字是该数组中剩余的最小元素时，它确保了“无需”检查哪个数组有更小的剩余元素。实际上，我们可以令∞取任意一个比所有排序关键字大的值。例如，如果排序关键字是作者名字，那么∞可以取ZZZZ——当然，假定真实的作者名字中不会取ZZZZ这个值。一旦来自数组B和C的所有元素全部拷贝完成，这时两个数组均以它们的标记作为最小剩余元素。但是此时没有必要比较标记大小，因为到那时我们已将所有的“真实”元素（非哨兵元素）拷贝至A［pr］。由于我们提前知道会将所有元素拷贝～A［p］到A［r］中，当将一个元素拷贝至A［r］时，我们就结束操作。因此，我们仅仅需要在A的索引上运行一个从p到r的循环即可。以下是归并程序。虽然看起来很长，但是它刚好采用了上面介绍的方法。

经过步骤1～4，实现了对数组B和C的赋值操作，将A［p…q］拷贝至B且将A［q+1r］拷贝至C，并且将标记插入到这些数组中，47在第6步的主循环的每次迭代中，将最小的剩余元素拷贝至A［pr］的下一位置上，一旦它将B和C中的所有元素拷贝完毕就终止。在这个循环迭代中，i指向B中最小的剩余元素，j指向C中最小的剩余元素，k指向A中的元素要拷贝的位置。如果要将n个元素合并在一起（以便n=n1+n2），将元素拷贝至数组B和C中会花费Θ（n）时间，将每个元素又拷贝回A［pr］需要花费常量时间，因此全部的归并操作仅仅需要Θ（n）时间。我们之前宣称整个归并操作算法需花费Θ（nlgn）时间。我们做最简单的假定，即数组大小n是2的幂，以便每次分解数组时，子数组大小是相等的。（一般而言，n可能不是2的幂且在一个给定递归调用中，子数组大小可能是不相等的。如果考虑这些，则需要一个严格的分析证明，此时我们不考虑这些细节。）我们对归并排序进行如下分析。假定排序一个包含n个元素的子数组需要花费T(n)时间，它是一个随着n增加的函数（假定排序更多的元素会花费更长的时间）。时间T(n)来自于分治模式的三个部分所耗费时间的累加和：1分解花费常量时间，因为它只计算了索引q。2解决包括关于两个子数组的递归调用，每个子数组有n/2个元素。现在我们定义了排序一个子数组的时间，每个子数组的递归调用需花费T(n/2)时间。3通过合并排序好的子数组来合并这两个递归调用的结果需要花费Θ（n）的时间。因为与合并操作所需的Θ（n）时间相比，分解所需花费的常量时间是一个低阶项，因此可以将分解时间并入合并时间，并称分解和合并一共花费Θ（n）的时间。解决步骤花费T(n/2)+T(n/2)时间，即2 T(n/2)时间。现在我们对T(n)写一个等式：
其中f(n)代表分解和合并操作所花费的时间，如我们刚刚得出的，分解和合并操作共花费的时间是Θ（n）。48在算法学习过程中的一个常见做法是对等式进行近似且将我们所不关心的内容归结为一个函数，因此将该等式重写为

等等！这里似乎存在一些缺陷。我们已经定义了函数T，它用来描述类似的归并排序的运行时间！我们称这样一个等式为一个递归式，或者称为一个递归。问题是我们想将T(n)表达为非递归形式，也就是说，表示成并不关于它本身的一个函数。将一个表示成递归形式的函数转化为非递归形式可能是一个瓶颈，但是对于相当一大类递归式我们能运用一个被称为“主方法”的标准化方法。主方法适用于许多形为T（n)=aT（n/b）+f(n)的递归（但并非所有），其中a和b是正整数。幸运的是，它适合于我们的归并排序递归，并且给出了结果，T(n)为Θ（nlgn）。该Θ（nlgn）的运行时间适合于归并排序的所有情况——最好情况、最坏情况和介于这两个情况之间的所有情况。每个元素均被拷贝了Θ（lgn）次。你能从MERGE方法中看到，当它以p=1和r=n被调用时，它会对所有的n个元素进行拷贝，因此归并排序一定不是原址的。