【正文】 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 循環(huán)賽日程表 設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。 } 復(fù)雜度分析 T(n)=O(nlogn) ??????? 44)()2/(2)1()(nnnOnTOnT設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。 4. 設(shè) P1是 S1中距垂直分割線 l的距離在 dm之內(nèi)的所有點(diǎn)組成的集合； P2是 S2中距分割線 l的距離在 dm之內(nèi)所有點(diǎn)組成的集合； 將 P1和 P2中點(diǎn)依其 y坐標(biāo)值排序； 并設(shè) X和 Y是相應(yīng)的已排好序的點(diǎn)列； 5. 通過掃描 X以及對(duì)于 X中每個(gè)點(diǎn)檢查 Y中與其距離在 dm之內(nèi)的所有點(diǎn) (最多 6個(gè) )可以完成合并； 當(dāng) X中的掃描指針逐次向上移動(dòng)時(shí)， Y中的掃描指針可在寬為 2dm的區(qū)間內(nèi)移動(dòng)； 設(shè) dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離； 6. d=min(dm,dl)。 d2=cpair2(S2)。 1. m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。 最接近點(diǎn)對(duì)問題 最接近點(diǎn)對(duì)問題 public static double cpair2(S) { n=|S|。 ?因此，若將 P1和 P2中所有 S中點(diǎn)按其 y坐標(biāo)排好序，則對(duì) P1中所有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對(duì)候選者的 S2中點(diǎn)一定在矩形 R中，所以它們?cè)谥本€ l上的投影點(diǎn)距 p在 l上投影點(diǎn)的距離小于 d。這與 d的意義相矛盾。若矩形 R中有多于 6個(gè) S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè) (d/2) (2d/3)的小矩形中有 2個(gè)以上 S中的點(diǎn)。由此可以推出 矩形 R中最多只有 6個(gè) S中的點(diǎn) 。 ?能否在線性時(shí)間內(nèi)找到 p,q？ 最接近點(diǎn)對(duì)問題 ?考慮 P1中任意一點(diǎn) p，它若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有 distance(p， q)＜ d。由此將 S分割為 S1和 S2。 ?選取一垂直線 l:x=m來作為分割直線。 從而我們用線性時(shí)間就可以將 S1的解和 S2的解合并成為 S的解 。由圖可以看出， 如果 (md,m]中有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 ?能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對(duì)問題 ?如果 S的最接近點(diǎn)對(duì)是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者與 m的距離不超過 d， 即 p3∈ (md,m]， q3∈ (m,m+d]。 ?假設(shè)我們用 x軸上某個(gè)點(diǎn) m將 S劃分為 2個(gè)子集 S1和 S2 ， 基于 平衡子問題 的思想，用 S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。此時(shí)，S中的 n個(gè)點(diǎn)退化為 x軸上的 n個(gè)實(shí)數(shù) x1,x2,…,xn 。 最接近點(diǎn)對(duì)問題 給定平面上 n個(gè)點(diǎn)的集合 S，找其中的一對(duì)點(diǎn)，使得在 n個(gè)點(diǎn)組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。這是使 T(n)=O(n)的關(guān)鍵之處。 } 復(fù)雜度分析 T(n)=O(n) ???????? 7575)4/3()5/()( 21nnnTnTnCCnT上述算法將每一組的大小定為 5，并選取 75作為是否作遞歸調(diào)用的分界點(diǎn)。 if (k=j) return select(p,i,k)。 } Comparable x = select(p, p+(rp4)/5, (rp+6)/10)。j++) bubble(s,tj)。 for (int j=0。 i=(rp4)/5。 } //將 a[p+5*i]至 a[p+5*i+4]的第 3小元素 //與 a[p+i]交換位置 。 bubbleSort(p,r)。而當(dāng)n≥75時(shí)， 3(n5)/10≥n/4所以按此基準(zhǔn)劃分所得的 2個(gè)子數(shù)組的長度都至少縮短 1/4。在這種情況下，找出的基準(zhǔn) x至少比 3(n5)/10個(gè)元素大，因?yàn)樵诿恳唤M中有 2個(gè)元素小于本組的中位數(shù)，而 n/5個(gè)中位數(shù)中又有 (n5)/10個(gè)小于基準(zhǔn) x。以這個(gè)元素作為劃分基準(zhǔn)。 ?遞歸調(diào)用 select來找出這 ?n/5?個(gè)元素的中位數(shù)。 ?將 n個(gè)輸入元素劃分成 ?n/5?個(gè)組，每組 5個(gè)元素，只可能有一個(gè)組不是 5個(gè)元素。所以，在最壞情況下，算法所需的計(jì)算時(shí)間 T(n)滿足遞歸式T(n)≤T(9n/10)+O(n) 。 線性時(shí)間選擇 如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的 2個(gè)子數(shù)組的長度都至少為原數(shù)組長度的 ε倍 (0ε1是某個(gè)正常數(shù) )，那么就可以 在最壞情況下 用 O(n)時(shí)間完成選擇任務(wù)。 else return randomizedSelect(i+1,r,kj)。 int i=randomizedpartition(p,r), j=ip+1。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時(shí)，可以在 a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。 } 快速排序 快速排序算法的性能取決于劃分的對(duì)稱性。 (a, i, p)。 ji完成 快速排序具有 不穩(wěn)定性 。 ji{5, 6, 5, 2, 7, 8} j。 } 初始序列 {6, 7, 5, 2, 5, 8} j。 a[j] = x。 (a, i, j)。 while (a[j].pareTo(x) 0)。 Comparable x = a[p]。 //對(duì)左半段排序 qSort (q+1,r)。下標(biāo) q在劃分過程中確定。 private static void qSort(int p, int r) { if (pr) { int q=partition(p,r)。 初始序列 [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] 合并排序 ?最壞時(shí)間復(fù)雜度： O(nlogn) ?平均時(shí)間復(fù)雜度： O(nlogn) ?輔助空間： O(n) ?穩(wěn)定性：穩(wěn)定 思考題： 給定 有序表 A[1:n]，修改合并排序算法，求出該有序表的逆序?qū)?shù)。 //合并到數(shù)組 b copy(a, b, left, right)。 mergeSort(a, i+1, right)。 public static void mergeSort(Comparable a[], int left, int right) { if (leftright) {//至少有 2個(gè)元素 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)。} // 覆蓋