【正文】 較大的記錄在子表中后移 //在本趟結束時將 r[i]插入到正確位置 24 課堂練習： 1. 欲將序列（ Q, H, C, Y, P, A, M, S, R, D, F, X）中的關鍵碼按字母升序重排，則初始步長為 4的希爾排序一趟的結果是？ 答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后： 2. 以關鍵字序列 （ 256， 301， 751， 129， 937， 863， 742， 694，076， 438） 為例 ， 分別寫出執(zhí)行以下算法的 各趟 排序結束時 ， 關鍵字序列的狀態(tài) ， 并說明這些排序方法中 ， 哪些易于在鏈表 （ 包括各種單 、 雙 、 循環(huán)鏈表 ） 上實現(xiàn) ？ ① 直接插入排序 ② 希爾排序 （ 取 dk=5,3,1） P, Q, R, A, D, H, C, F, M, S, X , Y 答： 顯然，直接插入排序方法易于在鏈表上實現(xiàn)；但希爾排序方法因為是按增量選擇記錄，不易于在鏈表上實現(xiàn)。 交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 交換排序的基本思想是： 28 1) 冒泡排序 基本思路： 每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。 前提： 順序存儲結構 例： 關鍵字序列 T=(21， 25， 49， 25*， 16， 08），請寫出冒泡排序的具體實現(xiàn)過程。 ?最壞情形： 初始排列逆序， 算法要執(zhí)行 n1趟起泡，第 i趟(1? i? n) 做了 n i 次關鍵碼比較，執(zhí)行了 ni 次對象交換。此時便為有序序列了。 21， 25， 49， 25*， 16， 08 初態(tài)： 第 1趟： 第 2趟： 第 3趟： 討論： 1. 這種不斷劃分子表的過程，計算機如何自動實現(xiàn)？ 2. “快速排序 ” 是否真的比任何排序算法都快？ 08， 16， 21， 25， 25*， (49) 21 16， 08 ， ( ) 25， 25*， 49 (08)， 16， 21， 25， (25*， 49) 32 ，計算機如何自動實現(xiàn)？ 編程時： ①每一趟的子表的形成是采用從兩頭向中間交替式逼近法； ②由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。L,int low,int high){ //一趟快排 //交換子表 r[low… high]的記錄，使支點（樞軸）記錄到位，并返回其位置。 r[0]=r[low]。 //取支點的關鍵碼存入 pivotkey變量 while(low high){ //從表的兩端交替地向中間掃描 while(lowhigh amp。 r[high].key=pivotkey ) high。 //將比支點小的記錄交換到低端； while(lowhigh amp。 r[low].key=pivotkey) + +low。 //將比支點大的記錄交換到高端； } r[low]=r[0]。 //返回支點記錄所在位置。 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)定 ！ 35 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 一趟快速排序算法流程圖 36 void QSort ( SqList amp。 QSort ( L, low, pivot1)。 } } 整個快速排序的遞歸算法： 見教材 P276 //長度 1 //對順序表 L中的子序列 r[ low… high] 作快速排序 //一趟快排，將 r[ ]一分為二 //在左子區(qū)間進行遞歸快排，直到長度為 1 //在右子區(qū)間進行遞歸快排，直到長度為 1 //QSort 新的 low void QuickSort ( SqList amp。 } 對順序表 L進行快速排序的操作函數為： 37 例 3： 以關鍵字序列（ 256， 301， 751， 129， 937， 863， 742，694， 076， 438）為例，寫出執(zhí)行快速算法的 各趟 排序結束時，關鍵字序列的狀態(tài)。 38 快速排序算法詳細分析： ?快速排序是遞歸的，需要有一個棧存放每層遞歸調用時的指針和參數 （新的 low和 high） 。 實驗結果表明：就平均計算時間而言，快速排序是我們所討論的所有內排序方法中最好的一個 。因此，要求存儲開銷為 o(log2n)。此時，快速排序的趟數最少。這樣，必須經過 n1 趟才能把所有對象定位，而且第 i 趟需要經過 ni 次關鍵碼比較才能找到第 i 個對象的安放位置，總的關鍵碼比較次數將達到 n2/2 ? 快速排序是一個 不穩(wěn)定 的排序方法 40 討論 2. “快速排序 ” 是否真的比任何排序算法都快？ 設每個子表的支點都在中間（比較均衡），則： 第 1趟比較，可以確定 1個元素的位置； 第 2趟比較（ 2個子表），可以再確定 2個元素的位置； 第 3趟比較（ 4個子表），可以再確定 4個元素的位置； 第 4趟比較（ 8個子表），可以再確定 8個元素的位置； …… 只需 ?log2n? ＋ 1趟便可排好序。 教材 P276有證明：快速排序的平均排序效率為 O(nlog2n)； 但最壞情況 (例如已經有序 )下仍為 O(n2),改進措施見 P277。待到第 n2 趟作完 , 待排序對象只剩下 1個 , 就不用再選了。 ③ 在這組對象中剔除這個具有最小排序碼的對象 。 ? 直接選擇排序是一種簡單的排序方法 , 它的基本步驟是： ① 在一組對象 V[i]～ V[n1] 中選擇具有最小排序碼的對象； 直接選擇排序 (Select Sort) 43 21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 0 49 25 16 25 16 08 49 08 25* 49 21 i = 1 i = 2 08 16 25* 25 21 初始 最小者 08 交換 21,08 最小者 16 交換 25,16 最小者 21 交換 49,21 44 49 25* 0 1 2 3 4 5 25* i = 4 25 16 08 49 25* 49 21 結果 i = 3 08 16 25 21 最小者 25* 無交換 最小者 25 無交換 25 21 16 08 各趟排序后的結果 45 直接選擇排序的算法 typedef int SortData。 i n1。 //選擇具有最小排序碼的對象 for ( int j = i+1。 j++) if ( V[j] V[k] ) k = j。 } } 46 0 1 2 3 4 5 49 16 08 25* 49 21 08 25* 25 21 i =1時選擇排序的過程 i k j 49 25 08 25* 16 21 i k j 49 ? 25 25* ? 25 16 25 i k j 16 25 47 49 25 08 25* 16 21 0 1 2 3 4 5 i k j 21 ? 16 k 指示當前序列中最小者 ? 直接選擇排序的 排序碼比較次數 KCN 與對象的初始排列無關?？偟呐判虼a比較次數為 ???????? 20 211ninninKCN )()(48 錦標賽排序 (Tournament Tree Sort) ? 它的思想與體育比賽時的淘汰賽類似。然后對這 ?n/2? 個對象再進行關鍵碼的兩兩比較， … ，如此重復，直到選出一個關鍵碼最小的對象為止。 49 ? 如果 n 不是 2的 k 次冪 ， 則讓葉結點數補足到滿足 2k1 n ? 2k 的 2k個 。 最頂層是樹的根 。 ? 位于最底層的葉結點叫做勝者樹的外結點 ， 非葉結點稱為勝者樹的內結點 。 ? 勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關鍵碼的對象。 //數據值 int index。 //參選標志： =1, 參選 , =0, 不參選 } 錦標賽排序的算法 template class Type void TournamentSort ( Type a[ ], int n ) { DataNodeType *tree。 58 int bottomRowSize = PowerOfTwo ( n )。 //總結點個數 int loadindex = bottomRowSize1。 int j = 0。 i TreeSize。 if ( j n ) { tree[i].active = 1。 } else tree[i].active = 0。 //進行初始比較選擇最小的項 while ( i ) { 59 j = i。 else tree[(j1)/2] = tree[j+1]。 } i = (i1)/2。 i n1。 //送出最小數據 tree[tree[0].index].active = 0。 //調整 } a[n1] = tree[0].data。 //i偶數 , 對手左結點 else tree[(i1)/2] = tree[i+1]。 //向上調整 61 while ( i ) { //直到 i==0 if ( i %2 == 0) j = i1。 if ( !tree[i].active || !tree[j].active ) if ( tree[i].active ) tree[(i1)/2] = tree[i]。 //否則 , j上 else //兩方都可參選 if ( tree[i].data tree[j].data ) tree[(i1)/2] = tree[i]。 i = (i1) / 2。 ? 除第一次選擇具有最小關鍵碼的對象需要進行 n1 次關鍵碼比較外，重構勝者樹選擇具有次小、再次小關鍵碼對象所需的關鍵碼比較次數均為 O(log2n)。 ? 對象的移動次數不超過關鍵碼的比較次數，所以錦標賽排序總的時間復雜度為 O(nlog2n)。 63 ? 如果有 n 個對象，必須使用至少 2n1 個結點來存放勝者樹。每個結點包括關鍵碼、對象序號和比較標志三種信息。 64 堆排序 (Heap Sort) ? 利用堆及其運算，可以很容易地實現(xiàn)選擇排序的思路。 65 建立初始的最大堆 21 25 25* 49 16 08 1 2 3 4 5 6 i 21 25 25*