算法导论随笔(二): 归并排序与分治策略

在上一篇文章中，我提到了两个排序算法，冒泡排序和归并排序。对于冒泡排序，上一篇文章中已经介绍了它的复杂度为什么是O(n²)。在这一篇文章中，我来写写归并排序的原理以及如何计算它的复杂度。

归并排序(Merge Sort)

首先介绍一下归并排序。归并排序(Merge Sort)是一种经典的排序算法，它的复杂度是O(nlogn)。 对于刚接触算法的同学来说，这个表达式可能比较奇怪。在后文中会介绍它的复杂度为什么是O(nlogn)。

注意: 在算法领域，logn是log₂n的缩写，即以2为底n的对数，一定不要混淆。(尤其是数学或其他领域中logn或lgn可能是指以10为底n的对数)

这个算法使用的是分治策略(Divide-and-conquer)。算法分为3个部分，即分解(Divide)，解决(Conquer)和合并(Combine)。我们用一个例子来看下。

首先来看分解部分的运行示例图：

假设我们有8个数字作为输入，那么归并排序的第一步就是把这8个数字平均分成两组，每组4个数字。接着，这两组4个数字又分别被分为2组，每组两个数字。接着继续分组，直到每组只有一个数字。这一部分的目的是将问题尽可能地分解，直到没法再分解为止。此时，由于问题已经被分解为最小，因此每一个问题也最简单，使我们可以在一个单位时间内就解决1个问题。比如图中8个数字被分为8组，由于每一组只有一个数字，所以每组的数字都是排好序的（因为只有1个数字，所以这个数字就是排好序的）。

接下来看解决和合并部分。所谓解决，就是把分解后的简单问题求解。而合并，就是已解决的简单问题的解法，通过合并，一步一步得到最初的复杂问题的解法。

上图中，85和24是两个排好序的数字通过合并和进一步的解决，得到1组2个排好序的数字24和85，类似地63和45也得到45和63。接着这2组2个数字的数组，又被合并和解决得到24，45，63，85这个排好序的数组。而图中右半部分也得到17， 31， 50， 96这4个排好序的数字。最后，两组数字再一次通过合并和解决，得到最后的结果。

归并排序的分析

前文中提到，归并排序算法的复杂度是O(nlogn)。这个结果是怎么计算出来的呢？这里要使用到二叉树的概念。归并排序算法的执行可以用一颗二叉树来表示。首先我们用MERGE_SORT()代表算法的主函数（分解+解决），也就是递归调用的函数；用MERGE()代表合并过程。
程序MERGE_SORT的伪代码如下：

算法的主要思路就是找到初始数组的中点，然后将数组平均分为两半，再对两个子数组递归调用MERGE_SORT函数。最后再调用MERGE函数来进行合并。我们可以看以下二叉树：

图中二叉树的每一个节点代表了一次对于MERGE_SORT的递归调用。每个节点(Node)中箭头左侧的数字是调用之前的数组，箭头右侧代表的是调用函数后得到的结果数组。这棵树的根节点(root)代表了第一次对MERGE_SORT的调用；其他每一个节点都代表了一次对MERGE_SORT的递归调用。而叶子(leaf nodes)节点(蓝色的节点)代表了MERGE_SORT的停止点，也代表了解决和MERGE合并的开始。

对于一课有n个叶子节点的完全二叉树，该二叉树的高度(height)为
$height = log(n)$height=log(n)
例如图中有8个叶子节点，则高度为log8 = 3，因为2³ = 8。而对于树的每一层，节点数量为n/2ⁱ ，比如第0层为8个节点，即8/2⁰ = 8。由于算法考虑的是程序运行的最坏情况，而每一层的节点数都不会超过最后一层，因此我们可以直接近似估计认为每一层的节点数都为n。所以问题就很简单了，树一共有log(n)层，每层有n个节点，每个节点需要的操作是O(1)，所以这个算法的复杂度就是
$T(n)= logn层 × 每层n个节点 ×每个节点操作O(1) = O(nlogn)$T(n)=logn层×每层n个节点×每个节点操作O(1)=O(nlogn)
这个计算的方法并不严谨，因为它近似估计每层都是n个节点。但这并不影响结果，因为我们知道计算复杂度是要忽略掉结果前面的系数，因此不论运算过程中产生多少个系数，这些系数最后都会被忽略。所以结果一定是相同的。

用更不严谨的话来说，求这个算法的复杂度，其实就是把上面的二叉树当成一个三角形，而求复杂度的过程其实就是计算该三角形的面积。所以根据三角形面积公式，
$T(n)= 底×高 / 2 = n × logn / 2 = O(1/2 nlogn) = O(nlogn)$T(n)=底×高/2=n×logn/2=O(1/2nlogn)=O(nlogn)
这种方法可以让我们省去很多时间直接获取结果。

分治策略与归并排序的严谨证明

分治策略的核心是对递归函数的使用。以归并排序为例，分治策略的算法复杂度可以使用如下公式表示。

先说公式的下半部分，也就是递归。归并排序中的解决步骤是合并两个已排序的数组，其中每个数组都有n/2个元素。2T(n/2)代表着解决两个分解过的数组；bn代表了对结果的合并，其中b是一个常数，也就是说合并的步骤是O(n)。

再来看上半部分。对于n<2时，也就是数组已经被分解至只剩一个元素，此时对该元素的排序消耗的是常数时间。这里用b表示。也就是说，对于单个元素数组的排序，复杂度为O(1)。

我们需要求出复杂度T(n)，所以我们要对这个公式进行变形，使得其等号左侧只含有T(n)而右侧不含有符号T。分解方法如下。

那么这个递归在什么时候结束呢？显然是访问到二叉树的最后一层（叶子节点）时。此时数组被分为n个只有1个元素的数组。因此2ⁱ = n，即i = logn。
所以，上述公式变为
$T(n) = bn + bnlogn$T(n)=bn+bnlogn
由于b是常数，而nlogn的渐进上界高于n（参见上一篇文章），因此n被忽略，该算法的复杂度为O(nlogn)。

写在最后

对于使用了分治策略的算法，书中介绍了一种通用方法来计算算法的复杂度。这个方法叫做主方法(Master Method), 使用的定理叫做主定理(Master Theorem)。这种看似复杂的方法极大地简化了计算复杂度的计算量，并且其实非常简单。下一篇笔记中我会用一些例子来介绍这种方法。

归并排序的具体实现代码在网上有很多，这里不再给出。

附归并排序中的合并步骤MERGE的伪代码，大家可以看看为什么它的复杂度是O(n)。