常用算法（2）分而治之算法
--------------------------------------------------------------------------------
作者:liuchaohai 来源: 类别:数据算法 日期:2002.09.19 今日/总浏览: 3/6
第 2 章 分而治之算法
君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、矩阵乘法、残缺棋盘、排序、选择和一个计算几何问题--找出二维空间中距离最近的两个点。
本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致）。
2.1 算法思想
分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。
例2-1 [找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。
另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。
现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。
例2-2 [金块问题] 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。
假设袋中有n 个金块。可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。程序2 - 2 6和2 - 2 7是另外两种方法，前者需要进行2n-2次比较，后者最多需要进行2n-2次比较。
下面用分而治之方法对这个问题进行求解。当n很小时，比如说， n≤2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法。
假设n= 8。这个袋子被平分为各有4个金块的两个袋子A和B。为了在A中找出最重和最轻的金块，A中的4个金块被分成两组A1和A2。每一组有两个金块，可以用一次比较在A中找出较重的金块HA1和较轻的金块LA1。经过另外一次比较，又能找出HA 2和LA 2。现在通过比较HA1和HA2，能找出HA；通过LA 1和LA2的比较找出LA。这样，通过4次比较可以找到HA 和LA。同样需要另外4次比较来确定HB 和LB。通过比较HA 和HB（LA 和LB），就能找出所有金块中最重和最轻的。因此，当n= 8时，这种分而治之的方法需要1 0次比较。如果使用程序1 - 3 1，则需要1 3次比较。如果使用程序2 - 2 6和2 - 2 7，则最多需要1 4次比较。设c(n)为使用分而治之方法所需要的比较次数。为了简便，假设n是2的幂。当n= 2时，c(n) = 1。对于较大的n，c(n) = 2c(n/ 2 ) + 2。当n是2的幂时，使用迭代方法（见例2 - 2 0）可知
c(n) = 3n/ 2 - 2。在本例中，使用分而治之方法比逐个比较的方法少用了2 5％的比较次数。
例2-3 [矩阵乘法] 两个n×n 阶的矩阵A与B的乘积是另一个n×n 阶矩阵C，C可表示为假如每一个C(i, j) 都用此公式计算，则计算C所需要的操作次数为n3 m+n2 (n- 1) a，其中m表示一次乘法，a 表示一次加法或减法。
为了得到两个矩阵相乘的分而治之算法，需要： 1) 定义一个小问题，并指明小问题是如何进行乘法运算的； 2) 确定如何把一个大的问题划分成较小的问题，并指明如何对这些较小的问题进行乘法运算； 3) 最后指出如何根据小问题的结果得到大问题的结果。为了使讨论简便，假设n 是2的幂（也就是说， n是1，2，4，8，1 6，.）。
首先，假设n= 1时是一个小问题，n> 1时为一个大问题。后面将根据需要随时修改这个假设。对于1×1阶的小矩阵，可以通过将两矩阵中的两个元素直接相乘而得到结果。
考察一个n> 1的大问题。可以将这样的矩阵分成4个n/ 2×n/ 2阶的矩阵A1，A2，A3，和A4。当n 大于1且n 是2的幂时，n/ 2也是2的幂。因此较小矩阵也满足前面对矩阵大小的假设。矩阵Bi 和Ci 的定义与此类似.
根据上述公式，经过8次n/ 2×n/ 2阶矩阵乘法和4次n/ 2×n/ 2阶矩阵的加法，就可以计算出A与B的乘积。因此，这些公式能帮助我们实现分而治之算法。在算法的第二步，将递归使用分而治之算法把8个小矩阵再细分（见程序2 - 1 9）。算法的复杂性为(n3 )，此复杂性与程序2 - 2 4直接使用公式（2 - 1）所得到的复杂性是一样的。事实上，由于矩阵分割和再组合所花费的额外开销，使用分而治之算法得出结果的时间将比用程序2 - 2 4还要长。
为了得到更快的算法，需要简化矩阵分割和再组合这两个步骤。一种方案是使用S t r a s s e n方法得到7个小矩阵。这7个小矩阵为矩阵D, E, ., J，矩阵D到J可以通过7次矩阵乘法， 6次矩阵加法，和4次矩阵减法计算得出。前述的4个小矩阵可以由矩阵D到J通过6次矩阵加法和两次矩阵减法得出.
用上述方案来解决n= 2的矩阵乘法。将某矩阵A和B相乘得结果C，如下所示：
因为n> 1，所以将A、B两矩阵分别划分为4个小矩阵，每个矩阵为1×1阶，仅包含一个元素。1×1阶矩阵的乘法为小问题，因此可以直接进行运算。利用计算D～J的公式，得：
D= 1（6-8）=-2
E= 4（7-5）= 8
F=（3 + 4）5 = 3 5
G=（1 + 2）8 = 2 4
H=（3-1）（5 + 6）= 2 2
I=（2-4）（7 + 8）=-3 0
J=（1 + 4）（5 + 8）= 6 5
根据以上结果可得：
对于上面这个2×2的例子，使用分而治之算法需要7次乘法和1 8次加/减法运算。而直接使用公式（2 - 1），则需要8次乘法和7次加/减法。要想使分而治之算法更快一些，则一次乘法所花费的时间必须比11次加/减法的时间要长。
假定S t r a s s e n矩阵分割方案仅用于n≥8的矩阵乘法，而对于n<8的矩阵乘法则直接利用公式（2 - 1）进行计算。则n= 8时，8×8矩阵相乘需要7次4×4矩阵乘法和1 8次4×4矩阵加/减法。每次矩阵乘法需花费6 4m+ 4 8a次操作，每次矩阵加法或减法需花费1 6a次操作。因此总的操作次数为7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接计算方法，则需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接计算方法快，至少要求5 1 2-4 4 8次乘法的开销比6 2 4-4 4 8次加/减法的开销大。或者说一次乘法的开销应该大于近似2 . 7 5次加/减法的开销。
假定n<1 6的矩阵是一个"小"问题，S t r a s s e n的分解方案仅仅用于n≥1 6的情况，对于n<1 6的矩阵相乘，直接利用公式（ 2 - 1）。则当n= 1 6时使用分而治之算法需要7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a次操作。直接计算时需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的开销与一次加/减法的开销相同，则S t r a s s e n方法需要7 8 7 2次操作及用于问题分解的额外时间，而直接计算方法则需要7 9 3 6次操作加上程序中执行f o r循环以及其他语句所花费的时间。即使直接计算方法所需要的操作次数比St r a s s e n方法少，但由于直接计算方法需要更多的额外开销，因此它也不见得会比S t r a s s e n方法快。
n 的值越大，Strassen 方法与直接计算方法所用的操作次数的差异就越大，因此对于足够大的n，Strassen 方法将更快。设t (n) 表示使用Strassen 分而治之方法所需的时间。因为大的矩阵会被递归地分割成小矩阵直到每个矩阵的大小小于或等于k（k至少为8，也许更大，具体值由计算机的性能决定）. 用迭代方法计算，可得t(n) = (nl og27 )。因为l og27 ≈2 . 8 1，所以与直接计算方法的复杂性(n3 )相比，分而治之矩阵乘法算法有较大的改进。
注意事项
分而治之方法很自然地导致了递归算法的使用。在许多例子里，这些递归算法在递归程序中得到了很好的运用。实际上，在许多情况下，所有为了得到一个非递归程序的企图都会导致采用一个模拟递归栈。不过在有些情况下，不使用这样的递归栈而采用一个非递归程序来完成分而治之算法也是可能的，并且在这种方式下，程序得到结果的速度会比递归方式更快。解决金块问题的分而治之算法（例2 - 2）和归并排序方法（ 2 . 3节）就可以不利用递归而通过一个非递归程序来更快地完成。
例2-4 [金块问题] 用例2 - 2的算法寻找8个金块中最轻和最重金块的工作可以用二叉树来表示。这棵树的叶子分别表示8个金块（a, b,., h)，每个阴影节点表示一个包含其子树中所有叶子的问题。因此，根节点A表示寻找8个金块中最轻、最重金块的问题，而节点B表示找出a,b,c 和d 这4个金块中最轻和最重金块的问题。算法从根节点开始。由根节点表示的8金块问题被划分成由节点B和C所表示的两个4金块问题。在B节点，4金块问题被划分成由D和E所表示的2金块问题。可通过比较金块a 和b 哪一个较重来解决D节点所表示的2金块问题。在解决了D和E所表示的问题之后，可以通过比较D和E中所找到的轻金块和重金块来解决B表示的问题。接着在F，G和C上重复这一过程，最后解决问题A。
可以将递归的分而治之算法划分成以下的步骤：
1) 从图2 - 2中的二叉树由根至叶的过程中把一个大问题划分成许多个小问题，小问题的大小为1或2。
2) 比较每个大小为2的问题中的金块，确定哪一个较重和哪一个较轻。在节点D、E、F和G上完成这种比较。大小为1的问题中只有一个金块，它既是最轻的金块也是最重的金块。
3) 对较轻的金块进行比较以确定哪一个金块最轻，对较重的金块进行比较以确定哪一个金块最重。对于节点A到C执行这种比较。
根据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。
当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。
首先处理n≤1的情况。若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。
在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和
最大值，这个工作对应于3 )。for 循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [ M a x ]进行比较，根据比较结果来修改M i n和M a x（如果必要）。
下面进行复杂性分析。注意到当n为偶数时，在for 循环外部将执行一次比较而在f o r循环内部执行3 ( n / 2 - 1 )次比较，比较的总次数为3 n / 2 - 2。当n 为奇数时，f o r循环外部没有执行比较，而内部执行了3(n-1)/2次比较。因此无论n 为奇数或偶数，当n>0时，比较的总次数为「3n/2ù-2次。
程序14-1 找出最小值和最大值的非递归程序
template<class T>
bool MinMax(T w[], int n, T& Min, T& Max)
{// 寻找w [ 0 : n - 1 ]中的最小和最大值
// 如果少于一个元素，则返回f a l s e
// 特殊情形： n <= 1
if (n < 1) return false;
if (n == 1) {Min = Max = 0;
return true;}
/ /对Min 和M a x进行初始化
int s; // 循环起点
if (n % 2) {// n 为奇数
Min = Max = 0;
s = 1;}
else {// n为偶数，比较第一对
if (w[0] > w[1]) {
Min = 1;
Max = 0;}
else {Min = 0;
Max = 1;}
s = 2;}
// 比较余下的数对
for (int i = s; i < n; i += 2) {
// 寻找w[i] 和w [ i + 1 ]中的较大者
// 然后将较大者与w [ M a x ]进行比较
// 将较小者与w [ M i n ]进行比较
if (w[i] > w[i+1]) {
if (w[i] > w[Max]) Max = i;
if (w[i+1] < w[Min]) Min = i + 1;}
else {
if (w[i+1] > w[Max]) Max = i + 1;
if (w[i] < w[Min]) Min = i;}
}
return true;
}
练习
1. 将例1 4 - 1的分而治之算法扩充到n> 1个硬币的情形。需要进行多少次重量的比较？
2. 考虑例1 4 - 1的伪币问题。假设把条件"伪币比真币轻"改为"伪币与真币的重量不同"，同样假定袋中有n 个硬币。
1) 给出相应分而治之算法的形式化描述，该算法可输出信息"不存在伪币"或找出伪币。算法应递归地将大的问题划分成两个较小的问题。需要多少次比较才能找到伪币（如果存在伪币）？
2) 重复1) ，但把大问题划分为三个较小问题。
3. 1) 编写一个C++ 程序，实现例1 4 - 2中寻找n 个元素中最大值和最小值的两种方案。使用递归来完成分而治之方案。
2) 程序2 - 2 6和2 - 2 7是另外两个寻找n 个元素中最大值和最小值的代码。试分别计算出每段程序所需要的最少和最大比较次数。
3) 在n 分别等于1 0 0，1 0 0 0或10 000的情况下，比较1）、2）中的程序和程序1 4 - 1的运行时间。对于程序2 - 2 7，使用平均时间和最坏情况下的时间。1）中的程序和程序2 - 2 6应具有相同的平均时间和最坏情况下的时间。
4) 注意到如果比较操作的开销不是很高，分而治之算法在最坏情况下不会比其他算法优越，为什么？它的平均时间优于程序2 - 2 7吗？为什么？
4. 证明直接运用公式（1 4 -2）~（1 4 - 5）得出结果的矩阵乘法的分而治之算法的复杂性为(n3 )。因此相应的分而治之程序将比程序2 - 2 4要慢。
5. 用迭代的方法来证明公式（1 4 - 6）的递归值为(n l og27)。
*6. 编写S t r a s s e n矩阵乘法程序。利用不同的k 值（见公式（1 4 - 6））进行实验，以确定k 为何值时程序性能最佳。比较程序及程序2 - 2 4的运行时间。可取n 为2的幂来进行比较。
7. 当n 不是2的幂时，可以通过增加矩阵的行和列来得到一个大小为2的幂的矩阵。假设使用最少的行数和列数将矩阵扩充为m 阶矩阵，其中m 为2的幂。
1) 求m / n。
2) 可使用哪些矩阵项组成新的行和列，以使新矩阵A' 和B' 相乘时，原来的矩阵A和B相乘的结果会出现在C' 的左上角？
3) 使用S t r a s s e n方法计算A' * B' 所需要的时间为(m2.81 )。给出以n 为变量的运行时间表达式。
2.2 应用
2.2.1 残缺棋盘
残缺棋盘（defective chessboard）是一个有2k×2k 个方格的棋盘，其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k= 0时，仅存在一种可能的残缺棋盘（如图1 4 - 3 a所示）。事实上，对于任意k，恰好存在22k 种不同的残缺棋盘。
残缺棋盘的问题要求用三格板（t r i o m i n o e s）覆盖残缺棋盘（如图1 4 - 4所示）。在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。在这种限制条件下，所需要的三格板总数为( 22k -1 ) / 3。可以验证( 22k -1 ) / 3是一个整数。k 为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。当k= 1时，正好存在3个非残缺的方格，并且这三个方格可用图1 4 - 4中的某一方向的三格板来覆盖。
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k×2k 残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k×2k 棋盘一个很自然的划分方法就是将它划分为如图1 4 - 5 a所示的4个2k - 1×2k - 1 棋盘。注意到当完成这种划分后， 4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的2k×2k 棋盘仅仅有一个残缺方格）。首先覆盖其中包含残缺方格的2k - 1×2k - 1 残缺棋盘，然后把剩下的3个小棋盘转变为残缺棋盘，为此将一个三格板放在由这3个小棋盘形成的角上，如图14-5b 所示，其中原2k×2k 棋盘中的残缺方格落入左上角的2k - 1×2k - 1 棋盘。可以采用这种分割技术递归地覆盖2k×2k 残缺棋盘。当棋盘的大小减为1×1时，递归过程终止。此时1×1的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。
可以将上述分而治之算法编写成一个递归的C++ 函数Ti l e B o a r d (见程序1 4 - 2 )。该函数定义了一个全局的二维整数数组变量B o a r d来表示棋盘。B o a r d [ 0 ] [ 0 ]表示棋盘中左上角的方格。该函数还定义了一个全局整数变量t i l e，其初始值为0。函数的输入参数如下：
• tr 棋盘中左上角方格所在行。
• tc 棋盘中左上角方格所在列。
• dr 残缺方块所在行。
• dl 残缺方块所在列。
• size 棋盘的行数或列数。
Ti l e B o a r d函数的调用格式为Ti l e B o a r d（0,0, dr, dc,size)，其中s i z e = 2k。覆盖残缺棋盘所需要的三格板数目为( s i z e2 -1 ) / 3。函数TileBoard 用整数1到( s i z e2-1 ) / 3来表示这些三格板，并用三格板的标号来标记被该三格板覆盖的非残缺方格。
令t (k) 为函数Ti l e B o a r d覆盖一个2k×2k 残缺棋盘所需要的时间。当k= 0时，s i z e等于1，覆盖它将花费常数时间d。当k > 0时，将进行4次递归的函数调用，这些调用需花费的时间为4t (k-1 )。除了这些时间外， if 条件测试和覆盖3个非残缺方格也需要时间，假设用常数c 表示这些额外时间。可以得到以下递归表达式：
程序14-2 覆盖残缺棋盘
void TileBoard(int tr, int tc, int dr, int dc, int size)
{// 覆盖残缺棋盘
if (size == 1) return;
int t = tile++, // 所使用的三格板的数目
s = size/2; // 象限大小
/ /覆盖左上象限
if (dr < tr + s && dc < tc + s)
// 残缺方格位于本象限
Ti l e B o a r d ( t r, tc, dr, dc, s);
else {// 本象限中没有残缺方格
// 把三格板t 放在右下角
Board[tr + s - 1][tc + s - 1] = t;
// 覆盖其余部分
Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}
/ /覆盖右上象限
if (dr < tr + s && dc >= tc + s)
// 残缺方格位于本象限
Ti l e B o a r d ( t r, tc+s, dr, dc, s);
else {// 本象限中没有残缺方格
// 把三格板t 放在左下角
Board[tr + s - 1][tc + s] = t;
// 覆盖其余部分
Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}
/ /覆盖左下象限
if (dr >= tr + s && dc < tc + s)
// 残缺方格位于本象限
TileBoard(tr+s, tc, dr, dc, s);
else {// 把三格板t 放在右上角
Board[tr + s][tc + s - 1] = t;
// 覆盖其余部分
TileBoard(tr+s, tc, tr+s, tc+s-1, s);}
// 覆盖右下象限
if (dr >= tr + s && dc >= tc + s)
// 残缺方格位于本象限
TileBoard(tr+s, tc+s, dr, dc, s);
else {// 把三格板t 放在左上角
Board[tr + s][tc + s] = t;
// 覆盖其余部分
TileBoard(tr+s, tc+s, tr+s, tc+s, s);}
}
void OutputBoard(int size)
{
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++)
cout << setw (5) << Board[i][j];
cout << endl;
}
}
可以用迭代的方法来计算这个表达式（见例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的数目）。由于必须花费至少( 1 )的时间来放置每一块三格表，因此不可能得到一个比分而治之算法更快的算法。
2.2.2 归并排序
可以运用分而治之方法来解决排序问题，该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法：若n 为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序，然后将排好序的子集合归并为一个集合。
假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中（称为A），最后一个元素放到第二个子集里（称为B）。按照这种方式对A递归地进行排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用程序2 - 1 0中的函数i n s e r t将A和B合并起来。把这种排序算法与I n s e r t i o n S o r t（见程序2 - 1 5）进行比较，可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O (n 2 )。把n 个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了合并排序后的A和B，只需要将B添加到A中即可。假如用函数M a x（见程序1 - 3 1）来找出最大元素，这种排序算法实际上就是S e l e c t i o n S o r t（见程序2 - 7）的递归算法。
假如用冒泡过程（见程序2 - 8）来寻找最大元素并把它移到最右边的位置，这种排序算法就是B u b b l e S o r t（见程序2 - 9）的递归算法。这两种递归排序算法的复杂性均为(n2 )。若一旦发现A已经被排好序就终止对A进行递归分割，则算法的复杂性为O(n2 )（见例2 - 1 6和2 - 1 7）。
上述分割方案将n 个元素分成两个极不平衡的集合A和B。A有n- 1个元素，而B仅含一个元素。下面来看一看采用平衡分割法会发生什么情况： A集合中含有n/k 个元素，B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并（ m e rg e）的过程，将已排好序的A和B合并成一个集合。
例2-5 考虑8个元素，值分别为[ 1 0，4，6，3，8，2，5，7 ]。如果选定k = 2，则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被分别独立地排序。结果分别为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始归并这两个已排序的序列。元素2比3更小，被移到结果序列；3与5进行比较，3被移入结果序列；4与5比较，4被放入结果序列；5和6比较，.。如果选择k= 4，则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序结果分别为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。当这两个排好序的序列被归并后，即可得所需要的排序序列。
图2 - 6给出了分而治之排序算法的伪代码。算法中子集合的数目为2，A中含有n/k个元素。
template<class T>
void sort( T E, int n)
{ / /对E中的n 个元素进行排序， k为全局变量
if (n >= k) {
i = n/k;
j = n-i;
令A 包含E中的前i 个元素
令B 包含E中余下的j 个元素
s o r t ( A , i ) ;
s o r t ( B , j ) ;
m e rge(A,B,E,i,j,); //把A 和B 合并到E
}
else 使用插入排序算法对E 进行排序
}
图14-6 分而治之排序算法的伪代码
从对归并过程的简略描述中，可以明显地看出归并n个元素所需要的时间为O (n)。设t (n)为分而治之排序算法（如图1 4 - 6所示）在最坏情况下所需花费的时间，则有以下递推公式：
其中c 和d 为常数。当n / k≈n-n / k 时，t (n) 的值最小。因此当k= 2时，也就是说，当两个子集合所包含的元素个数近似相等时， t (n) 最小，即当所划分的子集合大小接近时，分而治之算法通常具有最佳性能。
可以用迭代方法来计算这一递推方式，结果为t(n)= (nl o gn)。虽然这个结果是在n为2的幂时得到的，但对于所有的n，这一结果也是有效的，因为t(n) 是n 的非递减函数。t(n) =(nl o gn) 给出了归并排序的最好和最坏情况下的复杂性。由于最好和最坏情况下的复杂性是一样的，因此归并排序的平均复杂性为t (n)= (nl o gn)。
图2 - 6中k= 2的排序方法被称为归并排序（ m e rge sort ），或更精确地说是二路归并排序（two-way merge sort）。下面根据图1 4 - 6中k= 2的情况（归并排序）来编写对n 个元素进行排序的C + +函数。一种最简单的方法就是将元素存储在链表中（即作为类c h a i n的成员（程序3 -8））。在这种情况下，通过移到第n/ 2个节点并打断此链，可将E分成两个大致相等的链表。
归并过程应能将两个已排序的链表归并在一起。如果希望把所得到C + +程序与堆排序和插入排序进行性能比较，那么就不能使用链表来实现归并排序，因为后两种排序方法中都没有使用链表。为了能与前面讨论过的排序函数作比较，归并排序函数必须用一个数组a来存储元素集合E，并在a 中返回排序后的元素序列。为此按照下述过程来对图1 4 - 6的伪代码进行细化：当集合E被化分成两个子集合时，可以不必把两个子集合的元素分别复制到A和B中，只需简单地在集合E中保持两个子集合的左右边界即可。接下来对a 中的初始序列进行排序，并将所得到的排序序列归并到一个新数组b中，最后将它们复制到a 中。图1 4 - 6的改进版见图1 4 - 7。
template<class T>
M e rgeSort( T a[], int left, int right)
{ / /对a [ l e f t : r i g h t ]中的元素进行排序
if (left < right) {//至少两个元素
int i = (left + right)/2; //中心位置
M e rgeSort(a, left, i);
M e rgeSort(a, i+1, right);
M e rge(a, b, left, i, right); //从a 合并到b
Copy(b, a, left, right); //结果放回a
}
}
图14-7 分而治之排序算法的改进
可以从很多方面来改进图1 4 - 7的性能，例如，可以容易地消除递归。如果仔细地检查图1 4 - 7中的程序，就会发现其中的递归只是简单地重复分割元素序列，直到序列的长度变成1为止。当序列的长度变为1时即可进行归并操作，这个过程可以用n 为2的幂来很好地描述。长度为1的序列被归并为长度为2的有序序列；长度为2的序列接着被归并为长度为4的有序序列；这个过程不断地重复直到归并为长度为n 的序列。图1 4 - 8给出n= 8时的归并（和复制）过程，方括号表示一个已排序序列的首和尾。
初始序列[8] [4] [5] [6] [2] [1] [7] [3]
归并到b [4 8] [5 6] [1 2] [3 7]
复制到a [4 8] [5 6] [1 2] [3 7]
归并到b [4 5 6 8] [1 2 3 7]
复制到a [4 5 6 8] [1 2 3 7]
归并到b [1 2 3 4 5 6 7 8]
复制到a [1 2 3 4 5 6 7 8]
图14-8 归并排序的例子
另一种二路归并排序算法是这样的：首先将每两个相邻的大小为1的子序列归并，然后对上一次归并所得到的大小为2的子序列进行相邻归并，如此反复，直至最后归并到一个序列，归并过程完成。通过轮流地将元素从a 归并到b 并从b 归并到a，可以虚拟地消除复制过程。二路归并排序算法见程序1 4 - 3。
程序14-3 二路归并排序
template<class T>
void MergeSort(T a[], int n)
{// 使用归并排序算法对a[0:n-1] 进行排序
T *b = new T [n];
int s = 1; // 段的大小
while (s < n) {
MergePass(a, b, s, n); // 从a归并到b
s += s;
MergePass(b, a, s, n); // 从b 归并到a
s += s;
}
}
为了完成排序代码，首先需要完成函数M e rg e P a s s。函数M e rg e P a s s（见程序1 4 - 4）仅用来确定欲归并子序列的左端和右端，实际的归并工作由函数M e rg e (见程序1 4 - 5 )来完成。函数M e rg e要求针对类型T定义一个操作符< =。如果需要排序的数据类型是用户自定义类型，则必须重载操作符< =。这种设计方法允许我们按元素的任一个域进行排序。重载操作符< =的目的是用来比较需要排序的域。
程序14-4 MergePass函数
template<class T>
void MergePass(T x[], T y[], int s, int n)
{// 归并大小为s的相邻段
int i = 0;
while (i <= n - 2 * s) {
// 归并两个大小为s的相邻段
Merge(x, y, i, i+s-1, i+2*s-1);
i = i + 2 * s;
}
// 剩下不足2个元素
if (i + s < n) Merge(x, y, i, i+s-1, n-1);
else for (int j = i; j <= n-1; j++)
// 把最后一段复制到y
y[j] = x[j];
}
程序14-5 Merge函数
template<class T>
void Merge(T c[], T d[], int l, int m, int r)
{// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] .
int i = l, // 第一段的游标
j = m+1, // 第二段的游标
k = l; // 结果的游标
/ /只要在段中存在i和j，则不断进行归并
while ((i <= m) && (j <= r))
if (c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
// 考虑余下的部分
if (i > m) for (int q = j; q <= r; q++)
d[k++] = c[q];
else for (int q = i; q <= m; q++)
d[k++] = c[q];
}
自然归并排序（natural merge sort）是基本归并排序（见程序1 4 - 3）的一种变化。它首先对输入序列中已经存在的有序子序列进行归并。例如，元素序列[ 4，8，3，7，1，5，6，2 ]中包含有序的子序列[ 4，8 ]，[ 3，7 ]，[ 1，5，6 ]和[ 2 ]，这些子序列是按从左至右的顺序对元素表进行扫描而产生的，若位置i 的元素比位置i+ 1的元素大，则从位置i 进行分割。对于上面这个元素序列，可找到四个子序列，子序列1和子序列2归并可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4归并可得[ 1 , 2 , 5 , 6 ]，最后，归并这两个子序列得到[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，对于上述元素序列，仅仅使用了两趟归并，而程序1 4 - 3从大小为1的子序列开始，需使用三趟归并。作为一个极端的例子，假设输入的元素序列已经排好序并有n个元素，自然归并排序法将准确地识别该序列不必进行归并排序，但程序1 4 - 3仍需要进行[ l o g2 n] 趟归并。因此自然归并排序将在(n) 的时间内完成排序。而程序1 4 - 3将花费(n l o gn) 的时间。
2.2.3 快速排序
分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。
/ /使用快速排序方法对a[ 0 :n- 1 ]排序
从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点
把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点
递归地使用快速排序方法对left 进行排序
递归地使用快速排序方法对right
作者: liuchaohai