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