君主和殖民者們所成功運用的分而治之策略也可以運用到高效率的計算機算法的設計過程中。本章將首先介紹怎樣在算法設計領域應用這一古老的策略，然后將利用這一策略解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和計算一個幾何問題——找出二維空間中距離最近的兩個點。
本章給出了用來分析分而治之算法復雜性的數學方法，并通過推導最小最大問題和排序問題的復雜性下限來證明分而治之算法對于求解這兩種問題是最優的（因為算法的復雜性與下限一致）。
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
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
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
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
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
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
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 進行排序
所得結果為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
void QuickSort(T*a, int n)
{// 對a[0:n-1] 進行快速排序
{// 要求a[n] 必需有最大關鍵值
quickSort(a, 0, n-1);
template
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[i] < pivot);
do {// 在右側尋找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未發現交換對象
Swap(a[i], 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 ]做為支點，而是取 中大小居中的那個元素作為支點。例如，假如有三個元素，大小分別為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
這里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
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
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[i] < pivot);
do {// 在右側尋找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未發現交換對象
Swap(a[i], 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組[ 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 ]，每組的中間元素分別為4 , 11 , 7 , 1 0 , 1 2和4。[ 4 , 11 , 7 , 1 0 , 1 2 , 4 ]的中間元素為7。這個中間元素7被取為支點元素。由此可以得到l e ft= [ 2 , 6 , 1 , 4 , 6 , 4 , 3 , 2 , 1 , 5 , 4 ]，m i d d l e= [ 7 ] ,r i g h t= [ 8 , 1 0 , 2 0 , 2 2 , 11 , 9 , 8 , 8 , 1 6 , 11 , 1 0 , 8 , 1 4 , 1 5 , 1 2 ]。
如果要尋找第k個元素且k< 1 2，則僅僅需要在l e f t中尋找；如果k= 1 2，則要找的元素就是支點元素；如果k> 1 2，則需要檢查r i g h t中的1 5個元素。在最后一種情況下，需在r i g h t中尋找第(k- 1 2 )個元素。
定理2-2 當按“中間的中間”規則選取支點元素時，以下結論為真：
1) 若r=9, 那么當n≥9 0時，有m a x { |l e f e|, |r i g h t| }≤7n / 8。
2) 若r= 5，且a 中所有元素都不同，那么當n≥2 4時，有max{| left |, | right | }≤3n/ 4。
證明這個定理的證明留作練習2 3。
根據定理2 - 2和程序1 4 - 7可知，如果采用“中間的中間”規則并取r= 9，則用于尋找第k個元素的時間t (n)可按如下遞歸公式來計算：
在上述遞歸公式中，假設當n＜9 0時使用復雜性為nl o gn的求解算法，當n≥9 0時，采用“中間的中間”規則進行分而治之求解。利用歸納法可以證明，當n≥1時有t (n)≤7 2cn (練習2 4 )。
當元素互不相同時，可以使用r= 5來得到線性時間性能。
2.2.5 距離最近的點對
給定n 個點（xi，yi）（1≤i≤n），要求找出其中距離最近的兩個點。
例14-7 假設在一片金屬上鉆n 個大小一樣的洞，如果洞太近，金屬可能會斷。若知道任意兩個洞的最小距離，可估計金屬斷裂的概率。這種最小距離問題實際上也就是距離最近的點對問題。
通過檢查所有的n(n- 1 ) / 2對點，并計算每一對點的距離，可以找出距離最近的一對點。這種方法所需要的時間為(n2 )。我們稱這種方法為直接方法。圖1 4 - 1 3中給出了分而治之求解算法的偽代碼。該算法對于小的問題采用直接方法求解，而對于大的問題則首先把它劃分為兩個較小的問題，其中一個問題（稱為A）的大小為「n /2ù，另一個問題（稱為B）的大小為「n /2ù。初始時，最近的點對可能屬于如下三種情形之一： 1) 兩點都在A中（即最近的點對落在A中）；2) 兩點都在B中；3) 一點在A，一點在B。假定根據這三種情況來確定最近點對，則最近點對是所有三種情況中距離最小的一對點。在第一種情況下可對A進行遞歸求解，而在第二種情況下可對B進行遞歸求解。
if (n較小) {用直接法尋找最近點對
R e t u r n ; }
// n較大
將點集分成大致相等的兩個部分A和B
確定A和B中的最近點對
確定一點在A中、另一點在B中的最近點對
從上面得到的三對點中，找出距離最小的一對點
圖14-13 尋找最近的點對
為了確定第三種情況下的最近點對，需要采用一種不同的方法。這種方法取決于點集是如何被劃分成A、B的。一個合理的劃分方法是從xi（中間值）處劃一條垂線，線左邊的點屬于A，線右邊的點屬于B。位于垂線上的點可在A和B之間分配，以便滿足A、B的大小。
例2-8 考察圖14-14a 中從a到n的1 4個點。這些點標繪在圖14-14b 中。中點xi = 1，垂線x = 1如圖14-14b 中的虛線所示。虛線左邊的點(如b, c, h, n, i)屬于A，右邊的點(如a, e, f, j, k, l) 屬于B。d, g, m 落在垂線上，可將其中兩個加入A, 另一個加入B，以便A、B中包含相同的點數。假設d ,m加入A，g加入B。
設是i 的最近點對和B的最近點對中距離較小的一對點。若第三種情況下的最近點對比小。則每一個點距垂線的距離必小于，這樣，就可以淘汰那些距垂線距離≥ 的點。圖1 4 - 1 5中的虛線是分割線。陰影部分以分割線為中線，寬為2 。邊界線及其以外的點均被淘汰掉，只有陰影中的點被保留下來，以便確定是否存在第三類點對（對應于第三種情況）其距離小于。用RA、RB 分別表示A和B中剩下的點。如果存在點對(p,q)，p?A, q?B且p, q 的距離小于，則p?RA，q?RB。可以通過每次檢查RA 中一個點來尋找這樣的點對。假設考察RA 中的p 點，p的y 坐標為p.y，那么只需檢查RB 中滿足p.y- ＜q.y＜p.y+ 的q 點，看是否存在與p 間距小于的點。在圖14-16a 中給出了包含這種q 點的RB 的范圍。因此，只需將RB 中位于×2 陰影內的點逐個與p 配對，以判斷p 是否是距離小于的第三類點。這個×2 區域被稱為是p 的比較區（comparing region）。
例2-9 考察例2 - 8中的1 4個點。A中的最近點對為(b,h)，其距離約為0 . 3 1 6。B中最近點對為(f, j)，其距離為0 . 3，因此= 0 . 3。當考察是否存在第三類點時，除d, g, i, l, m 以外的點均被淘汰，因為它們距分割線x= 1的距離≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m 的比較區中沒有點，只需考察i即可。i 的比較區中僅含點l。計算i 和l的距離，發現它小于，因此(i, l) 是最近的點對。
為了確定一個距離更小的第三類點，RA 中的每個點最多只需和RB 中的6個點比較，如圖1 4 - 1 6所示。
1. 選擇數據結構
為了實現圖1 4 - 1 3的分而治之算法，需要確定什么是“小問題”以及如何表示點。由于集合中少于兩點時不存在最近點對，因此必須保證分解過程不會產生少于兩點的點集。如果將少于四點的點集做為“小問題”，就可以避免產生少于兩點的點集。
每個點可有三個參數：標號， x 坐標，y 坐標。假設標號為整數，每個點可用P o i n t l類（見程序1 4 - 8）來表示。為了便于按x 坐標對各個點排序，可重載操作符＜=。歸并排序程序如1 4 -3所示。
程序14-8 點類
class Point1 {
friend float dist(const Point1&, const Point1&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&,float&);
friend void main();
p u b l i c :
int operator<=(Point1 a) const
{return (x <= a.x);}
p r i v a t e :
int ID; // 點的編號
float x, y; // 點坐標
} ;
class Point2 {
friend float dist(const Point2&, const Point2&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&, float&);
friend void main();
p u b l i c :
int operator<=(Point2 a) const
{return (y <= a.y);}
p r i v a t e :
int p; // 數組X中相同點的索引
float x, y; // 點坐標
} ;
所輸入的n 個點可以用數組X來表示。假設X中的點已按照x 坐標排序，在分割過程中如果當前考察的點是X [l :r]，那么首先計算m= (l+r) / 2，X[ l:m]中的點屬于A，剩下的點屬于B。計算出A和B中的最近點對之后，還需要計算RA 和RB，然后確定是否存在更近的點對，其中一點屬于RA，另一點屬于RB。如果點已按y 坐標排序，那么可以用一種很簡單的方式來測試圖1 4 - 1 6。按y 坐標排序的點保存在另一個使用類P o i n t 2 (見程序14-8) 的數組中。注意到在P o i n t 2類中，為了便于y 坐標排序，已重載了操作符＜＝。成員p 用于指向X中的對應點。
確定了必要的數據結構之后，再來看看所要產生的代碼。首先定義一個模板函數d i s t (見程序1 4 - 9 )來計算點a, b 之間的距離。T可能是P o i n t 1或P o i n t 2，因此d i s t必須是P o i n t 1和P o i n t 2類的友元。
程序14-9 計算兩點距離
template
inline float dist(const T& u, const T& v)
{ / /計算點u 和v之間的距離
float dx = u.x-v. x ;
float dy = u.y-v. y ;
return sqrt(dx * dx + dy * dy);
}
如果點的數目少于兩個，則函數c l o s e s t (見程序1 4 - 1 0 )返回f a l s e，如果成功時函數返回t r u e。當函數成功時，在參數a 和b 中返回距離最近的兩個點，在參數d 中返回距離。代碼首先驗證至少存在兩點，然后使用M e rg e S o r t函數(見程序14-3) 按x 坐標對X中的點排序。接下來把這些點復制到數組Y中并按y 坐標進行排序。排序完成時，對任一個i，有Y [i ] . y≤Y [i+ 1 ] . y，并且Y [i ] .p給出了點i 在X中的位置。上述準備工作做完以后，調用函數close (見程序1 4 - 11 )，該函數實際求解最近點對。
程序14-10 預處理及調用c l o s e
bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)
{// 在n >= 2 個點中尋找最近點對
// 如果少于2個點，則返回f a l s e
// 否則，在a 和b中返回距離最近的兩個點
if (n < 2) return false;
// 按x坐標排序
M e r g e S o r t ( X , n ) ;
// 創建一個按y坐標排序的點數組
Point2 *Y = new Point2 [n];
for (int i = 0; i < n; i++) {
// 將點i 從X 復制到Y
Y[i].p = i;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
M e r g e S o r t ( Y,n); // 按y坐標排序
// 創建臨時數組
Point2 *Z = new Point2 [n];
// 尋找最近點對
c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;
// 刪除數組并返回
delete [] Y;
delete [] Z;
return true;
}
程序1 4 - 11 計算最近點對
void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d)
{//X[l:r] 按x坐標排序
//Y[l:r] 按y坐標排序
if (r-l == 1) {// 兩個點
a = X[l];
b = X[r];
d = dist(X[l], X[r]);
r e t u r n ; }
if (r-l == 2) {// 三個點
// 計算所有點對之間的距離
float d1 = dist(X[l], X[l+1]);
float d2 = dist(X[l+1], X[r]);
float d3 = dist(X[l], X[r]);
// 尋找最近點對
if (d1 <= d2 && d1 <= d3) {
a = X[l];
b = X[l+1];
d = d1;
r e t u r n ; }
if (d2 <= d3) {a = X[l+1];
b = X[r];
d = d2;}
else {a = X[l];
b = X[r];
d = d3;}
r e t u r n ; }
/ /多于三個點，劃分為兩部分
int m = (l+r)/2; // X[l:m] 在A中，余下的在B中
// 在Z[l:m] 和Z [ m + 1 : r ]中創建按y排序的表
int f = l, // Z[l:m]的游標
g = m+1; // Z[m+1:r]的游標
for (int i = l; i <= r; i++)
if (Y[i].p > m) Z[g++] = Y[i];
else Z[f++] = Y[i];
// 對以上兩個部分進行求解
c l o s e ( X , Z , Y, l , m , a , b , d ) ;
float dr;
Point1 ar, br;
c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;
// (a,b) 是兩者中較近的點對
if (dr < d) {a = ar;
b = br;
d = dr;}
M e r g e ( Z , Y,l,m,r);// 重構Y
/ /距離小于d的點放入Z
int k = l; // Z的游標
for (i = l; i <= r; i++)
if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i];
// 通過檢查Z [ l : k - 1 ]中的所有點對，尋找較近的點對
for (i = l; i < k; i++){
for (int j = i+1; j < k && Z[j].y - Z[i].y < d;
j + + ) {
float dp = dist(Z[i], Z[j]);
if (dp < d) {// 較近的點對
d = dp;
a = X[Z[i].p];
b = X[Z[j].p];}
}
}
}
函數c l o s e（見程序1 4 - 11）用來確定X[1:r] 中的最近點對。假定這些點按x 坐標排序。在Y [ 1 : r ]中對這些點按y 坐標排序。Z[ 1 : r ]用來存放中間結果。找到最近點對以后，將在a, b中返回最近點對，在d 中返回距離，數組Y被恢復為輸入狀態。函數并未修改數組X。
首先考察“小問題”，即少于四個點的點集。因為分割過程不會產生少于兩點的數組，因此只需要處理兩點和三點的情形。對于這兩種情形，可以嘗試所有的可能性。當點數超過三個時，通過計算m = ( 1 + r ) / 2把點集分為兩組A和B，X [ 1 : m ]屬于A，X [ m + 1 : r ]屬于B。通過從左至右掃描Y中的點以及確定哪些點屬于A，哪些點屬于B，可以創建分別與A組和B組對應的，按y 坐標排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此時Y和Z的角色互相交換，依次執行兩個遞歸調用來獲取A和B中的最近點對。在兩次遞歸調用返回后，必須保證Z不發生改變，但對Y則無此要求。不過，僅Y [ l : r ]可能會發生改變。通過合并操作（見程序1 4 - 5）可以以Z [ 1 : r ]重構Y [ 1 : r ]。
為實現圖1 4 - 1 6的策略，首先掃描Y [ 1 : r ]，并收集距分割線小于的點，將這些點存放在Z [ 1 : k - 1 ]中。可按如下兩種方式來把RA中點p 與p 的比較區內的所有點進行配對：1) 與RB 中y 坐標≥p.y 的點配對；2) 與y 坐標≤p.y 的點配對。這可以通過將每個點Z [ i ]（1≤i < k，不管該點是在RA
還是在RB中）與Z[j] 配對來實現，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。對每一個Z [ i ]，在2 × 區域內所檢查的點如圖1 4 - 1 7所示。由于在每個2 × 子區域內的點至少相距。因此每一個子區域中的點數不會超過四個，所以與Z [ i ]配對的點Z [ j ]最多有七個。
2. 復雜性分析
令t (n) 代表處理n 個點時，函數close 所需要的時間。當n＜4時，t (n) 等于某個常數d。當n≥4時，需花費(n) 時間來完成以下工作：將點集劃分為兩個部分，兩次遞歸調用后重構Y，淘汰距分割線很遠的點，尋找更好的第三類點對。兩次遞歸調用需分別耗時t (「n /2ù」和t (?n /2?).
這個遞歸式與歸并排序的遞歸式完全一樣，其結果為t (n) = (nl o gn)。另外，函數c l o s e s t還需耗時(nl o gn)來完成如下額外工作：對X進行排序，創建Y和Z，對Y進行排序。因此分而治之最近點對求解算法的時間復雜性為(nl o gn)。