數據結構C語言版CHAP10

1、結束第 1 頁結束第 2 頁第第 十十 章章 排排 序序 第十章第十章 排排 序序 10.1 概述 10.2 插入排序 10.3 交換排序 10.4 選擇排序 10.5 歸并排序結束第 3 頁10.1 10.1 概概 述述學習要點理解排序的定義和各種排序方法的特點；了解各種方法的排序過程及其依據的原則；1理解“穩(wěn)定”或“不穩(wěn)定”的含義；結束第 4 頁10.1 10.1 概概 述述 排序也是數據處理中經常使用的一種操作。例 高考考生信息管理系統(tǒng)提供了將考生按總分排序、按單科排序的功能；1 排序定義 設r1 r2 r3 rn 是n個記錄，k1,k2, k3 kn為它們的關鍵字，排序就是將記錄按關鍵

2、字遞增（或遞減）的次序排列起來。2 分類按記錄的存放位置分類有 內排序：待排記錄放在內存 外排序：待排記錄放在外存按排序原則分類（內排序） 插入排序 交換排序 選擇排序 歸并排序 基數排序結束第 5 頁10.1 10.1 概概 述述穩(wěn)性排序： 在待排記錄序列中，任何兩個關鍵字相同的記錄，用某種排序方法排序后相對位置不變，則稱這種排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。例 設 49,38,65,97,76,13,27,49 是待排序列 排序后:13,27,38,49,49,65,76,97 穩(wěn)定 排序后:13,27,38,49,49,65,76,97不穩(wěn)定穩(wěn)性排序的應用：例 股票交易系統(tǒng) 考慮一種股

3、票交易(清華紫光)） 1）顧客輸入：股東帳號、股票代碼、申購價格、數量，股票交易系統(tǒng)將用戶申購請求插入申購隊列隊尾； 2）股票交易系統(tǒng)按如下原則交易： a）申購價高者先成交 b）申購價相同者按申購時間先后順序成交結束第 6 頁10.1 10.1 概概 述述如何實現股票交易系統(tǒng) ？申購隊列：用線性表表示交易前：將申購隊列按申購價排序，顯然為滿足原則交易b），要求排序方法是穩(wěn)定的申購隊列（09,10),(06,10.5),(033,9.8),(051,10)排序后：(06,10.5),(09,10),(051,10),(033,9.8)4 存貯方式待排序的記錄序列通常有下列三種存貯方法：1）順序表

4、2）靜態(tài)鏈表：在排序過程，只需修改指針，不需要移動記錄；3）待排記錄本身有放在連續(xù)單元中，同時另建一索引表用于存放各記錄存貯位置；排序時不移過記錄本身，而移動索引表中的記錄“地址”，在排序結束后再按地址調整記錄的存貯位置結束第 7 頁10.1 10.1 概概 述述5 約定在本章中1)為簡潔起見，對待排記錄只寫出其關鍵字序列 如對待排記錄（(09,10),(06,10.5),(033,9.8),(051,10)只寫出其關鍵字序列（10，10.5，9.8，10）2）將按關鍵字遞增的順序排序結束第 8 頁10.1 10.1 概概 述述3)待排序記錄用順序表存儲順序表類型說明#define maxsi

5、ze 20 /一個用作示例的小順序表的最大長度typedef int keytype; /定義關鍵字類型為整數類型typedef structkeytype key; /關鍵字項infotype otherinfo; /其它數據項redtype; /記錄類型typedef structredtype rmaxsize+1; /r0閑置或用作哨兵單元int length; /順序表長度sqlist; /順序表類型結束第 9 頁10.1 10.1 概概 述述 6 本課程介紹如下幾種排序方法 插入排序 交換排序 選擇排序 歸并排序 結束第 10 頁10.2 10.2 插入排序插入排序基本思想 依次將

6、待排記錄插入到有序子表中，并使插入子表后仍保持有序，直到全部記錄插入完畢；初始時，有序子表中只有一個元素。直接插入排序插入排序的關鍵：如何查找插入位置。直接插入排序（也稱為順序插入排序）是用順序查找法定位插入位置。若采用二分查找法定位插入位置則得到另一種插入算法，二分插入排序 例：待排記錄 49 38 65 97 76 13 27 49 （49）38 65 97 76 13 27 49 （38 49）65 97 76 13 27 49 （38 49 65）97 76 13 27 49 （38 49 65 97） 76 13 27 49 （38 49 65 76 97）13 27 49 （13

7、38 49 65 76 97）27 49 （13 27 38 49 65 76 97）49 （13 27 38 49 49 65 76 97）一趟直接插入排序結束第 11 頁10.2 10.2 插入排序插入排序void insertsort(sqlist &l) /對順序表l作直接插入排序。for (i=2; i=l. length; +i) if lt(l.ri.key, l.ri-1.key) /若l.ri.key l.ri-1.key，需將l.ri插入有序子表， l.r0=l.ri; / l.ri復制為哨兵 for(j=i-1; lt(l.r(0).key, l.rj.key); -j

8、) /從后向前查找子表 l.rj+1=l.rj; / 若l.ri.key l.rj.key， l.rj記錄后移 l.rj+1=l.r0; /插入到正確位置/insertsort 49 38 65 76 97 13 27 490 1 2 3 4 5 6 7 8 9 初始時，有序子表中只有一個元素結束第 12 頁10.2 10.2 插入排序插入排序 38 49 65 97 76 13 27 490 1 2 3 4 5 6 7 8 9 l.r0.key l.r4.key， l.r4記錄后移看一下外層for循環(huán) i=5 時算法的執(zhí)行的情況l.r5復制為哨兵 76 38 49 65 97 76 13 2

9、7 490 1 2 3 4 5 6 7 8 9 76 38 49 65 97 97 13 27 490 1 2 3 4 5 6 7 8 9 76 38 49 65 97 97 13 27 490 1 2 3 4 5 6 7 8 9 l.r0.key l.r3.key找到插入位置 76 38 49 65 97 97 13 27 490 1 2 3 4 5 6 7 8 9 l.r5為待插入元素插入！7676結束第 13 頁10.2 10.2 插入排序插入排序 性能分析：基本操作 比較元素：比較、移動元素次數均取決于插入位置 移動元素處理第i個記錄時 待排序列遞增（正向）有序時，比較元素次數最少：1

10、次 待排序列遞減（逆向）有序時，比較元素次數最多：i 次 一般待排序列，平均比較元素次數： (i+1)/2 對n個記錄待排序列,直接插入排序 待排序列正向有序時，比較元素次數最少：n-1次 待排序列逆向有序時，比較元素次數最多：(n+2)(n-1)/2次 一般待排序列，平均比較元素次數大約為：n2/4 類似可分析移動元素次數結束第 14 頁10.2 10.2 插入排序插入排序時間復雜度 待排序列正向有序時 ：0 （n） 待排序列逆向有序時： 0（n2） 一般待排序列：0（n2）特點： 1) 算法簡單 2) 時間復雜度為o（n2 ） 3）初始序列基本（正向）有序時，時間復雜度為o（n） 4）穩(wěn)定

11、排序 該方法適用于記錄基本（正向）有序或n較少的情況結束第 15 頁10.2 10.2 插入排序插入排序四、希爾排序四、希爾排序 直接插入排序法簡單，適用于記錄較少，或待排記錄基本（正向）有序的情況。 基于直接插入排序上是述特點，希爾提出了另一種插入排序算法。1 基本思想：1） 將待排序記分為若干組，在各組內分別進行直接插入排序；2） 作若干次使待排記錄基本有序；3） 對全部記錄進行一次順序插入排序；分組方法：選定一增量d，將間隔為d的記錄作為一組例 待排記錄 49 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 13 27 4

12、9 55 04 49 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 04 49 38 27 49 55 65 97 76 04 13 27 38 49 49 55 65 76 97一趟希爾排序結果兩趟希爾排序結果d=5d=3結束第 16 頁10.2 10.2 插入排序插入排序特點 1）時間復雜度，取決于增量序列的選擇，選擇的好，效率優(yōu)于直接插入排序，其時間復雜度為0（nlog2n） 2）不穩(wěn)定排序方法 3）適用于n 較大情況 結束第 17 頁10.3 10.3 交換排序交換排序一、基本思想： 將待排記錄中兩兩記錄關鍵字進行比較，若逆序而交換位置。 例

13、：49 38 65 97 76 13 27 49 若按關鍵字遞增的順序排序 則49 38 為逆序 不同的比較順序就得到不同的交換排序方法二 起泡排序：順序比較相鄰的兩記錄的關鍵字，若逆序而交換位置三 快速排序1 基本思想1） 選定一記錄r，將所有其他記錄關鍵字k與該記錄關鍵字k比較, 若 kk 則將記錄換至r之后;2） 繼續(xù)對r前后兩部分記錄進行快速排序，直至排序范圍為1;結束第 18 頁10.3 10.3 交換排序交換排序2 基本步驟 為簡潔起見，對待排記錄仍只寫出其關鍵字序列1(一趟快速排序）設被指定的關鍵字為待排序列的第一個關鍵字k ，i指向待排序列的的第一個關鍵字； j指向最后一個關鍵

14、字； 若i j 循環(huán)：1）從后向前將關鍵字與k比較，直至遇到小于k的關鍵字 k，k 前移；2）從前向后將關鍵字與k比較，直至遇到大于k的關鍵字k，k后移；（一趟快速排序后，“小”記錄被移至k 前，“大”的記錄被移至k 后2 繼續(xù)對k前后兩部分關鍵字進行快速排序，直至排序范圍為1;結束第 19 頁10.3 10.3 交換排序交換排序 27 38 65 97 76 13 27 49ii例例 待排記錄 49 38 65 97 76 13 27 49 jj 27 38 65 97 76 13 65 49jj 27 38 13 49 76 97 65 49jji被指定的關鍵字從后向前，將關鍵字與49比較

15、，直至遇到小于49的關鍵字，前移從后向前，將關鍵字與49比較，直至遇到小于49的關鍵字，前移從前向后，將關鍵字與49比較，直至遇到大于49的關鍵字，后移從前向后，將關鍵字與49比較，直至遇到大于49的關鍵字，后移 27 38 13 97 76 13 65 49ii從后向前，將關鍵字與49比較，直至遇到i=j,將49放至i處49一趟快速排序結束結束第 20 頁10.3 10.3 交換排序交換排序 27 27 38 13 38 13 4949 7676 97 65 97 65 4949 1313 27 27 38 38 4949 4949 65 65 76 76 97 97 13 13 27 27

16、 38 38 4949 4949 65 65 7676 97 97 13 27 38 49 49 65 76 97兩趟快速排序結束三趟快速排序結束快速排序結束結束第 21 頁10.3 10.3 交換排序交換排序例例 待排記錄 49 38 65 97 76 13 27 4927 38 13 49 76 97 65 49 27 27 38 13 38 13 4949 7676 97 65 97 65 4949 1313 27 27 38 38 4949 4949 65 65 76 76 97 97 13 13 27 27 38 38 4949 4949 65 65 7676 97 97 13 27

17、 38 49 49 65 76 97兩趟快速排序結果三趟快速排序結果一趟快速排序結果快速排序結束特點： 1) 時間復雜度為0（nlog2n） 2）不穩(wěn)定結束第 22 頁10.4 10.4 選擇排序選擇排序一一 基本思想基本思想在待排記錄中依次選擇關鍵字最小的記錄，逐漸縮小范圍直至全部記錄選擇完畢。二二 簡單選擇排序簡單選擇排序基本步驟1）從左至右掃描待排記錄 ri，ri+1 ，rn（初始.i=1），在已掃描記錄中選擇關鍵字最小者，用j指示；2） r（j）與r（i）交換；3） 縮小范圍 i=i+1；重復1）2）3）直至i=n-1例例 49 38 65 97 76 49 38 65 97 76 1

18、313 27 27 4949 13 13 38 65 97 76 49 38 65 97 76 49 2727 4949 13 2713 27 65 97 76 49 65 97 76 49 3838 4949 13 27 3813 27 38 65 97 76 65 97 76 4949 4949 13 27 38 4913 27 38 49 65 97 76 65 97 76 4949 13 27 38 49 13 27 38 49 4949 6565 97 76 97 76 13 27 38 49 13 27 38 49 4949 65 65 97 97 7676 13 27 38 49 13 27 38 49 4949 65 76 65 76 97 97一趟選擇排序結束結束第 23 頁10.4 10.4 選擇排序選擇排序2 算法void selectsort(sqlist &k) /對順序表l作簡單選擇排序。 for (i=1; il.length; +i) j=selectminkey(l, i); /在l.ri.l.length 中選擇key最小的記錄 if(i!=j)l.ril.rj; /與第個i記錄交換 /for/selectsort3 特點： 1) 算法簡單 2) 時間復雜度為o（n2 ） 3）穩(wěn)定排序結束第 2