【正文】 . 2021年 11月 12日 85 快速排序 （ 2） 求解子問題 ：分別對(duì)劃分后的每一個(gè)子序列遞歸處理； （ 3） 合并 ：由于對(duì)子序列 ap … a q1和 aq+1 … a r的排序是就地進(jìn)行的，所以合并不需要執(zhí)行任何操作。 快速排序的分治策略是： （ 1） 劃分 ：選定一個(gè)記錄作為軸值 ， 以軸值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列 ap … aq1和 aq+1 … ar，前一個(gè)子序列中記錄的值均小于或等于軸值 ， 后一個(gè)子序列中記錄的值均大于或等于軸值； 2021年 11月 12日 86 快速排序 [ ap … … aq1 ] aq [ aq+1 … … ar ] 均 ≤aq 軸值 均 ≥aq 位于最終位置 ?合并排序按照記錄在序列中的位置對(duì)序列進(jìn)行劃分； ?快速排序按照記錄的值對(duì)序列進(jìn)行劃分。 2021年 11月 12日 87 快速排序 在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。 templateclass Type void QuickSort (Type a[], int p, int r) { if (pr) { int q=Partition(a,p,r)。 QuickSort (a,p,q1)。 //對(duì)左半段排序 QuickSort (a,q+1,r)。 //對(duì)右半段排序 } } 2021年 11月 12日 88 templateclass Type int Partition (Type a[], int p, int r) { int i = p, j = r + 1。 Type x=a[p]。 // 將 x的元素交換到左邊區(qū)域 // 將 x的元素交換到右邊區(qū)域 while (true) { while (a[++i] xamp。amp。ir)。 while (a[ j] x)。 if (i = j) break。 Swap(a[i], a[j])。 } a[p] = a[j]。 a[j] = x。 return j。 2021年 11月 12日 89 13 65 27 50 38 49 55 j i i i 13 65 27 50 38 49 55 i j j 快速排序一次劃分示例 j 13 65 27 50 38 49 55 i j 2021年 11月 12日 90 13 65 27 50 38 49 55 j i i j j 13 65 27 50 38 49 55 i 13 65 27 50 38 49 55 快速排序一次劃分示例 j 2021年 11月 12日 91 按照快速排序的思想排下列序列 初始序列： {6, 7, 5, 2, 5, 8} 2021年 11月 12日 92 ?“基準(zhǔn)值”的選擇有多種方法。最簡(jiǎn)單的方法是使用第一個(gè)記錄的關(guān)鍵字值。但是，如 果輸入的數(shù)組是正序或者是逆序的，就會(huì)將所有的記錄分到“基準(zhǔn)值”的一邊。較好的方法是隨機(jī)選取“基準(zhǔn)值”，這樣可以減少由于原始輸入對(duì)排序造成的影響，但隨機(jī)選取“基準(zhǔn)值”的開銷較大。 2021年 11月 12日 93 templateclass Type int RandomizedPartition (Type a[], int p, int r) { int i = Random(p,r)。 Swap(a[i], a[p])。 return Partition (a, p, r)。 } 快速排序 快速排序算法的性能取決于劃分的對(duì)稱性。通過修改算法 partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時(shí)，可以在 a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。 2021年 11月 12日 94 templateclass Type void RandomizedQuickSort (Type a[], int p, int r) { if (pr) { int q=RandomizedPartition(a,p,r)。 RandomizedQuickSort (a,p,q1)。 //對(duì)左半段排序 RandomizedQuickSort (a,q+1,r)。 //對(duì)右半段排序 } } 2021年 11月 12日 95 快速排序 ?在 最壞情況 下，待排序記錄序列正序或逆序，每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列（另一個(gè)子序列為空）。 )()()1()(2nOnOnTnT????2021年 11月 12日 96 快速排序 ? 在 最好情況 下，每次劃分對(duì)一個(gè)記錄定位后，該記錄的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同。 )l o g()()2/(2)(nnOnOnTnT???)l o g()(2))1()((1)(11nnOnkTnnkTknTnnTnknk???????? ????? 在平均情況下，設(shè)基準(zhǔn)記錄的關(guān)鍵字第 k小（ 1≤k≤n） ，則有： 2021年 11月 12日 97 ?最壞時(shí)間復(fù)雜度： O(n2) ?平均時(shí)間復(fù)雜度： O(nlogn) ?輔助空間： O(n)或 O(logn) 2021年 11月 12日 98 冒泡排序 ? 冒泡排序又稱起泡排序。其基本思想是先將數(shù)組中的第n1個(gè)記錄與第 n2個(gè)記錄的關(guān)鍵字值進(jìn)行比較，如果第n1個(gè)記錄的關(guān)鍵字值小于第 n2個(gè)記錄的關(guān)鍵字值，則兩個(gè)記錄交換位臵，否則不交換。然后比較第 n2個(gè)記錄與第 n3個(gè)記錄的關(guān)鍵字值，若第 n2個(gè)記錄的關(guān)鍵字值小于第 n3個(gè)記錄的關(guān)鍵字值，兩個(gè)記錄交換位臵，否則不交換， … ，依此類推，直到第 1個(gè)記錄與第 0個(gè)記錄進(jìn)行比較。經(jīng)過如此一趟的比較與交換， n個(gè)記錄中關(guān)鍵字值最小的記錄就會(huì)被交換到數(shù)組的第 0個(gè)位臵。此后，再對(duì)數(shù)組中位臵 1~n1的記錄進(jìn)行同樣的過程，使得 n1個(gè)記錄中關(guān)鍵字值最小的記錄被放到數(shù)組的第 1個(gè)位臵。然后再對(duì) n2個(gè)記錄重復(fù)上述過程， … ，直到某一趟排序過程中不出現(xiàn)記錄交換位臵，排序結(jié)束。 2021年 11月 12日 99 ?由于每一趟排序具有最小關(guān)鍵字值的記錄就向數(shù)組的頂部移動(dòng)。就象水底的“水泡”冒到水面上一樣，因此稱為冒泡排序。 2021年 11月 12日 100 冒泡排序的工作過程 ?46 95 90 56 82 17 30 15 ?i =0 15 46 95 90 56 82 17 30 ?i = 1 15 17 46 95 90 56 82 30 ?i = 2 15 17 30 46 95 90 56 82 ?i = 3 15 17 30 46 56 95 90 82 ?i = 4 15 17 30 46 56 82 95 90 ?i = 5 15 17 30 46 56 82 90 95 ?i = 6 15 17 30 46 56 82 90 95 ?i = 7 15 17 30 46 56 82 90 95 2021年 11月 12日 101 ?冒泡排序算法比較容易理解和編程，但它不是一個(gè)高效率的算法。不考慮數(shù)組中記錄的排列情況，冒泡排序的比較次數(shù)總將是 i，因此冒泡排序的時(shí)間復(fù)雜性為： O(n2) 一個(gè)記錄比它前一記錄的關(guān)鍵字小的概率有多大決定了記錄交換的次數(shù)。我們可以假定這個(gè)概率為平均情況下比較次數(shù)的一半，因此冒泡排序算法交換記錄的時(shí)間復(fù)雜性也為 O(n2)。 2021年 11月 12日 102 ?算法 : void bubblesort(ElemType a[ ],int n) { int i,j。 for (i=0。in1。i++) for (j = n1。ji。j) if (key(a[j])key(a[j1])) swap(a[j],a[j1])。 } 2021年 11月 12日 103 循環(huán)賽日程表 設(shè)有 n=2k個(gè)選手要進(jìn)行循環(huán)賽 ， 要求設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： （ 1） 每個(gè)選手必須與其他 n1個(gè)選手各賽一次； （ 2） 每個(gè)選手一天只能賽一次 。 2021年 11月 12日 104 (c) 2k(k=3)個(gè)選手比賽 加 4 加 2 (a) 2k(k=1)個(gè)選手比賽 1 2 2 1 1 2 2 1 3 4 4 3 3 4 4 3 1 2 2 1 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è) n行 n1列的二維表 ， 其中 ， 第 i 行第 j 列表示和第 i 個(gè)選手在第 j 天比賽的選手 。 (b) 2k(k=2)個(gè)選手比賽 2021年 11月 12日 105 2k個(gè)選手的比賽日程是在 2k1個(gè)選手的比賽日程的基礎(chǔ)上通過迭代的方法求得的 。 在每次迭代中 ， 將問題劃分為 4部分： （ 1） 左上角：左上角為 2k1個(gè)選手在前半程的比賽日程； （ 2） 左下角：左下角為另 2k1個(gè)選手在前半程的比賽日程 ，由左上角加 2k1得到 ， 例如 22個(gè)選手比賽 ， 左下角由左上角直接加 2得到 ， 23個(gè)選手比賽 ， 左下角由左上角直接加 4得到； （ 3） 右上角：將左下角直接抄到右上角得到另 2k1個(gè)選手在后半程的比賽日程； （ 4） 右下角：將左上角直接抄到右下角得到 2k1個(gè)選手在后半程的比賽日程； 算法設(shè)計(jì)的關(guān)鍵在于尋找這 4部分元素之間的對(duì)應(yīng)關(guān)系 。 循環(huán)賽日程表 2021年 11月 12日 106 循環(huán)賽日程表 ?算法復(fù)雜性分析 遞歸算法： )4()1(4)( kOkTkT ??? 非遞歸算法： ? ? ? ?? ? ? ????ks t i jksk s sOkT1212222)4(2)(