君主和殖民者們所成功運(yùn)用的分而治之策略也可以運(yùn)用到高效率的計(jì)算機(jī)算法的設(shè)計(jì)過程中。本章將首先介紹怎樣在算法設(shè)計(jì)領(lǐng)域應(yīng)用這一古老的策略，然后將利用這一策略解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和計(jì)算一個(gè)幾何問題——找出二維空間中距離最近的兩個(gè)點(diǎn)。
本章給出了用來分析分而治之算法復(fù)雜性的數(shù)學(xué)方法，并通過推導(dǎo)最小最大問題和排序問題的復(fù)雜性下限來證明分而治之算法對(duì)于求解這兩種問題是最優(yōu)的（因?yàn)樗惴ǖ膹?fù)雜性與下限一致）。
2.1 算法思想
分而治之方法與軟件設(shè)計(jì)的模塊化方法非常相似。為了解決一個(gè)大的問題，可以： 1) 把它分成兩個(gè)或多個(gè)更小的問題； 2) 分別解決每個(gè)小問題； 3) 把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。
例2-1 [找出偽幣] 給你一個(gè)裝有1 6個(gè)硬幣的袋子。1 6個(gè)硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。你的任務(wù)是找出這個(gè)偽造的硬幣。為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務(wù)。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個(gè)硬幣輕一些，則尋找偽幣的任務(wù)完成。假如兩硬幣重量相等，則繼續(xù)比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在并找出這一偽幣。
另外一種方法就是利用分而治之方法。假如把1 6硬幣的例子看成一個(gè)大的問題。第一步，把這一問題分成兩個(gè)小問題。隨機(jī)選擇8個(gè)硬幣作為第一組稱為A組，剩下的8個(gè)硬幣作為第二組稱為B組。這樣，就把1 6個(gè)硬幣的問題分成兩個(gè)8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣?？梢岳脙x器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，并且可以判斷它位于較輕的那一組硬幣中。最后，在第三步中，用第二步的結(jié)果得出原先1 6個(gè)硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無論A組還是B組中有偽幣，都可以推斷這1 6個(gè)硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。
現(xiàn)在假設(shè)需要識(shí)別出這一偽幣。把兩個(gè)或三個(gè)硬幣的情況作為不可再分的小問題。注意如果只有一個(gè)硬幣，那么不能判斷出它是否就是偽幣。在一個(gè)小問題中，通過將一個(gè)硬幣分別與其他兩個(gè)硬幣比較，最多比較兩次就可以找到偽幣。這樣，1 6硬幣的問題就被分為兩個(gè)8硬幣（A組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則算法終止。否則，繼續(xù)劃分這兩組硬幣來尋找偽幣。假設(shè)B是輕的那一組，因此再把它分成兩組，每組有4個(gè)硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個(gè)硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個(gè)較輕的組。由于這個(gè)組只有兩個(gè)硬幣，因此不必再細(xì)分。比較組中兩個(gè)硬幣的重量，可以立即知道哪一個(gè)硬幣輕一些。較輕的硬幣就是所要找的偽幣。
例2-2 [金塊問題] 有一個(gè)老板有一袋金塊。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個(gè)月都必須找出最輕和最重的金塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金塊。
假設(shè)袋中有n 個(gè)金塊?？梢杂煤瘮?shù)M a x（程序1 - 3 1）通過n-1次比較找到最重的金塊。找到最重的金塊后，可以從余下的n-1個(gè)金塊中用類似的方法通過n-2次比較找出最輕的金塊。這樣，比較的總次數(shù)為2n-3。程序2 - 2 6和2 - 2 7是另外兩種方法，前者需要進(jìn)行2n-2次比較，后者最多需要進(jìn)行2n-2次比較。
下面用分而治之方法對(duì)這個(gè)問題進(jìn)行求解。當(dāng)n很小時(shí)，比如說， n≤2，識(shí)別出最重和最輕的金塊，一次比較就足夠了。當(dāng)n 較大時(shí)（n＞2），第一步，把這袋金塊平分成兩個(gè)小袋A和B。第二步，分別找出在A和B中最重和最輕的金塊。設(shè)A中最重和最輕的金塊分別為HA 與LA，以此類推，B中最重和最輕的金塊分別為HB 和LB。第三步，通過比較HA 和HB，可以找到所有金塊中最重的；通過比較LA 和LB，可以找到所有金塊中最輕的。在第二步中，若n＞2，則遞歸地應(yīng)用分而治之方法。
假設(shè)n= 8。這個(gè)袋子被平分為各有4個(gè)金塊的兩個(gè)袋子A和B。為了在A中找出最重和最輕的金塊，A中的4個(gè)金塊被分成兩組A1和A2。每一組有兩個(gè)金塊，可以用一次比較在A中找出較重的金塊HA1和較輕的金塊LA1。經(jīng)過另外一次比較，又能找出HA 2和LA 2。現(xiàn)在通過比較HA1和HA2，能找出HA；通過LA 1和LA2的比較找出LA。這樣，通過4次比較可以找到HA 和LA。同樣需要另外4次比較來確定HB 和LB。通過比較HA 和HB（LA 和LB），就能找出所有金塊中最重和最輕的。因此，當(dāng)n= 8時(shí)，這種分而治之的方法需要1 0次比較。如果使用程序1 - 3 1，則需要1 3次比較。如果使用程序2 - 2 6和2 - 2 7，則最多需要1 4次比較。設(shè)c(n)為使用分而治之方法所需要的比較次數(shù)。為了簡便，假設(shè)n是2的冪。當(dāng)n= 2時(shí)，c(n) = 1。對(duì)于較大的n，c(n) = 2c(n/ 2 ) + 2。當(dāng)n是2的冪時(shí)，使用迭代方法（見例2 - 2 0）可知
c(n) = 3n/ 2 - 2。在本例中，使用分而治之方法比逐個(gè)比較的方法少用了2 5％的比較次數(shù)。
例2-3 [矩陣乘法] 兩個(gè)n×n 階的矩陣A與B的乘積是另一個(gè)n×n 階矩陣C，C可表示為假如每一個(gè)C(i, j) 都用此公式計(jì)算，則計(jì)算C所需要的操作次數(shù)為n3 m+n2 (n- 1) a，其中m表示一次乘法，a 表示一次加法或減法。
為了得到兩個(gè)矩陣相乘的分而治之算法，需要： 1) 定義一個(gè)小問題，并指明小問題是如何進(jìn)行乘法運(yùn)算的； 2) 確定如何把一個(gè)大的問題劃分成較小的問題，并指明如何對(duì)這些較小的問題進(jìn)行乘法運(yùn)算； 3) 最后指出如何根據(jù)小問題的結(jié)果得到大問題的結(jié)果。為了使討論簡便，假設(shè)n 是2的冪（也就是說， n是1，2，4，8，1 6，.）。
首先，假設(shè)n= 1時(shí)是一個(gè)小問題，n> 1時(shí)為一個(gè)大問題。后面將根據(jù)需要隨時(shí)修改這個(gè)假設(shè)。對(duì)于1×1階的小矩陣，可以通過將兩矩陣中的兩個(gè)元素直接相乘而得到結(jié)果。
考察一個(gè)n> 1的大問題?？梢詫⑦@樣的矩陣分成4個(gè)n/ 2×n/ 2階的矩陣A1，A2，A3，和A4。當(dāng)n 大于1且n 是2的冪時(shí)，n/ 2也是2的冪。因此較小矩陣也滿足前面對(duì)矩陣大小的假設(shè)。矩陣Bi 和Ci 的定義與此類似.
根據(jù)上述公式，經(jīng)過8次n/ 2×n/ 2階矩陣乘法和4次n/ 2×n/ 2階矩陣的加法，就可以計(jì)算出A與B的乘積。因此，這些公式能幫助我們實(shí)現(xiàn)分而治之算法。在算法的第二步，將遞歸使用分而治之算法把8個(gè)小矩陣再細(xì)分（見程序2 - 1 9）。算法的復(fù)雜性為(n3 )，此復(fù)雜性與程序2 - 2 4直接使用公式（2 - 1）所得到的復(fù)雜性是一樣的。事實(shí)上，由于矩陣分割和再組合所花費(fèi)的額外開銷，使用分而治之算法得出結(jié)果的時(shí)間將比用程序2 - 2 4還要長。
為了得到更快的算法，需要簡化矩陣分割和再組合這兩個(gè)步驟。一種方案是使用S t r a s s e n方法得到7個(gè)小矩陣。這7個(gè)小矩陣為矩陣D, E, ., J，矩陣D到J可以通過7次矩陣乘法， 6次矩陣加法，和4次矩陣減法計(jì)算得出。前述的4個(gè)小矩陣可以由矩陣D到J通過6次矩陣加法和兩次矩陣減法得出.
用上述方案來解決n= 2的矩陣乘法。將某矩陣A和B相乘得結(jié)果C，如下所示：
因?yàn)閚> 1，所以將A、B兩矩陣分別劃分為4個(gè)小矩陣，每個(gè)矩陣為1×1階，僅包含一個(gè)元素。1×1階矩陣的乘法為小問題，因此可以直接進(jìn)行運(yùn)算。利用計(jì)算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
根據(jù)以上結(jié)果可得：
對(duì)于上面這個(gè)2×2的例子，使用分而治之算法需要7次乘法和1 8次加/減法運(yùn)算。而直接使用公式（2 - 1），則需要8次乘法和7次加/減法。要想使分而治之算法更快一些，則一次乘法所花費(fèi)的時(shí)間必須比11次加/減法的時(shí)間要長。
假定S t r a s s e n矩陣分割方案僅用于n≥8的矩陣乘法，而對(duì)于n<8的矩陣乘法則直接利用公式（2 - 1）進(jìn)行計(jì)算。則n= 8時(shí)，8×8矩陣相乘需要7次4×4矩陣乘法和1 8次4×4矩陣加/減法。每次矩陣乘法需花費(fèi)6 4m+ 4 8a次操作，每次矩陣加法或減法需花費(fèi)1 6a次操作。因此總的操作次數(shù)為7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接計(jì)算方法，則需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接計(jì)算方法快，至少要求5 1 2-4 4 8次乘法的開銷比6 2 4-4 4 8次加/減法的開銷大?；蛘哒f一次乘法的開銷應(yīng)該大于近似2 . 7 5次加/減法的開銷。
假定n<1 6的矩陣是一個(gè)“小”問題，S t r a s s e n的分解方案僅僅用于n≥1 6的情況，對(duì)于n<1 6的矩陣相乘，直接利用公式（ 2 - 1）。則當(dāng)n= 1 6時(shí)使用分而治之算法需要7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a次操作。直接計(jì)算時(shí)需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的開銷與一次加/減法的開銷相同，則S t r a s s e n方法需要7 8 7 2次操作及用于問題分解的額外時(shí)間，而直接計(jì)算方法則需要7 9 3 6次操作加上程序中執(zhí)行f o r循環(huán)以及其他語句所花費(fèi)的時(shí)間。即使直接計(jì)算方法所需要的操作次數(shù)比St r a s s e n方法少，但由于直接計(jì)算方法需要更多的額外開銷，因此它也不見得會(huì)比S t r a s s e n方法快。
n 的值越大，Strassen 方法與直接計(jì)算方法所用的操作次數(shù)的差異就越大，因此對(duì)于足夠大的n，Strassen 方法將更快。設(shè)t (n) 表示使用Strassen 分而治之方法所需的時(shí)間。因?yàn)榇蟮木仃嚂?huì)被遞歸地分割成小矩陣直到每個(gè)矩陣的大小小于或等于k（k至少為8，也許更大，具體值由計(jì)算機(jī)的性能決定）. 用迭代方法計(jì)算，可得t(n) = (nl og27 )。因?yàn)閘 og27 ≈2 . 8 1，所以與直接計(jì)算方法的復(fù)雜性(n3 )相比，分而治之矩陣乘法算法有較大的改進(jìn)。
注意事項(xiàng)
分而治之方法很自然地導(dǎo)致了遞歸算法的使用。在許多例子里，這些遞歸算法在遞歸程序中得到了很好的運(yùn)用。實(shí)際上，在許多情況下，所有為了得到一個(gè)非遞歸程序的企圖都會(huì)導(dǎo)致采用一個(gè)模擬遞歸棧。不過在有些情況下，不使用這樣的遞歸棧而采用一個(gè)非遞歸程序來完成分而治之算法也是可能的，并且在這種方式下，程序得到結(jié)果的速度會(huì)比遞歸方式更快。解決金塊問題的分而治之算法（例2 - 2）和歸并排序方法（ 2 . 3節(jié)）就可以不利用遞歸而通過一個(gè)非遞歸程序來更快地完成。
例2-4 [金塊問題] 用例2 - 2的算法尋找8個(gè)金塊中最輕和最重金塊的工作可以用二叉樹來表示。這棵樹的葉子分別表示8個(gè)金塊（a, b,., h)，每個(gè)陰影節(jié)點(diǎn)表示一個(gè)包含其子樹中所有葉子的問題。因此，根節(jié)點(diǎn)A表示尋找8個(gè)金塊中最輕、最重金塊的問題，而節(jié)點(diǎn)B表示找出a,b,c 和d 這4個(gè)金塊中最輕和最重金塊的問題。算法從根節(jié)點(diǎn)開始。由根節(jié)點(diǎn)表示的8金塊問題被劃分成由節(jié)點(diǎn)B和C所表示的兩個(gè)4金塊問題。在B節(jié)點(diǎn)，4金塊問題被劃分成由D和E所表示的2金塊問題?？赏ㄟ^比較金塊a 和b 哪一個(gè)較重來解決D節(jié)點(diǎn)所表示的2金塊問題。在解決了D和E所表示的問題之后，可以通過比較D和E中所找到的輕金塊和重金塊來解決B表示的問題。接著在F，G和C上重復(fù)這一過程，最后解決問題A。
可以將遞歸的分而治之算法劃分成以下的步驟：
1) 從圖2 - 2中的二叉樹由根至葉的過程中把一個(gè)大問題劃分成許多個(gè)小問題，小問題的大小為1或2。
2) 比較每個(gè)大小為2的問題中的金塊，確定哪一個(gè)較重和哪一個(gè)較輕。在節(jié)點(diǎn)D、E、F和G上完成這種比較。大小為1的問題中只有一個(gè)金塊，它既是最輕的金塊也是最重的金塊。
3) 對(duì)較輕的金塊進(jìn)行比較以確定哪一個(gè)金塊最輕，對(duì)較重的金塊進(jìn)行比較以確定哪一個(gè)金塊最重。對(duì)于節(jié)點(diǎn)A到C執(zhí)行這種比較。
根據(jù)上述步驟，可以得出程序1 4 - 1的非遞歸代碼。該程序用于尋找到數(shù)組w [ 0 : n - 1 ]中的最小數(shù)和最大數(shù)，若n < 1，則程序返回f a l s e，否則返回t r u e。
當(dāng)n≥1時(shí)，程序1 4 - 1給M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]為最大的重量。
首先處理n≤1的情況。若n>1且為奇數(shù)，第一個(gè)重量w [ 0 ]將成為最小值和最大值的候選值，因此將有偶數(shù)個(gè)重量值w [ 1 : n - 1 ]參與f o r循環(huán)。當(dāng)n 是偶數(shù)時(shí)，首先將兩個(gè)重量值放在for 循環(huán)外進(jìn)行比較，較小和較大的重量值分別置為Min和Max，因此也有偶數(shù)個(gè)重量值w[2:n-1]參與for循環(huán)。
在for 循環(huán)中，外層if 通過比較確定( w [ i ] , w [ i + 1 ] )中的較大和較小者。此工作與前面提到的分而治之算法步驟中的2) 相對(duì)應(yīng)，而內(nèi)層的i f負(fù)責(zé)找出較小重量值和較大重量值中的最小值和
最大值，這個(gè)工作對(duì)應(yīng)于3 )。for 循環(huán)將每一對(duì)重量值中較小值和較大值分別與當(dāng)前的最小值w [ M i n ]和最大值w [ M a x ]進(jìn)行比較，根據(jù)比較結(jié)果來修改M i n和M a x（如果必要）。
下面進(jìn)行復(fù)雜性分析。注意到當(dāng)n為偶數(shù)時(shí)，在for 循環(huán)外部將執(zhí)行一次比較而在f o r循環(huán)內(nèi)部執(zhí)行3 ( n / 2 - 1 )次比較，比較的總次數(shù)為3 n / 2 - 2。當(dāng)n 為奇數(shù)時(shí)，f o r循環(huán)外部沒有執(zhí)行比較，而內(nèi)部執(zhí)行了3(n-1)/2次比較。因此無論n 為奇數(shù)或偶數(shù)，當(dāng)n>0時(shí)，比較的總次數(shù)為「3n/2ù-2次。
程序14-1 找出最小值和最大值的非遞歸程序
template
bool MinMax(T w[], int n, T& Min, T& Max)
{// 尋找w [ 0 : n - 1 ]中的最小和最大值
// 如果少于一個(gè)元素，則返回f a l s e
// 特殊情形： n <= 1
if (n < 1) return false;
if (n == 1) {Min = Max = 0;
return true;}
/ /對(duì)Min 和M a x進(jìn)行初始化
int s; // 循環(huán)起點(diǎn)
if (n % 2) {// n 為奇數(shù)
Min = Max = 0;
s = 1;}
else {// n為偶數(shù)，比較第一對(duì)
if (w[0] > w[1]) {
Min = 1;
Max = 0;}
else {Min = 0;
Max = 1;}
s = 2;}
// 比較余下的數(shù)對(duì)
for (int i = s; i < n; i += 2) {
// 尋找w[i] 和w [ i + 1 ]中的較大者
// 然后將較大者與w [ M a x ]進(jìn)行比較
// 將較小者與w [ M i n ]進(jì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;
}
練習(xí)
1. 將例1 4 - 1的分而治之算法擴(kuò)充到n> 1個(gè)硬幣的情形。需要進(jìn)行多少次重量的比較？
2. 考慮例1 4 - 1的偽幣問題。假設(shè)把條件“偽幣比真幣輕”改為“偽幣與真幣的重量不同”，同樣假定袋中有n 個(gè)硬幣。
1) 給出相應(yīng)分而治之算法的形式化描述，該算法可輸出信息“不存在偽幣”或找出偽幣。算法應(yīng)遞歸地將大的問題劃分成兩個(gè)較小的問題。需要多少次比較才能找到偽幣（如果存在偽幣）？
2) 重復(fù)1) ，但把大問題劃分為三個(gè)較小問題。
3. 1) 編寫一個(gè)C++ 程序，實(shí)現(xiàn)例1 4 - 2中尋找n 個(gè)元素中最大值和最小值的兩種方案。使用遞歸來完成分而治之方案。
2) 程序2 - 2 6和2 - 2 7是另外兩個(gè)尋找n 個(gè)元素中最大值和最小值的代碼。試分別計(jì)算出每段程序所需要的最少和最大比較次數(shù)。
3) 在n 分別等于1 0 0，1 0 0 0或10 000的情況下，比較1）、2）中的程序和程序1 4 - 1的運(yùn)行時(shí)間。對(duì)于程序2 - 2 7，使用平均時(shí)間和最壞情況下的時(shí)間。1）中的程序和程序2 - 2 6應(yīng)具有相同的平均時(shí)間和最壞情況下的時(shí)間。
4) 注意到如果比較操作的開銷不是很高，分而治之算法在最壞情況下不會(huì)比其他算法優(yōu)越，為什么？它的平均時(shí)間優(yōu)于程序2 - 2 7嗎？為什么？
4. 證明直接運(yùn)用公式（1 4 -2）~（1 4 - 5）得出結(jié)果的矩陣乘法的分而治之算法的復(fù)雜性為(n3 )。因此相應(yīng)的分而治之程序?qū)⒈瘸绦? - 2 4要慢。
5. 用迭代的方法來證明公式（1 4 - 6）的遞歸值為(n l og27)。
*6. 編寫S t r a s s e n矩陣乘法程序。利用不同的k 值（見公式（1 4 - 6））進(jìn)行實(shí)驗(yàn)，以確定k 為何值時(shí)程序性能最佳。比較程序及程序2 - 2 4的運(yùn)行時(shí)間?？扇 為2的冪來進(jìn)行比較。
7. 當(dāng)n 不是2的冪時(shí)，可以通過增加矩陣的行和列來得到一個(gè)大小為2的冪的矩陣。假設(shè)使用最少的行數(shù)和列數(shù)將矩陣擴(kuò)充為m 階矩陣，其中m 為2的冪。
1) 求m / n。
2) 可使用哪些矩陣項(xiàng)組成新的行和列，以使新矩陣A' 和B' 相乘時(shí)，原來的矩陣A和B相乘的結(jié)果會(huì)出現(xiàn)在C' 的左上角？
3) 使用S t r a s s e n方法計(jì)算A' * B' 所需要的時(shí)間為(m2.81 )。給出以n 為變量的運(yùn)行時(shí)間表達(dá)式。
2.2 應(yīng)用
2.2.1 殘缺棋盤
殘缺棋盤（defective chessboard）是一個(gè)有2k×2k 個(gè)方格的棋盤，其中恰有一個(gè)方格殘缺。圖2 - 3給出k≤2時(shí)各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。注意當(dāng)k= 0時(shí)，僅存在一種可能的殘缺棋盤（如圖1 4 - 3 a所示）。事實(shí)上，對(duì)于任意k，恰好存在22k 種不同的殘缺棋盤。
殘缺棋盤的問題要求用三格板（t r i o m i n o e s）覆蓋殘缺棋盤（如圖1 4 - 4所示）。在此覆蓋中，兩個(gè)三格板不能重疊，三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格。在這種限制條件下，所需要的三格板總數(shù)為( 22k -1 ) / 3?？梢则?yàn)證( 22k -1 ) / 3是一個(gè)整數(shù)。k 為0的殘缺棋盤很容易被覆蓋，因?yàn)樗鼪]有非殘缺的方格，用于覆蓋的三格板的數(shù)目為0。當(dāng)k= 1時(shí)，正好存在3個(gè)非殘缺的方格，并且這三個(gè)方格可用圖1 4 - 4中的某一方向的三格板來覆蓋。
用分而治之方法可以很好地解決殘缺棋盤問題。這一方法可將覆蓋2k×2k 殘缺棋盤的問題轉(zhuǎn)化為覆蓋較小殘缺棋盤的問題。2k×2k 棋盤一個(gè)很自然的劃分方法就是將它劃分為如圖1 4 - 5 a所示的4個(gè)2k - 1×2k - 1 棋盤。注意到當(dāng)完成這種劃分后， 4個(gè)小棋盤中僅僅有一個(gè)棋盤存在殘缺方格（因?yàn)樵瓉淼?k×2k 棋盤僅僅有一個(gè)殘缺方格）。首先覆蓋其中包含殘缺方格的2k - 1×2k - 1 殘缺棋盤，然后把剩下的3個(gè)小棋盤轉(zhuǎn)變?yōu)闅埲逼灞P，為此將一個(gè)三格板放在由這3個(gè)小棋盤形成的角上，如圖14-5b 所示，其中原2k×2k 棋盤中的殘缺方格落入左上角的2k - 1×2k - 1 棋盤?？梢圆捎眠@種分割技術(shù)遞歸地覆蓋2k×2k 殘缺棋盤。當(dāng)棋盤的大小減為1×1時(shí)，遞歸過程終止。此時(shí)1×1的棋盤中僅僅包含一個(gè)方格且此方格殘缺，所以無需放置三格板。
可以將上述分而治之算法編寫成一個(gè)遞歸的C++ 函數(shù)Ti l e B o a r d (見程序1 4 - 2 )。該函數(shù)定義了一個(gè)全局的二維整數(shù)數(shù)組變量B o a r d來表示棋盤。B o a r d [ 0 ] [ 0 ]表示棋盤中左上角的方格。該函數(shù)還定義了一個(gè)全局整數(shù)變量t i l e，其初始值為0。函數(shù)的輸入?yún)?shù)如下：
? tr 棋盤中左上角方格所在行。
? tc 棋盤中左上角方格所在列。
? dr 殘缺方塊所在行。
? dl 殘缺方塊所在列。
? size 棋盤的行數(shù)或列數(shù)。
Ti l e B o a r d函數(shù)的調(diào)用格式為Ti l e B o a r d（0,0, dr, dc,size)，其中s i z e = 2k。覆蓋殘缺棋盤所需要的三格板數(shù)目為( s i z e2 -1 ) / 3。函數(shù)TileBoard 用整數(shù)1到( s i z e2-1 ) / 3來表示這些三格板，并用三格板的標(biāo)號(hào)來標(biāo)記被該三格板覆蓋的非殘缺方格。
令t (k) 為函數(shù)Ti l e B o a r d覆蓋一個(gè)2k×2k 殘缺棋盤所需要的時(shí)間。當(dāng)k= 0時(shí)，s i z e等于1，覆蓋它將花費(fèi)常數(shù)時(shí)間d。當(dāng)k > 0時(shí)，將進(jìn)行4次遞歸的函數(shù)調(diào)用，這些調(diào)用需花費(fèi)的時(shí)間為4t (k-1 )。除了這些時(shí)間外， if 條件測試和覆蓋3個(gè)非殘缺方格也需要時(shí)間，假設(shè)用常數(shù)c 表示這些額外時(shí)間。可以得到以下遞歸表達(dá)式：
程序14-2 覆蓋殘缺棋盤
void TileBoard(int tr, int tc, int dr, int dc, int size)
{// 覆蓋殘缺棋盤
if (size == 1) return;
int t = tile++, // 所使用的三格板的數(shù)目
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;
}
}
可以用迭代的方法來計(jì)算這個(gè)表達(dá)式（見例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的數(shù)目）。由于必須花費(fèi)至少( 1 )的時(shí)間來放置每一塊三格表，因此不可能得到一個(gè)比分而治之算法更快的算法。
2.2.2 歸并排序
可以運(yùn)用分而治之方法來解決排序問題，該問題是將n 個(gè)元素排成非遞減順序。分而治之方法通常用以下的步驟來進(jìn)行排序算法：若n 為1，算法終止；否則，將這一元素集合分割成兩個(gè)或更多個(gè)子集合，對(duì)每一個(gè)子集合分別排序，然后將排好序的子集合歸并為一個(gè)集合。
假設(shè)僅將n 個(gè)元素的集合分成兩個(gè)子集合。現(xiàn)在需要確定如何進(jìn)行子集合的劃分。一種可能性就是把前面n- 1個(gè)元素放到第一個(gè)子集中（稱為A），最后一個(gè)元素放到第二個(gè)子集里（稱為B）。按照這種方式對(duì)A遞歸地進(jìn)行排序。由于B僅含一個(gè)元素，所以它已經(jīng)排序完畢，在A排完序后，只需要用程序2 - 1 0中的函數(shù)i n s e r t將A和B合并起來。把這種排序算法與I n s e r t i o n S o r t（見程序2 - 1 5）進(jìn)行比較，可以發(fā)現(xiàn)這種排序算法實(shí)際上就是插入排序的遞歸算法。該算法的復(fù)雜性為O (n 2 )。把n 個(gè)元素劃分成兩個(gè)子集合的另一種方法是將含有最大值的元素放入B，剩下的放入A中。然后A被遞歸排序。為了合并排序后的A和B，只需要將B添加到A中即可。假如用函數(shù)M a x（見程序1 - 3 1）來找出最大元素，這種排序算法實(shí)際上就是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）的遞歸算法。這兩種遞歸排序算法的復(fù)雜性均為(n2 )。若一旦發(fā)現(xiàn)A已經(jīng)被排好序就終止對(duì)A進(jìn)行遞歸分割，則算法的復(fù)雜性為O(n2 )（見例2 - 1 6和2 - 1 7）。
上述分割方案將n 個(gè)元素分成兩個(gè)極不平衡的集合A和B。A有n- 1個(gè)元素，而B僅含一個(gè)元素。下面來看一看采用平衡分割法會(huì)發(fā)生什么情況： A集合中含有n/k 個(gè)元素，B中包含其余的元素。遞歸地使用分而治之方法對(duì)A和B進(jìn)行排序。然后采用一個(gè)被稱之為歸并（ m e rg e）的過程，將已排好序的A和B合并成一個(gè)集合。
例2-5 考慮8個(gè)元素，值分別為[ 1 0，4，6，3，8，2，5，7 ]。如果選定k = 2，則[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]將被分別獨(dú)立地排序。結(jié)果分別為[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。從兩個(gè)序列的頭部開始?xì)w并這兩個(gè)已排序的序列。元素2比3更小，被移到結(jié)果序列；3與5進(jìn)行比較，3被移入結(jié)果序列；4與5比較，4被放入結(jié)果序列；5和6比較，.。如果選擇k= 4，則序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]將被排序。排序結(jié)果分別為[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。當(dāng)這兩個(gè)排好序的序列被歸并后，即可得所需要的排序序列。
圖2 - 6給出了分而治之排序算法的偽代碼。算法中子集合的數(shù)目為2，A中含有n/k個(gè)元素。
template
void sort( T E, int n)
{ / /對(duì)E中的n 個(gè)元素進(jìn)行排序， k為全局變量
if (n >= k) {
i = n/k;
j = n-i;
令A(yù) 包含E中的前i 個(gè)元素
令B 包含E中余下的j 個(gè)元素
s o r t ( A , i ) ;
s o r t ( B , j ) ;
m e rge(A,B,E,i,j,); //把A 和B 合并到E
}
else 使用插入排序算法對(duì)E 進(jìn)行排序
}
圖14-6 分而治之排序算法的偽代碼
從對(duì)歸并過程的簡略描述中，可以明顯地看出歸并n個(gè)元素所需要的時(shí)間為O (n)。設(shè)t (n)為分而治之排序算法（如圖1 4 - 6所示）在最壞情況下所需花費(fèi)的時(shí)間，則有以下遞推公式：
其中c 和d 為常數(shù)。當(dāng)n / k≈n-n / k 時(shí)，t (n) 的值最小。因此當(dāng)k= 2時(shí)，也就是說，當(dāng)兩個(gè)子集合所包含的元素個(gè)數(shù)近似相等時(shí)， t (n) 最小，即當(dāng)所劃分的子集合大小接近時(shí)，分而治之算法通常具有最佳性能。
可以用迭代方法來計(jì)算這一遞推方式，結(jié)果為t(n)= (nl o gn)。雖然這個(gè)結(jié)果是在n為2的冪時(shí)得到的，但對(duì)于所有的n，這一結(jié)果也是有效的，因?yàn)閠(n) 是n 的非遞減函數(shù)。t(n) =(nl o gn) 給出了歸并排序的最好和最壞情況下的復(fù)雜性。由于最好和最壞情況下的復(fù)雜性是一樣的，因此歸并排序的平均復(fù)雜性為t (n)= (nl o gn)。
圖2 - 6中k= 2的排序方法被稱為歸并排序（ m e rge sort ），或更精確地說是二路歸并排序（two-way merge sort）。下面根據(jù)圖1 4 - 6中k= 2的情況（歸并排序）來編寫對(duì)n 個(gè)元素進(jìn)行排序的C + +函數(shù)。一種最簡單的方法就是將元素存儲(chǔ)在鏈表中（即作為類c h a i n的成員（程序3 -8））。在這種情況下，通過移到第n/ 2個(gè)節(jié)點(diǎn)并打斷此鏈，可將E分成兩個(gè)大致相等的鏈表。
歸并過程應(yīng)能將兩個(gè)已排序的鏈表歸并在一起。如果希望把所得到C + +程序與堆排序和插入排序進(jìn)行性能比較，那么就不能使用鏈表來實(shí)現(xiàn)歸并排序，因?yàn)楹髢煞N排序方法中都沒有使用鏈表。為了能與前面討論過的排序函數(shù)作比較，歸并排序函數(shù)必須用一個(gè)數(shù)組a來存儲(chǔ)元素集合E，并在a 中返回排序后的元素序列。為此按照下述過程來對(duì)圖1 4 - 6的偽代碼進(jìn)行細(xì)化：當(dāng)集合E被化分成兩個(gè)子集合時(shí)，可以不必把兩個(gè)子集合的元素分別復(fù)制到A和B中，只需簡單地在集合E中保持兩個(gè)子集合的左右邊界即可。接下來對(duì)a 中的初始序列進(jìn)行排序，并將所得到的排序序列歸并到一個(gè)新數(shù)組b中，最后將它們復(fù)制到a 中。圖1 4 - 6的改進(jìn)版見圖1 4 - 7。
template
M e rgeSort( T a[], int left, int right)
{ / /對(duì)a [ l e f t : r i g h t ]中的元素進(jìn)行排序
if (left < right) {//至少兩個(gè)元素
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); //結(jié)果放回a
}
}
圖14-7 分而治之排序算法的改進(jìn)
可以從很多方面來改進(jìn)圖1 4 - 7的性能，例如，可以容易地消除遞歸。如果仔細(xì)地檢查圖1 4 - 7中的程序，就會(huì)發(fā)現(xiàn)其中的遞歸只是簡單地重復(fù)分割元素序列，直到序列的長度變成1為止。當(dāng)序列的長度變?yōu)?時(shí)即可進(jìn)行歸并操作，這個(gè)過程可以用n 為2的冪來很好地描述。長度為1的序列被歸并為長度為2的有序序列；長度為2的序列接著被歸并為長度為4的有序序列；這個(gè)過程不斷地重復(fù)直到歸并為長度為n 的序列。圖1 4 - 8給出n= 8時(shí)的歸并（和復(fù)制）過程，方括號(hào)表示一個(gè)已排序序列的首和尾。
初始序列[8] [4] [5] [6] [2] [1] [7] [3]
歸并到b [4 8] [5 6] [1 2] [3 7]
復(fù)制到a [4 8] [5 6] [1 2] [3 7]
歸并到b [4 5 6 8] [1 2 3 7]
復(fù)制到a [4 5 6 8] [1 2 3 7]
歸并到b [1 2 3 4 5 6 7 8]
復(fù)制到a [1 2 3 4 5 6 7 8]
圖14-8 歸并排序的例子
另一種二路歸并排序算法是這樣的：首先將每兩個(gè)相鄰的大小為1的子序列歸并，然后對(duì)上一次歸并所得到的大小為2的子序列進(jìn)行相鄰歸并，如此反復(fù)，直至最后歸并到一個(gè)序列，歸并過程完成。通過輪流地將元素從a 歸并到b 并從b 歸并到a，可以虛擬地消除復(fù)制過程。二路歸并排序算法見程序1 4 - 3。
程序14-3 二路歸并排序
template
void MergeSort(T a[], int n)
{// 使用歸并排序算法對(duì)a[0:n-1] 進(jìn)行排序
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;
}
}
為了完成排序代碼，首先需要完成函數(shù)M e rg e P a s s。函數(shù)M e rg e P a s s（見程序1 4 - 4）僅用來確定欲歸并子序列的左端和右端，實(shí)際的歸并工作由函數(shù)M e rg e (見程序1 4 - 5 )來完成。函數(shù)M e rg e要求針對(duì)類型T定義一個(gè)操作符< =。如果需要排序的數(shù)據(jù)類型是用戶自定義類型，則必須重載操作符< =。這種設(shè)計(jì)方法允許我們按元素的任一個(gè)域進(jìn)行排序。重載操作符< =的目的是用來比較需要排序的域。
程序14-4 MergePass函數(shù)
template
void MergePass(T x[], T y[], int s, int n)
{// 歸并大小為s的相鄰段
int i = 0;
while (i <= n - 2 * s) {
// 歸并兩個(gè)大小為s的相鄰段
Merge(x, y, i, i+s-1, i+2*s-1);
i = i + 2 * s;
}
// 剩下不足2個(gè)元素
if (i + s < n) Merge(x, y, i, i+s-1, n-1);
else for (int j = i; j <= n-1; j++)
// 把最后一段復(fù)制到y(tǒng)
y[j] = x[j];
}
程序14-5 Merge函數(shù)
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, // 第一段的游標(biāo)
j = m+1, // 第二段的游標(biāo)
k = l; // 結(jié)果的游標(biāo)
/ /只要在段中存在i和j，則不斷進(jìn)行歸并
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）的一種變化。它首先對(duì)輸入序列中已經(jīng)存在的有序子序列進(jìn)行歸并。例如，元素序列[ 4，8，3，7，1，5，6，2 ]中包含有序的子序列[ 4，8 ]，[ 3，7 ]，[ 1，5，6 ]和[ 2 ]，這些子序列是按從左至右的順序?qū)υ乇磉M(jìn)行掃描而產(chǎn)生的，若位置i 的元素比位置i+ 1的元素大，則從位置i 進(jìn)行分割。對(duì)于上面這個(gè)元素序列，可找到四個(gè)子序列，子序列1和子序列2歸并可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4歸并可得[ 1 , 2 , 5 , 6 ]，最后，歸并這兩個(gè)子序列得到[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，對(duì)于上述元素序列，僅僅使用了兩趟歸并，而程序1 4 - 3從大小為1的子序列開始，需使用三趟歸并。作為一個(gè)極端的例子，假設(shè)輸入的元素序列已經(jīng)排好序并有n個(gè)元素，自然歸并排序法將準(zhǔn)確地識(shí)別該序列不必進(jìn)行歸并排序，但程序1 4 - 3仍需要進(jìn)行[ l o g2 n] 趟歸并。因此自然歸并排序?qū)⒃?n) 的時(shí)間內(nèi)完成排序。而程序1 4 - 3將花費(fèi)(n l o gn) 的時(shí)間。
2.2.3 快速排序
分而治之方法還可以用于實(shí)現(xiàn)另一種完全不同的排序方法，這種排序法稱為快速排序（quick sort）。在這種方法中， n 個(gè)元素被分成三段（組）：左段l e f t，右段r i g h t和中段m i d d l e。中段僅包含一個(gè)元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以獨(dú)立排序，并且不必對(duì)l e f t和r i g h t的排序結(jié)果進(jìn)行合并。m i d d l e中的元素被稱為支點(diǎn)( p i v o t )。圖1 4 - 9中給出了快速排序的偽代碼。
/ /使用快速排序方法對(duì)a[ 0 :n- 1 ]排序
從a[ 0 :n- 1 ]中選擇一個(gè)元素作為m i d d l e，該元素為支點(diǎn)
把余下的元素分割為兩段left 和r i g h t，使得l e f t中的元素都小于等于支點(diǎn)，而right 中的元素都大于等于支點(diǎn)
遞歸地使用快速排序方法對(duì)left 進(jìn)行排序
遞歸地使用快速排序方法對(duì)right 進(jìn)行排序
所得結(jié)果為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 ]。假設(shè)選擇元素6作為支點(diǎn)，則6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。當(dāng)left 排好序后，所得結(jié)果為1，2，3，4，5；當(dāng)r i g h t排好序后，所得結(jié)果為7，8。把right 中的元素放在支點(diǎn)元素之后， l e f t中的元素放在支點(diǎn)元素之前，即可得到最終的結(jié)果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。
把元素序列劃分為l e f t、m i d d l e和r i g h t可以就地進(jìn)行（見程序1 4 - 6）。在程序1 4 - 6中，支點(diǎn)總是取位置1中的元素。也可以采用其他選擇方式來提高排序性能，本章稍后部分將給出這樣一種選擇。
程序14-6 快速排序
template
void QuickSort(T*a, int n)
{// 對(duì)a[0:n-1] 進(jìn)行快速排序
{// 要求a[n] 必需有最大關(guā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, // 從左至右的游標(biāo)
j = r + 1; // 從右到左的游標(biāo)
T pivot = a[l];
// 把左側(cè)>= pivot的元素與右側(cè)<= pivot 的元素進(jìn)行交換
while (true) {
do {// 在左側(cè)尋找>= pivot 的元素
i = i + 1;
} while (a[i] < pivot);
do {// 在右側(cè)尋找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未發(fā)現(xiàn)交換對(duì)象
Swap(a[i], a[j]);
}
// 設(shè)置p i v o t
a[l] = a[j];
a[j] = pivot;
quickSort(a, l, j-1); // 對(duì)左段排序
quickSort(a, j+1, r); // 對(duì)右段排序
}
若把程序1 4 - 6中d o - w h i l e條件內(nèi)的<號(hào)和>號(hào)分別修改為< =和> =，程序1 4 - 6仍然正確。實(shí)驗(yàn)結(jié)果表明使用程序1 4 - 6的快速排序代碼可以得到比較好的平均性能。為了消除程序中的遞歸，必須引入堆棧。不過，消除最后一個(gè)遞歸調(diào)用不須使用堆棧。消除遞歸調(diào)用的工作留作練習(xí)（練習(xí)1 3）。程序1 4 - 6所需要的遞歸棧空間為O (n)。若使用堆棧來模擬遞歸，則可以把這個(gè)空間減少為O ( l o gn)。在模擬過程中，首先對(duì)left 和right 中較小者進(jìn)行排序，把較大者的邊界放入堆棧中。在最壞情況下l e f t總是為空，快速排序所需的計(jì)算時(shí)間為(n2 )。在最好情況下， l e f t和r i g h t中的元素?cái)?shù)目大致相同，快速排序的復(fù)雜性為(nl o gn)。令人吃驚的是，快速排序的平均復(fù)雜性也是(nl o gn)。
定理2-1 快速排序的平均復(fù)雜性為(nl o gn)。
證明用t (n) 代表對(duì)含有n 個(gè)元素的數(shù)組進(jìn)行排序的平均時(shí)間。當(dāng)n≤1時(shí)，t (n)≤d，d為某一常數(shù)。當(dāng)n <1時(shí)，用s 表示左段所含元素的個(gè)數(shù)。由于在中段中有一個(gè)支點(diǎn)元素，因此右段中元素的個(gè)數(shù)為n-s- 1。所以左段和右段的平均排序時(shí)間分別為t (s), t (n-s- 1 )。分割數(shù)組中元素所需要的時(shí)間用cn 表示，其中c 是一個(gè)常數(shù)。因?yàn)閟 有同等機(jī)會(huì)取0 ~n- 1中的任何一個(gè)值.
如對(duì)（2 - 8）式中的n 使用歸納法，可得到t (n)≤kn l o ge n，其中n> 1且k=2(c+d)，e～2 . 7 1 8為自然對(duì)數(shù)的基底。在歸納開始時(shí)首先驗(yàn)證n= 2時(shí)公式的正確性。根據(jù)公式（ 1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在歸納假設(shè)部分，假定t(n)≤kn l o ge n（當(dāng)2≤n＜m 時(shí)，m 是任意一個(gè)比2大的整數(shù)＝.
圖1 4 - 1 0對(duì)本書中所討論的算法在平均條件下和最壞條件下的復(fù)雜性進(jìn)行了比較。
方法最壞復(fù)雜性平均復(fù)雜性
冒泡排序n2 n2
計(jì)數(shù)排序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 ]做為支點(diǎn)，而在這種快速排序算法中，可以不必使用a [ 1 ]做為支點(diǎn)，而是取 中大小居中的那個(gè)元素作為支點(diǎn)。例如，假如有三個(gè)元素，大小分別為5，9，7，那么取7為支點(diǎn)。為了實(shí)現(xiàn)中值快速排序算法，一種最簡單的方式就是首先選出中值元素并與a[1] 進(jìn)行交換，然后利用程序1 4 - 6完成排序。如果a [ r ]是被選出的中值元素，那么將a[1] 與a[r] 進(jìn)行交換，然后將a [ 1 ]（即原來的a [ r ]）賦值給程序1 4 - 6中的變量p i v o t，之后繼續(xù)執(zhí)行程序1 4 - 6中的其余代碼。
圖2 - 11中分別給出了根據(jù)實(shí)驗(yàn)所得到的歸并排序、堆排序、插入排序、快速排序的平均時(shí)間。對(duì)于每一個(gè)不同的n, 都隨機(jī)產(chǎn)生了至少1 0 0組整數(shù)。隨機(jī)整數(shù)的產(chǎn)生是通過反復(fù)調(diào)用s t d l i b . h庫中的r a n d o m函數(shù)來實(shí)現(xiàn)的。如果對(duì)一組整數(shù)進(jìn)行排序的時(shí)間少于1 0個(gè)時(shí)鐘滴答，則繼續(xù)對(duì)其他組整數(shù)進(jìn)行排序，直到所用的時(shí)間不低于1 0個(gè)時(shí)鐘滴答。在圖2 - 11中的數(shù)據(jù)包含產(chǎn)生隨機(jī)整數(shù)的時(shí)間。對(duì)于每一個(gè)n，在各種排序法中用于產(chǎn)生隨機(jī)整數(shù)及其他開銷的時(shí)間是相同的。因此，圖2 - 11中的數(shù)據(jù)對(duì)于比較各種排序算法是很有用的。
對(duì)于足夠大的n，快速排序算法要比其他算法效率更高。從圖中可以看到快速排序曲線與插入排序曲線的交點(diǎn)橫坐標(biāo)比2 0略小，可通過實(shí)驗(yàn)來確定這個(gè)交點(diǎn)橫坐標(biāo)的精確值?？梢苑謩e用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9進(jìn)行實(shí)驗(yàn)，以尋找精確的交點(diǎn)。令精確的交點(diǎn)橫坐標(biāo)為nBr e a k。當(dāng)n≤nBreak 時(shí)，插入排序的平均性能最佳。當(dāng)n＞nBreak 時(shí)，快速排序性能最佳。當(dāng)n＞nBreak 時(shí)，把插入排序與快速排序組合為一個(gè)排序函數(shù)，可以提高快速排序的性能，實(shí)現(xiàn)方法是把程序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 )用來對(duì)a [ 1 : r ]進(jìn)行插入排序。測量修改后的快速排序算法的性能留作練習(xí)（練習(xí)2 0）。用更小的值替換n B r e a k有可能使性能進(jìn)一步提高（見練習(xí)2 0）。
大多數(shù)實(shí)驗(yàn)表明，當(dāng)n＞c時(shí)（c為某一常數(shù)），在最壞情況下歸并排序的性能也是最佳的。而當(dāng)n≤c時(shí)，在最壞情況下插入排序的性能最佳。通過將插入排序與歸并排序混合使用，可以提高歸并排序的性能（練習(xí)2 1）。
2.2.4 選擇
對(duì)于給定的n 個(gè)元素的數(shù)組a [ 0 : n - 1 ]，要求從中找出第k小的元素。當(dāng)a [ 0 : n - 1 ]被排序時(shí)，該元素就是a [ k - 1 ]。假設(shè)n = 8，每個(gè)元素有兩個(gè)域k e y和I D，其中k e y是一個(gè)整數(shù)，I D是一個(gè)字符。假設(shè)這8個(gè)元素為[ ( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序后得到數(shù)組[ ( 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 的元素。實(shí)際上，對(duì)最后一種情況，所得到的結(jié)果可能不唯一，因?yàn)榕判蜻^程中既可能將I D為d 的元素排在a [ 1 ]，也可能將I D為b 的元素排在a [ 1 ]，原因是它們具有相同大小的k e y，因而兩個(gè)元素中的任何一個(gè)都有可能被返回。但是無論如何，如果一個(gè)元素在k = 2時(shí)被返回，另一個(gè)就必須在k = 3時(shí)被返回。
選擇問題的一個(gè)應(yīng)用就是尋找中值元素，此時(shí)k = [n / 2 ]。中值是一個(gè)很有用的統(tǒng)計(jì)量，例如中間工資，中間年齡，中間重量。其他k值也是有用的。例如，通過尋找第n / 4 , n / 2和3 n / 4這三個(gè)元素,可將人口劃分為4份。
選擇問題可在O ( n l o g n )時(shí)間內(nèi)解決，方法是首先對(duì)這n個(gè)元素進(jìn)行排序（如使用堆排序式或歸并排序），然后取出a [ k - 1 ]中的元素。若使用快速排序（如圖1 4 - 11所示），可以獲得更好的平均性能，盡管該算法有一個(gè)比較差的漸近復(fù)雜性O(shè)( n2 )。
可以通過修寫程序1 4 - 6來解決選擇問題。如果在執(zhí)行兩個(gè)w h i l e循環(huán)后支點(diǎn)元素a [ l ]被交換到a [ j ] ,那么a [ l ]是a [ l : j ]中的第j - l + 1個(gè)元素。如果要尋找的第k 個(gè)元素在a [ l : r ]中，并且j - l + 1等于k，則答案就是a [ l ]；如果j - l + 1 < k，那么尋找的元素是r i g h t中的第k - j + l - 1個(gè)元素，否則要尋找的元素是left 中的第k個(gè)元素。因此，只需進(jìn)行0次或1次遞歸調(diào)用。新代碼見程序1 4 - 7。S e l e c t中的遞歸調(diào)用可用f o r或w h i l e循環(huán)來替代（練習(xí)2 5）。
程序14-7 尋找第k 個(gè)元素
template
T Select(T a[], int n, int k)
{// 返回a [ 0 : n - 1 ]中第k小的元素
// 假定a[n] 是一個(gè)偽最大元素
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, // 從左至右的游標(biāo)
j = r + 1; // 從右到左的游標(biāo)
T pivot = a[l];
// 把左側(cè)>= pivot的元素與右側(cè)<= pivot 的元素進(jìn)行交換
while (true) {
do {// 在左側(cè)尋找>= pivot 的元素
i = i + 1;
} while (a[i] < pivot);
do {// 在右側(cè)尋找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未發(fā)現(xiàn)交換對(duì)象
Swap(a[i], a[j]);
}
if (j - l + 1 == k) return pivot;
// 設(shè)置p i v o t
a[l] = a[j];
a[j] = pivot;
// 對(duì)一個(gè)段進(jìn)行遞歸調(diào)用
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在最壞情況下的復(fù)雜性是( n2 )，此時(shí)left 總是為空，而且第k個(gè)元素總是位于r i g h t.
如果假定n 是2的冪，則可以取消公式（2 - 1 0）中的向下取整操作符。通過使用迭代方法，可以得到t (n) = (n)。若仔細(xì)地選擇支點(diǎn)元素，則最壞情況下的時(shí)間開銷也可以變成(n)。一種選擇支點(diǎn)元素的方法是使用“中間的中間（ m e d i a n - o f - m e d i a n）”規(guī)則，該規(guī)則首先將數(shù)組a中的n 個(gè)元素分成n/r 組，r 為某一整常數(shù)，除了最后一組外，每組都有r 個(gè)元素。然后通過在每組中對(duì)r 個(gè)元素進(jìn)行排序來尋找每組中位于中間位置的元素。最后根據(jù)所得到的n/r 個(gè)中間元素，遞歸使用選擇算法，求得所需要的支點(diǎn)元素。
例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個(gè)元素可以被分為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。這個(gè)中間元素7被取為支點(diǎn)元素。由此可以得到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個(gè)元素且k< 1 2，則僅僅需要在l e f t中尋找；如果k= 1 2，則要找的元素就是支點(diǎn)元素；如果k> 1 2，則需要檢查r i g h t中的1 5個(gè)元素。在最后一種情況下，需在r i g h t中尋找第(k- 1 2 )個(gè)元素。
定理2-2 當(dāng)按“中間的中間”規(guī)則選取支點(diǎn)元素時(shí)，以下結(jié)論為真：
1) 若r=9, 那么當(dāng)n≥9 0時(shí)，有m a x { |l e f e|, |r i g h t| }≤7n / 8。
2) 若r= 5，且a 中所有元素都不同，那么當(dāng)n≥2 4時(shí)，有max{| left |, | right | }≤3n/ 4。
證明這個(gè)定理的證明留作練習(xí)2 3。
根據(jù)定理2 - 2和程序1 4 - 7可知，如果采用“中間的中間”規(guī)則并取r= 9，則用于尋找第k個(gè)元素的時(shí)間t (n)可按如下遞歸公式來計(jì)算：
在上述遞歸公式中，假設(shè)當(dāng)n＜9 0時(shí)使用復(fù)雜性為nl o gn的求解算法，當(dāng)n≥9 0時(shí)，采用“中間的中間”規(guī)則進(jìn)行分而治之求解。利用歸納法可以證明，當(dāng)n≥1時(shí)有t (n)≤7 2cn (練習(xí)2 4 )。
當(dāng)元素互不相同時(shí)，可以使用r= 5來得到線性時(shí)間性能。
2.2.5 距離最近的點(diǎn)對(duì)
給定n 個(gè)點(diǎn)（xi，yi）（1≤i≤n），要求找出其中距離最近的兩個(gè)點(diǎn)。
例14-7 假設(shè)在一片金屬上鉆n 個(gè)大小一樣的洞，如果洞太近，金屬可能會(huì)斷。若知道任意兩個(gè)洞的最小距離，可估計(jì)金屬斷裂的概率。這種最小距離問題實(shí)際上也就是距離最近的點(diǎn)對(duì)問題。
通過檢查所有的n(n- 1 ) / 2對(duì)點(diǎn)，并計(jì)算每一對(duì)點(diǎn)的距離，可以找出距離最近的一對(duì)點(diǎn)。這種方法所需要的時(shí)間為(n2 )。我們稱這種方法為直接方法。圖1 4 - 1 3中給出了分而治之求解算法的偽代碼。該算法對(duì)于小的問題采用直接方法求解，而對(duì)于大的問題則首先把它劃分為兩個(gè)較小的問題，其中一個(gè)問題（稱為A）的大小為「n /2ù，另一個(gè)問題（稱為B）的大小為「n /2ù。初始時(shí)，最近的點(diǎn)對(duì)可能屬于如下三種情形之一： 1) 兩點(diǎn)都在A中（即最近的點(diǎn)對(duì)落在A中）；2) 兩點(diǎn)都在B中；3) 一點(diǎn)在A，一點(diǎn)在B。假定根據(jù)這三種情況來確定最近點(diǎn)對(duì)，則最近點(diǎn)對(duì)是所有三種情況中距離最小的一對(duì)點(diǎn)。在第一種情況下可對(duì)A進(jìn)行遞歸求解，而在第二種情況下可對(duì)B進(jìn)行遞歸求解。
if (n較小) {用直接法尋找最近點(diǎn)對(duì)
R e t u r n ; }
// n較大
將點(diǎn)集分成大致相等的兩個(gè)部分A和B
確定A和B中的最近點(diǎn)對(duì)
確定一點(diǎn)在A中、另一點(diǎn)在B中的最近點(diǎn)對(duì)
從上面得到的三對(duì)點(diǎn)中，找出距離最小的一對(duì)點(diǎn)
圖14-13 尋找最近的點(diǎn)對(duì)
為了確定第三種情況下的最近點(diǎn)對(duì)，需要采用一種不同的方法。這種方法取決于點(diǎn)集是如何被劃分成A、B的。一個(gè)合理的劃分方法是從xi（中間值）處劃一條垂線，線左邊的點(diǎn)屬于A，線右邊的點(diǎn)屬于B。位于垂線上的點(diǎn)可在A和B之間分配，以便滿足A、B的大小。
例2-8 考察圖14-14a 中從a到n的1 4個(gè)點(diǎn)。這些點(diǎn)標(biāo)繪在圖14-14b 中。中點(diǎn)xi = 1，垂線x = 1如圖14-14b 中的虛線所示。虛線左邊的點(diǎn)(如b, c, h, n, i)屬于A，右邊的點(diǎn)(如a, e, f, j, k, l) 屬于B。d, g, m 落在垂線上，可將其中兩個(gè)加入A, 另一個(gè)加入B，以便A、B中包含相同的點(diǎn)數(shù)。假設(shè)d ,m加入A，g加入B。
設(shè)是i 的最近點(diǎn)對(duì)和B的最近點(diǎn)對(duì)中距離較小的一對(duì)點(diǎn)。若第三種情況下的最近點(diǎn)對(duì)比小。則每一個(gè)點(diǎn)距垂線的距離必小于，這樣，就可以淘汰那些距垂線距離≥ 的點(diǎn)。圖1 4 - 1 5中的虛線是分割線。陰影部分以分割線為中線，寬為2 。邊界線及其以外的點(diǎn)均被淘汰掉，只有陰影中的點(diǎn)被保留下來，以便確定是否存在第三類點(diǎn)對(duì)（對(duì)應(yīng)于第三種情況）其距離小于。用RA、RB 分別表示A和B中剩下的點(diǎn)。如果存在點(diǎn)對(duì)(p,q)，p?A, q?B且p, q 的距離小于，則p?RA，q?RB。可以通過每次檢查RA 中一個(gè)點(diǎn)來尋找這樣的點(diǎn)對(duì)。假設(shè)考察RA 中的p 點(diǎn)，p的y 坐標(biāo)為p.y，那么只需檢查RB 中滿足p.y- ＜q.y＜p.y+ 的q 點(diǎn)，看是否存在與p 間距小于的點(diǎn)。在圖14-16a 中給出了包含這種q 點(diǎn)的RB 的范圍。因此，只需將RB 中位于×2 陰影內(nèi)的點(diǎn)逐個(gè)與p 配對(duì)，以判斷p 是否是距離小于的第三類點(diǎn)。這個(gè)×2 區(qū)域被稱為是p 的比較區(qū)（comparing region）。
例2-9 考察例2 - 8中的1 4個(gè)點(diǎn)。A中的最近點(diǎn)對(duì)為(b,h)，其距離約為0 . 3 1 6。B中最近點(diǎn)對(duì)為(f, j)，其距離為0 . 3，因此= 0 . 3。當(dāng)考察是否存在第三類點(diǎn)時(shí)，除d, g, i, l, m 以外的點(diǎn)均被淘汰，因?yàn)樗鼈兙喾指罹€x= 1的距離≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m 的比較區(qū)中沒有點(diǎn)，只需考察i即可。i 的比較區(qū)中僅含點(diǎn)l。計(jì)算i 和l的距離，發(fā)現(xiàn)它小于，因此(i, l) 是最近的點(diǎn)對(duì)。
為了確定一個(gè)距離更小的第三類點(diǎn)，RA 中的每個(gè)點(diǎn)最多只需和RB 中的6個(gè)點(diǎn)比較，如圖1 4 - 1 6所示。
1. 選擇數(shù)據(jù)結(jié)構(gòu)
為了實(shí)現(xiàn)圖1 4 - 1 3的分而治之算法，需要確定什么是“小問題”以及如何表示點(diǎn)。由于集合中少于兩點(diǎn)時(shí)不存在最近點(diǎn)對(duì)，因此必須保證分解過程不會(huì)產(chǎn)生少于兩點(diǎn)的點(diǎn)集。如果將少于四點(diǎn)的點(diǎn)集做為“小問題”，就可以避免產(chǎn)生少于兩點(diǎn)的點(diǎn)集。
每個(gè)點(diǎn)可有三個(gè)參數(shù)：標(biāo)號(hào)， x 坐標(biāo)，y 坐標(biāo)。假設(shè)標(biāo)號(hào)為整數(shù)，每個(gè)點(diǎn)可用P o i n t l類（見程序1 4 - 8）來表示。為了便于按x 坐標(biāo)對(duì)各個(gè)點(diǎn)排序，可重載操作符＜=。歸并排序程序如1 4 -3所示。
程序14-8 點(diǎn)類
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; // 點(diǎn)的編號(hào)
float x, y; // 點(diǎn)坐標(biāo)
} ;
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; // 數(shù)組X中相同點(diǎn)的索引
float x, y; // 點(diǎn)坐標(biāo)
} ;
所輸入的n 個(gè)點(diǎn)可以用數(shù)組X來表示。假設(shè)X中的點(diǎn)已按照x 坐標(biāo)排序，在分割過程中如果當(dāng)前考察的點(diǎn)是X [l :r]，那么首先計(jì)算m= (l+r) / 2，X[ l:m]中的點(diǎn)屬于A，剩下的點(diǎn)屬于B。計(jì)算出A和B中的最近點(diǎn)對(duì)之后，還需要計(jì)算RA 和RB，然后確定是否存在更近的點(diǎn)對(duì)，其中一點(diǎn)屬于RA，另一點(diǎn)屬于RB。如果點(diǎn)已按y 坐標(biāo)排序，那么可以用一種很簡單的方式來測試圖1 4 - 1 6。按y 坐標(biāo)排序的點(diǎn)保存在另一個(gè)使用類P o i n t 2 (見程序14-8) 的數(shù)組中。注意到在P o i n t 2類中，為了便于y 坐標(biāo)排序，已重載了操作符＜＝。成員p 用于指向X中的對(duì)應(yīng)點(diǎn)。
確定了必要的數(shù)據(jù)結(jié)構(gòu)之后，再來看看所要產(chǎn)生的代碼。首先定義一個(gè)模板函數(shù)d i s t (見程序1 4 - 9 )來計(jì)算點(diǎn)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 計(jì)算兩點(diǎn)距離
template
inline float dist(const T& u, const T& v)
{ / /計(jì)算點(diǎn)u 和v之間的距離
float dx = u.x-v. x ;
float dy = u.y-v. y ;
return sqrt(dx * dx + dy * dy);
}
如果點(diǎn)的數(shù)目少于兩個(gè)，則函數(shù)c l o s e s t (見程序1 4 - 1 0 )返回f a l s e，如果成功時(shí)函數(shù)返回t r u e。當(dāng)函數(shù)成功時(shí)，在參數(shù)a 和b 中返回距離最近的兩個(gè)點(diǎn)，在參數(shù)d 中返回距離。代碼首先驗(yàn)證至少存在兩點(diǎn)，然后使用M e rg e S o r t函數(shù)(見程序14-3) 按x 坐標(biāo)對(duì)X中的點(diǎn)排序。接下來把這些點(diǎn)復(fù)制到數(shù)組Y中并按y 坐標(biāo)進(jìn)行排序。排序完成時(shí)，對(duì)任一個(gè)i，有Y [i ] . y≤Y [i+ 1 ] . y，并且Y [i ] .p給出了點(diǎn)i 在X中的位置。上述準(zhǔn)備工作做完以后，調(diào)用函數(shù)close (見程序1 4 - 11 )，該函數(shù)實(shí)際求解最近點(diǎn)對(duì)。
程序14-10 預(yù)處理及調(diào)用c l o s e
bool closest(Point1 X[], int n, Point1& a, Point1& b, float& d)
{// 在n >= 2 個(gè)點(diǎn)中尋找最近點(diǎn)對(duì)
// 如果少于2個(gè)點(diǎn)，則返回f a l s e
// 否則，在a 和b中返回距離最近的兩個(gè)點(diǎn)
if (n < 2) return false;
// 按x坐標(biāo)排序
M e r g e S o r t ( X , n ) ;
// 創(chuàng)建一個(gè)按y坐標(biāo)排序的點(diǎn)數(shù)組
Point2 *Y = new Point2 [n];
for (int i = 0; i < n; i++) {
// 將點(diǎn)i 從X 復(fù)制到Y(jié)
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坐標(biāo)排序
// 創(chuàng)建臨時(shí)數(shù)組
Point2 *Z = new Point2 [n];
// 尋找最近點(diǎn)對(duì)
c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;
// 刪除數(shù)組并返回
delete [] Y;
delete [] Z;
return true;
}
程序1 4 - 11 計(jì)算最近點(diǎn)對(duì)
void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1& a, Point1& b, float& d)
{//X[l:r] 按x坐標(biāo)排序
//Y[l:r] 按y坐標(biāo)排序
if (r-l == 1) {// 兩個(gè)點(diǎn)
a = X[l];
b = X[r];
d = dist(X[l], X[r]);
r e t u r n ; }
if (r-l == 2) {// 三個(gè)點(diǎn)
// 計(jì)算所有點(diǎn)對(duì)之間的距離
float d1 = dist(X[l], X[l+1]);
float d2 = dist(X[l+1], X[r]);
float d3 = dist(X[l], X[r]);
// 尋找最近點(diǎn)對(duì)
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 ; }
/ /多于三個(gè)點(diǎn)，劃分為兩部分
int m = (l+r)/2; // X[l:m] 在A中，余下的在B中
// 在Z[l:m] 和Z [ m + 1 : r ]中創(chuàng)建按y排序的表
int f = l, // Z[l:m]的游標(biāo)
g = m+1; // Z[m+1:r]的游標(biāo)
for (int i = l; i <= r; i++)
if (Y[i].p > m) Z[g++] = Y[i];
else Z[f++] = Y[i];
// 對(duì)以上兩個(gè)部分進(jìn)行求解
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) 是兩者中較近的點(diǎn)對(duì)
if (dr < d) {a = ar;
b = br;
d = dr;}
M e r g e ( Z , Y,l,m,r);// 重構(gòu)Y
/ /距離小于d的點(diǎn)放入Z
int k = l; // Z的游標(biāo)
for (i = l; i <= r; i++)
if (fabs(Y[m].x - Y[i].x) < d) Z[k++] = Y[i];
// 通過檢查Z [ l : k - 1 ]中的所有點(diǎn)對(duì)，尋找較近的點(diǎn)對(duì)
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) {// 較近的點(diǎn)對(duì)
d = dp;
a = X[Z[i].p];
b = X[Z[j].p];}
}
}
}
函數(shù)c l o s e（見程序1 4 - 11）用來確定X[1:r] 中的最近點(diǎn)對(duì)。假定這些點(diǎn)按x 坐標(biāo)排序。在Y [ 1 : r ]中對(duì)這些點(diǎn)按y 坐標(biāo)排序。Z[ 1 : r ]用來存放中間結(jié)果。找到最近點(diǎn)對(duì)以后，將在a, b中返回最近點(diǎn)對(duì)，在d 中返回距離，數(shù)組Y被恢復(fù)為輸入狀態(tài)。函數(shù)并未修改數(shù)組X。
首先考察“小問題”，即少于四個(gè)點(diǎn)的點(diǎn)集。因?yàn)榉指钸^程不會(huì)產(chǎn)生少于兩點(diǎn)的數(shù)組，因此只需要處理兩點(diǎn)和三點(diǎn)的情形。對(duì)于這兩種情形，可以嘗試所有的可能性。當(dāng)點(diǎn)數(shù)超過三個(gè)時(shí)，通過計(jì)算m = ( 1 + r ) / 2把點(diǎn)集分為兩組A和B，X [ 1 : m ]屬于A，X [ m + 1 : r ]屬于B。通過從左至右掃描Y中的點(diǎn)以及確定哪些點(diǎn)屬于A，哪些點(diǎn)屬于B，可以創(chuàng)建分別與A組和B組對(duì)應(yīng)的，按y 坐標(biāo)排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此時(shí)Y和Z的角色互相交換，依次執(zhí)行兩個(gè)遞歸調(diào)用來獲取A和B中的最近點(diǎn)對(duì)。在兩次遞歸調(diào)用返回后，必須保證Z不發(fā)生改變，但對(duì)Y則無此要求。不過，僅Y [ l : r ]可能會(huì)發(fā)生改變。通過合并操作（見程序1 4 - 5）可以以Z [ 1 : r ]重構(gòu)Y [ 1 : r ]。
為實(shí)現(xiàn)圖1 4 - 1 6的策略，首先掃描Y [ 1 : r ]，并收集距分割線小于的點(diǎn)，將這些點(diǎn)存放在Z [ 1 : k - 1 ]中。可按如下兩種方式來把RA中點(diǎn)p 與p 的比較區(qū)內(nèi)的所有點(diǎn)進(jìn)行配對(duì)：1) 與RB 中y 坐標(biāo)≥p.y 的點(diǎn)配對(duì)；2) 與y 坐標(biāo)≤p.y 的點(diǎn)配對(duì)。這可以通過將每個(gè)點(diǎn)Z [ i ]（1≤i < k，不管該點(diǎn)是在RA
還是在RB中）與Z[j] 配對(duì)來實(shí)現(xiàn)，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。對(duì)每一個(gè)Z [ i ]，在2 × 區(qū)域內(nèi)所檢查的點(diǎn)如圖1 4 - 1 7所示。由于在每個(gè)2 × 子區(qū)域內(nèi)的點(diǎn)至少相距。因此每一個(gè)子區(qū)域中的點(diǎn)數(shù)不會(huì)超過四個(gè)，所以與Z [ i ]配對(duì)的點(diǎn)Z [ j ]最多有七個(gè)。
2. 復(fù)雜性分析
令t (n) 代表處理n 個(gè)點(diǎn)時(shí)，函數(shù)close 所需要的時(shí)間。當(dāng)n＜4時(shí)，t (n) 等于某個(gè)常數(shù)d。當(dāng)n≥4時(shí)，需花費(fèi)(n) 時(shí)間來完成以下工作：將點(diǎn)集劃分為兩個(gè)部分，兩次遞歸調(diào)用后重構(gòu)Y，淘汰距分割線很遠(yuǎn)的點(diǎn)，尋找更好的第三類點(diǎn)對(duì)。兩次遞歸調(diào)用需分別耗時(shí)t (「n /2ù」和t (?n /2?).
這個(gè)遞歸式與歸并排序的遞歸式完全一樣，其結(jié)果為t (n) = (nl o gn)。另外，函數(shù)c l o s e s t還需耗時(shí)(nl o gn)來完成如下額外工作：對(duì)X進(jìn)行排序，創(chuàng)建Y和Z，對(duì)Y進(jìn)行排序。因此分而治之最近點(diǎn)對(duì)求解算法的時(shí)間復(fù)雜性為(nl o gn)。