【正文】 。這時只要讓這 2個選手進行比賽就可以了。 按分治策略，將所有的選手分為兩半， n個選手的比賽日程表就可以通過為 n/2個選手設計的比賽日程表來決定。 return d。 dm=min(d1,d2)。 構造 S1和 S2； //S1={p∈ S|x(p)=m}, S2={p∈ S|x(p)m} d1=cpair2(S1)。 if (n 2) return 。對 P1中每一點最多只要檢查 P2中排好序的相繼 6個點。由上面的分析可知，這種投影點最多只有 6個。 22222 3625)3/2()2/())()(())()(( dddvyuyvxux ???????為了 確切地知道要檢查哪 6個點 ，可以將 p和P2中所有 S2的點投影到垂直線 l上。設 u， v是位于同一小矩形中的 2個點，則 distance(u,v)d。 ?因此，在分治法的合并步驟中 最多只需要檢查 6 n/2=3n個候選者 能否在線性時間內找到 p3,q3？ 證明 :將矩形 R的長為 2d的邊 3等分，將它的長為d的邊 2等分，由此導出 6個 (d/2) (2d/3)的矩形。 滿足這個條件的 P2中的點一定落在一個 d 2d的矩形 R中 ?由 d的意義可知， P2中任何 2個 S中的點的距離都不小于 d。 ?遞歸地在 S1和 S2上找出其最小距離 d1和 d2，并設d=min{d1,d2}， S中的最接近點對或者是 d，或者是某個 {p,q}，其中 p∈ P1且 q∈ P2。其中 m為 S中各點 x坐標的中位數。 能否在線性時間內找到 p3,q3？ 最接近點對問題 ?下面來考慮二維的情形。 ?因此，我們用線性時間就能找到區(qū)間 (md,m]和 (m,m+d]中所有點，即 p3和 q3。 ?由于在 S1中，每個長度為 d的半閉區(qū)間至多包含一個點（否則必有兩點距離小于 d），并且 m是 S1和 S2的分割點，因此(md,m]中至多包含 S中的一個點。 ?遞歸地在 S1和 S2上找出其最接近點對 {p1,p2}和 {q1,q2}，并設 d=min{|p1p2|,|q1q2|}， S中的最接近點對或者是 {p1,p2}，或者是 {q1,q2}，或者是某個 {p3,q3}，其中 p3∈ S1且 q3∈ S2。最接近點對即為這 n個實數中相差最小的 2個實數。 ?為了使問題易于理解和分析，先來考慮 一維 的情形。當然，除了 5和 75之外，還有其他選擇。這 2點保證了 T(n)的遞歸式中 2個自變量之和n/5+3n/4=19n/20=εn， 0ε1。 else return Select(a,i+1,r,kj)。 int i=Partition(a,p,r, x), j=ip+1。 i++ ) 將 a[p+5*i]至 a[p+5*i+4]的第 3小元素 與 a[p+i]交換位置 。 for ( int i = 0。 return a[p+k1]。而當n≥75時， 3(n5)/10≥n/4所以按此基準劃分所得的 2個子數組的長度都至少縮短 1/4。在這種情況下，找出的基準 x至少比 3(n5)/10個元素大，因為在每一組中有 2個元素小于本組的中位數，而 n/5個中位數中又有 (n5)/10個小于基準 x。以這個元素作為劃分基準。 ?遞歸調用 select來找出這 ?n/5?個元素的中位數。 ?將 n個輸入元素劃分成 ?n/5?個組，每組 5個元素，只可能有一個組不是 5個元素。所以，在最壞情況下，算法所需的計算時間 T(n)滿足遞歸式T(n)≤T(9n/10)+O(n) 。 線性時間選擇 如果能在線性時間內找到一個劃分基準，使得按這個基準所劃分出的 2個子數組的長度都至少為原數組長度的 ε倍 (0ε1是某個正常數 )，那么就可以 在最壞情況下 用 O(n)時間完成選擇任務。 else return RandomizedSelect(a,i+1,r,kj)。 int i=RandomizedPartition(a,p,r), j=ip+1。在快速排序算法的每一步中，當數組還沒有被劃分時，可以在 a[p:r]中隨機選出一個元素作為劃分基準，這樣可以使劃分基準的選擇是隨機的，從而可以期望劃分是較對稱的。 } 快速排序 快速排序算法的性能取決于劃分的對稱性。 Swap(a[i], a[p])。 ji{5, 2, 5, 6, 7, 8} i++。 ji{5, 7, 5, 2, 6, 8} i++。 return j。 } a[p] = a[j]。 if (i = j) break。 // 將 x的元素交換到左邊區(qū)域 // 將 x的元素交換到右邊區(qū)域 while (true) { while (a[++i] x)。 //對右半段排序 } } 快速排序 templateclass Type int Partition (Type a[], int p, int r) { int i = p, j = r + 1。 QuickSort (a,p,q1)。 初始序列 [49] [38] [65] [97] [76] [13] [27] [38 49] [65 97] [13 76] [27] 第一步 第二步 [38 49 65 97] [13 27 76] 第三步 [13 27 38 49 65 76 97] 合并排序 ?最壞時間復雜度： O(nlogn) ?平均時間復雜度： O(nlogn) ?輔助空間： O(n) 快速排序 在快速排序中，記錄的比較和交換是從兩端向中間 進行的，關鍵字較大的記錄一次就能交換到后面單 元，關鍵字較小的記錄一次就能交換到前面單元， 記錄每次移動的距離較大，因而總的比較和移動次 數較少。 //合并到數組 b copy(a, b, left, right)。 mergeSort(a, i+1, right)。 void MergeSort(Type a[], int left, int right) { if (leftright) {//至少有 2個元素 int i=(left+right)/2。 // 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s)。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s)。} // 覆蓋右下角子棋盤 if (dr = tr + s amp。 else {// 用 t 號 L型骨牌覆蓋右上角 board[tr + s][tc + s 1] = t。amp。 // 覆蓋其余方格 chessBoard(tr, tc+s, tr+s1, tc+s, s)。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s)。} // 覆蓋右上角子棋盤 if (dr tr + s amp。 else {// 此棋盤中無特殊方格 // 用 t 號 L型骨牌覆蓋右下角 board[tr + s 1][tc + s 1] = t。amp。 int t = tile++, // L型骨牌號 s = size/2。遞歸地使用這種分割，直至棋盤簡化為棋盤 1 1。 特殊方格必