分而治之算法
君主和殖民者們所成功運用的分而治之策略也可以運用到高效率的計算機算法的設計過程中。本章將首先介紹怎樣在算法設計領域套用這一古老的策略，然後將利用這一策略解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和一個計算幾何問題——找出二維空間中距離最近的兩個點。
本章給出了用來分析分而治之算法複雜性的數學方法，並通過推導最小最大問題和排序問題的複雜性下限來證明分而治之算法對於求解這兩種問題是最優的（因為算法的複雜性與下限一致）。
算法思想
分而治之方法與軟體設計的模組化方法非常相似。為了解決一個大的問題，可以： 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 和w [ i + 1 ]中的較大者
// 然後將較大者與w [ M a x ]進行比較
// 將較小者與w [ M i n ]進行比較
if (w > w[i+1]) {
if (w > 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 < 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.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[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 <= 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 進行排序
所得結果為l e f t + m i d d l e + r i g h t
圖14-9 快速排序的偽代碼
考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假設選擇元素6作為支點，則6位於m i d d l e；4，3，1，5，2位於l e f t；8，7位於r i g h t。當left 排好序後，所得結果為1，2，3，4，5；當r i g h t排好序後，所得結果為7，8。把right 中的元素放在支點元素之後， l e f t中的元素放在支點元素之前，即可得到最終的結果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。
把元素序列劃分為l e f t、m i d d l e和r i g h t可以就地進行（見程式1 4 - 6）。在程式1 4 - 6中，支點總是取位置1中的元素。也可以採用其他選擇方式來提高排序性能，本章稍後部分將給出這樣一種選擇。
程式14-6 快速排序
template<class T>
void QuickSort(T*a, int n)
{// 對a[0:n-1] 進行快速排序
{// 要求a[n] 必需有最大關鍵值
quickSort(a, 0, n-1);
template<class T>
void quickSort(T a[], int l, int r)
{// 排序a [ l : r ]， a[r+1] 有大值
if (l >= r) return;
int i = l, // 從左至右的游標
j = r + 1; // 從右到左的游標
T pivot = a[l];
// 把左側>= pivot的元素與右側<= pivot 的元素進行交換
while (true) {
do {// 在左側尋找>= pivot 的元素
i = i + 1;
} while (a < pivot);
do {// 在右側尋找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未發現交換對象
Swap(a, a[j]);
}
// 設定p i v o t
a[l] = a[j];
a[j] = pivot;
quickSort(a, l, j-1); // 對左段排序
quickSort(a, j+1, r); // 對右段排序
}
若把程式1 4 - 6中d o - w h i l e條件內的<號和>號分別修改為< =和> =，程式1 4 - 6仍然正確。實驗結果表明使用程式1 4 - 6的快速排序代碼可以得到比較好的平均性能。為了消除程式中的遞歸，必須引入堆疊。不過，消除最後一個遞歸調用不須使用堆疊。消除遞歸調用的工作留作練習（練習1 3）。程式1 4 - 6所需要的遞歸棧空間為O (n)。若使用堆疊來模擬遞歸，則可以把這個空間減少為O ( l o gn)。在模擬過程中，首先對left 和right 中較小者進行排序，把較大者的邊界放入堆疊中。在最壞情況下l e f t總是為空，快速排序所需的計算時間為(n2 )。在最好情況下， l e f t和r i g h t中的元素數目大致相同，快速排序的複雜性為(nl o gn)。令人吃驚的是，快速排序的平均複雜性也是(nl o gn)。
定理2-1 快速排序的平均複雜性為(nl o gn)。
證明用t (n) 代表對含有n 個元素的數組進行排序的平均時間。當n≤1時，t (n)≤d，d為某一常數。當n <1時，用s 表示左段所含元素的個數。由於在中段中有一個支點元素，因此右段中元素的個數為n-s- 1。所以左段和右段的平均排序時間分別為t (s), t (n-s- 1 )。分割數組中元素所需要的時間用cn 表示，其中c 是一個常數。因為s 有同等機會取0 ~n- 1中的任何一個值.
如對（2 - 8）式中的n 使用歸納法，可得到t (n)≤kn l o ge n，其中n> 1且k=2(c+d)，e～2 . 7 1 8為自然對數的基底。在歸納開始時首先驗證n= 2時公式的正確性。根據公式（ 1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在歸納假設部分，假定t(n)≤kn l o ge n（當2≤n＜m 時，m 是任意一個比2大的整數＝.
圖1 4 - 1 0對本書中所討論的算法在平均條件下和最壞條件下的複雜性進行了比較。
方法最壞複雜性平均複雜性
冒泡排序n2 n2
計數排序n2 n2
插入排序n2 n2
選擇排序n2 n2
堆排序nl o gn nl o gn
歸併排序nl o gn nl o gn
快速排序n2 nl o gn
圖14-10 各種排序算法的比較
中值快速排序（ median-of-three quick sort）是程式1 4 - 6的一種變化，這種算法有更好的平均性能。注意到在程式1 4 - 6中總是選擇a [ 1 ]做為支點，而在這種快速排序算法中，可以不必使用a [ 1 ]做為支點，而是取{a[1],a[(1+r)/2],a[r]} 中大小居中的那個元素作為支點。例如，假如有三個元素，大小分別為5，9，7，那么取7為支點。為了實現中值快速排序算法，一種最簡單的方式就是首先選出中值元素並與a[1] 進行交換，然後利用程式1 4 - 6完成排序。如果a [ r ]是被選出的中值元素，那么將a[1] 與a[r] 進行交換，然後將a [ 1 ]（即原來的a [ r ]）賦值給程式1 4 - 6中的變數p i v o t，之後繼續執行程式1 4 - 6中的其餘代碼。
圖2 - 11中分別給出了根據實驗所得到的歸併排序、堆排序、插入排序、快速排序的平均時間。對於每一個不同的n, 都隨機產生了至少1 0 0組整數。隨機整數的產生是通過反覆調用s t d l i b . h庫中的r a n d o m函式來實現的。如果對一組整數進行排序的時間少於1 0個時鐘滴答，則繼續對其他組整數進行排序，直到所用的時間不低於1 0個時鐘滴答。在圖2 - 11中的數據包含產生隨機整數的時間。對於每一個n，在各種排序法中用於產生隨機整數及其他開銷的時間是相同的。因此，圖2 - 11中的數據對於比較各種排序算法是很有用的。
對於足夠大的n，快速排序算法要比其他算法效率更高。從圖中可以看到快速排序曲線與插入排序曲線的交點橫坐標比2 0略小，可通過實驗來確定這個交點橫坐標的精確值。可以分別用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9進行實驗，以尋找精確的交點。令精確的交點橫坐標為nBr e a k。當n≤nBreak 時，插入排序的平均性能最佳。當n＞nBreak 時，快速排序性能最佳。當n＞nBreak 時，把插入排序與快速排序組合為一個排序函式，可以提高快速排序的性能，實現方法是把程式1 4 - 6中的以下語句：
if(l >= r)r e t u r n ;
替換為
if (r-1<nBreak) {InsertionSort(a,l,r); return;}
這裡I n s e r t i o n S o r t ( a , l , r )用來對a [ 1 : r ]進行插入排序。測量修改後的快速排序算法的性能留作練習（練習2 0）。用更小的值替換n B r e a k有可能使性能進一步提高（見練習2 0）。
大多數實驗表明，當n＞c時（c為某一常數），在最壞情況下歸併排序的性能也是最佳的。而當n≤c時，在最壞情況下插入排序的性能最佳。通過將插入排序與歸併排序混合使用，可以提高歸併排序的性能（練習2 1）。
2.2.4 選擇
對於給定的n 個元素的數組a [ 0 : n - 1 ]，要求從中找出第k小的元素。當a [ 0 : n - 1 ]被排序時，該元素就是a [ k - 1 ]。假設n = 8，每個元素有兩個域k e y和I D，其中k e y是一個整數，I D是一個字元。假設這8個元素為[ ( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序後得到數組[ ( 2 ,g)，( 4 ,d)，( 4 ,b)，( 5 ,c)，( 5 ,e)，( 1 0 ,f)，( 1 2 ,a)，( 2 0 ,h) ]。如果k = 1，返回I D為g 的元素；如果k = 8，返回I D為h 的元素；如果k = 6，返回是I D為f 的元素；如果k = 2，返回I D為d 的元素。實際上，對最後一種情況，所得到的結果可能不唯一，因為排序過程中既可能將I D為d 的元素排在a [ 1 ]，也可能將I D為b 的元素排在a [ 1 ]，原因是它們具有相同大小的k e y，因而兩個元素中的任何一個都有可能被返回。但是無論如何，如果一個元素在k = 2時被返回，另一個就必須在k = 3時被返回。
選擇問題的一個套用就是尋找中值元素，此時k = [n / 2 ]。中值是一個很有用的統計量，例如中間工資，中間年齡，中間重量。其他k值也是有用的。例如，通過尋找第n / 4 , n / 2和3 n / 4這三個元素,可將人口劃分為4份。
選擇問題可在O ( n l o g n )時間內解決，方法是首先對這n個元素進行排序（如使用堆排序式或歸併排序），然後取出a [ k - 1 ]中的元素。若使用快速排序（如圖1 4 - 11所示），可以獲得更好的平均性能，儘管該算法有一個比較差的漸近複雜性O( n2 )。
可以通過修寫程式1 4 - 6來解決選擇問題。如果在執行兩個w h i l e循環後支點元素a [ l ]被交換到a [ j ] ,那么a [ l ]是a [ l : j ]中的第j - l + 1個元素。如果要尋找的第k 個元素在a [ l : r ]中，並且j - l + 1等於k，則答案就是a [ l ]；如果j - l + 1 < k，那么尋找的元素是r i g h t中的第k - j + l - 1個元素，否則要尋找的元素是left 中的第k個元素。因此，只需進行0次或1次遞歸調用。新代碼見程式1 4 - 7。S e l e c t中的遞歸調用可用f o r或w h i l e循環來替代（練習2 5）。
程式14-7 尋找第k 個元素
template<class T>
T Select(T a[], int n, int k)
{// 返回a [ 0 : n - 1 ]中第k小的元素
// 假定a[n] 是一個偽最大元素
if (k < 1 || k > n) throw OutOfBounds();
return select(a, 0, n-1, k);
}
template<class T>
T select(T a[], int l, int r, int k)
{// 在a [ l : r ]中選擇第k小的元素
if (l >= r) return a[l];
int i = l, // 從左至右的游標
j = r + 1; // 從右到左的游標
T pivot = a[l];
// 把左側>= pivot的元素與右側<= pivot 的元素進行交換
while (true) {
do {// 在左側尋找>= pivot 的元素
i = i + 1;
} while (a < pivot);
do {// 在右側尋找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未發現交換對象
Swap(a, a[j]);
}
if (j - l + 1 == k) return pivot;
// 設定p i v o t
a[l] = a[j];
a[j] = pivot;
// 對一個段進行遞歸調用
if (j - l + 1 < k)
return select(a, j+1, r, k-j+l-1);
else return select(a, l, j-1, k);
}
程式1 4 - 7在最壞情況下的複雜性是( n2 )，此時left 總是為空，而且第k個元素總是位於r i g h t.
如果假定n 是2的冪，則可以取消公式（2 - 1 0）中的向下取整操作符。通過使用疊代方法，可以得到t (n) = (n)。若仔細地選擇支點元素，則最壞情況下的時間開銷也可以變成(n)。一種選擇支點元素的方法是使用“中間的中間（ m e d i a n - o f - m e d i a n）”規則，該規則首先將數組a中的n 個元素分成n/r 組，r 為某一整常數，除了最後一組外，每組都有r 個元素。然後通過在每組中對r 個元素進行排序來尋找每組中位於中間位置的元素。最後根據所得到的n/r 箇中間元素，遞歸使用選擇算法，求得所需要的支點元素。
例2-6 [中間的中間] 考察如下情形：r=5, n=27, 並且a= [ 2，6，8，1，4，1 0，2 0，6，2 2，11，9，8，4，3，7，8，1 6，11，1 0，8，2，1 4，1 5，1，1 2，5，4 ]。這2 7個元素可以被分為6組
