【正文】 ,int low,int high){ //交換順序表 [low… high]的記錄，使樞軸記錄到位，并返回其位置。 pivotkey=[low].key。amp。 [low]←→ [high]。amp。 [high] ←→ [low]。 //返回樞軸記錄所在位置。 r[i] 0 1 2 3 4 5 6 初態(tài) 21 25 49 25* 16 08 第 1趟 high low 21 08 25 16 49 25* 21pivotkey=21 08 2516 49( 08 ， 16 ） 21 （ 25* ， 49， 25 ） 25*跑到了前面， 不穩(wěn)定 ！ 39 j從高端 掃描 尋找小于pivot的元素 i從低端 掃描 尋找大于pivot的元素 i=low。r[0]=r[low]。 i j i j amp。r[j].key=pivot j。 i j amp。r[i].key=pivot i。 r[i] = r[0]。 Y Y Y N N N 一趟快速排序算法流程圖 40 void QSort ( SqList amp。 QSort ( L, low, pivot1)。 } } 整個快速排序的遞歸算法： 見教材 P276 //長度 1 //對順序表 L中的子序列 r[ low… high] 作快速排序 //QSort void QuickSort ( SqList amp。 } 對順序表 L進行快速排序的操作函數(shù)為： 41 例 3： 以關(guān)鍵字序列（ 256， 301， 751， 129， 937， 863， 742，694， 076， 438）為例，寫出執(zhí)行快速算法的 各趟 排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。 42 快速排序算法詳細(xì)分析： ?快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù) （新的 low和 high） 。 實驗結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個 。因此，要求存儲開銷為 o(log2n)。此時，快速排序的趟數(shù)最少。這樣，必須經(jīng)過 n1 趟才能把所有對象定位，而且第 i 趟需要經(jīng)過 ni 次關(guān)鍵字比較才能找到第 i 個對象的安放位置，總的關(guān)鍵字比較次數(shù)將達到 n2/2 ? 快速排序是一個 不穩(wěn)定 的排序方法 45 討論 2. “快速排序 ” 是否真的比任何排序算法都快？ 設(shè)每個子表的支點都在中間（比較均衡），則： 第 1趟比較，可以確定 1個元素的位置； 第 2趟比較（ 2個子表），可以再確定 2個元素的位置； 第 3趟比較（ 4個子表），可以再確定 4個元素的位置； 第 4趟比較（ 8個子表），可以再確定 8個元素的位置； …… 只需 ?log2n? ＋ 1趟便可排好序。 教材 P276有證明：快速排序的平均排序效率為 O(nlog2n)； 但最壞情況 (例如已經(jīng)有序 )下仍為 O(n2),改進措施見 P277。待到第 n1 趟作完，待排序?qū)ο笾皇Ｏ?1個，就不用再選了。L) { for (int i=1。++i) { j=SelectMinKey(L,i)。//與第 i個記錄交換 } } 50 21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 1 49 25 16 25 16 08 49 08 25* 49 21 i = 2 i = 3 08 16 25* 25 21 初始 最小者 08 交換 21,08 最小者 16 交換 25,16 最小者 21 交換 49,21 51 49 25* 0 1 2 3 4 5 25* i = 5 25 16 08 49 25* 49 21 結(jié)果 i = 4 08 16 25 21 最小者 25* 無交換 最小者 25 無交換 25 21 16 08 各趟排序后的結(jié)果 52 算法分析 ? 直接選擇排序的關(guān)鍵字比較次數(shù) KCN與對象的初始排列無關(guān)。因此，總的關(guān)鍵字比較次數(shù)為 ???????? 20 211ninninKCN )()(時間復(fù)雜度？ O（ n2） 53 ? 對象的移動次數(shù)與對象序列的初始排列有關(guān)。 ? 最壞情況是每一趟都要進行交換，總的對象移動次數(shù)為 RMN = 3(n1)。 54 樹形選擇排序 (錦標(biāo)賽排序 ) ? 它的思想與體育比賽時的淘汰賽類似。然后對這 ?n/2? 個對象再進行關(guān)鍵字的兩兩比較， … ，如此重復(fù)，直到選出一個關(guān)鍵字最小的對象為止。 55 08 Winner 21 08 08 63 25* 21 21 25 49 25* 16 08 63 56 勝者樹的概念 ? 每次兩兩比較的結(jié)果是把關(guān)鍵字小者作為優(yōu)勝者上升到雙親結(jié)點 ， 稱這種比賽樹為勝者樹 。 57 08 Winner (勝者 ) 21 08 08 63 25* 21 21 25 49 25* 16 08 63 形成初始勝者樹（最小關(guān)鍵字上升到根） a[0] 關(guān)鍵字比較次數(shù) : 6 58 16 Winner (勝者 ) 21 16 16 63 25* 21 21 25 49 25* 16 63 輸出冠軍并調(diào)整勝者樹后樹的狀態(tài) a[1] 關(guān)鍵字比較次數(shù) : 2 59 21 Winner (勝者 ) 21 63 63 25* 21 21 25 49 25* 63 輸出亞軍并調(diào)整勝者樹后樹的狀態(tài) a[2] 關(guān)鍵字比較次數(shù) : 2 60 25 Winner (勝者 ) 25 63 63 25* 25 25 49 25* 63 輸出第三名并調(diào)整勝者樹后樹的狀態(tài) a[3] 關(guān)鍵字比較次數(shù) : 2 61 25* Winner (勝者 ) 25* 63 63 25* 49 25* 63 輸出第四名并調(diào)整勝者樹后樹的狀態(tài) a[4] 關(guān)鍵字比較次數(shù) : 2 62 63 Winner (勝者 ) 63 63 63 全部比賽結(jié)果輸出時樹的狀態(tài) a[6] 關(guān)鍵字比較次數(shù) : 2 63 算法分析 ? 錦標(biāo)賽排序構(gòu)成的樹是滿的完全二叉樹，其深度為 ?log2(n+1)?，其中 n 為待排序元素個數(shù)?？傟P(guān)鍵字比較次數(shù)為 O(nlog2n)。 ? 這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。 64 堆排序 (Heap Sort) ? 利用堆及其運算，可以很容易地實現(xiàn)選擇排序的思路。 ? 給定一組關(guān)鍵字，初始態(tài)存儲時是一個完全二叉樹 ? 堆的建立 ? 對堆的篩選與建立的重復(fù)交替 65 堆排序 (Heap Sort) ? 給定一組關(guān)鍵字，初始態(tài)存儲時是一個完全二叉樹 ? 小頂堆的建立： 對 n/2 1,的元素依次進行篩選： ?若 ki=k2i且 ki=k2i+1，則不換 ?若 kik2i(k2i+1)且 ki=k2i+1(k2i)，則 ki 與 k2i（ k2i+1 ）交換 ?若 kik2i且 kik2i+1，則 ki與較小的哪個交換 ?若 (k2i=k2i+1) ki,則 ki與 k2i交換 （大頂堆剛好相反） ? 對堆的篩選與建立的重復(fù)交替 66 建立初始的最大堆 21 25 25* 49 16 08 1 2 3 4 5 6 i 21 25 25* 16 49 08 1 3 6 5 4 2 i 21 25 49 25* 16 08 初始關(guān)鍵字集合 21 25 49 25* 16 08 i = 3 時的局部調(diào)整 67 21 25 25* 49 16 08 1 2 3 4 5 6 i 49 25 25* 16 21 08 1 3 6 5 4 2 21 25 49 25* 16 08 49 25 21 25* 16 08 i = 1 時的局部調(diào)整 形成大頂堆 i = 2 時的局部調(diào)整 68 最大堆的向下調(diào)整算法 void HeapAdjust(HeapType amp。 for (int j=2*s。j*=2) { if ((jm) amp。 (LT([j].key,[j+1].key))) ++j。 [s].key=[j].key。 } [s]=rc。結(jié)果具有次最大關(guān)鍵字的對象又上浮到堆頂，即 r[1]位置。 ? 如此反復(fù)執(zhí)行，最后得到全部排序好的對象序列。 70 49 25 25* 21 16 08 1 2 3 4 5 6 08 25 25* 16 21 49 1 3 6 5 4 2 49 25 21 25* 16 08 08 25 21 25* 16 49 交換 1 號與 6 號對象 , 6 號對象就位 初始最大堆 71 25 25* 08 21 16 49 1 2 3 4 5 6 16 25* 08 25 21 49 1 3 6 5 4 2 25 25* 21 08 16 49 16 25* 21 08 25 49 交換 1 號與 5 號對象 , 5 號對象就位 從 1 號到 5號 重新 調(diào)整為最大堆 72 25* 16 08 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 25* 16 21 08 25 49 08 16 21 25* 25 49 交換 1 號與 4 號對象 , 4 號對象就位 從 1 號到 4 號 重新 調(diào)整為最大堆 73 21 16 25* 08 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 21 16 08 25* 25 49 08 16 21 25* 25 49 交換 1 號與 3 號對象 , 3 號對象就位 從 1 號到 3 號 重新 調(diào)整為最大堆 74 16 08 25* 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 16 08 21 25* 25 49 08 16 21 25* 25 49 交換 1 號與 2 號對象 , 2 號對象就位 從 1 號到 2 號 重新 調(diào)整為最大堆 75 堆排序的算法 void HeapSort(HeapType amp。 for (int i=。 i) HeapAdjust(H,i,)。 i1。 [1]=[i]。 Heap