數(shù)據(jù)結(jié)構(gòu)(c語言版)通用通用課件_第八章_排序_(嚴(yán)蔚敏吳偉民編_清華大學(xué)出版社)PPT通用課件

1、第八章 排序排序定義將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列叫排序分類v按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對(duì)外存進(jìn)行訪問的排序v按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡單選擇排序、堆排序歸并排序：2-路歸并排序基數(shù)排序v按排序所需工作量簡單的排序方法：T(n)=O(n)先進(jìn)的排序方法：T(n)=O(logn) 基數(shù)排序：T(n)=O(d.n)排序基本操作v比較兩個(gè)關(guān)鍵字大小v將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置v8.1 插入排序直接插入排序v排序過程：整個(gè)排序過程為n-1趟

2、插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序v算法描述例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序

3、結(jié)果：v算法評(píng)價(jià)時(shí)間復(fù)雜度v若待排序記錄按關(guān)鍵字從小到大排列(正序)Y關(guān)鍵字比較次數(shù)：112nniY記錄移動(dòng)次數(shù)：)1(222nniv若待排序記錄按關(guān)鍵字從大到小排列(逆序)Y關(guān)鍵字比較次數(shù)：2)1)(2(2nniniY記錄移動(dòng)次數(shù)：2)1)(4()1(2nniniv若待排序記錄是隨機(jī)的，取平均值Y關(guān)鍵字比較次數(shù)：42nY記錄移動(dòng)次數(shù)：42nT(n)=O(n)空間復(fù)雜度：S(n)=O(1)Ch8_1.c折半插入排序v排序過程：用折半查找方法確定插入位置的排序叫例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6

4、 13 30 39 42 70 85 ) 20.i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )v算法描述v算法評(píng)價(jià)時(shí)間復(fù)雜度：T(n)=O(n)空間復(fù)雜度：S(n)=O(1)Ch8_2.c希爾排序(縮小增量法)v排序過程：先取一個(gè)正整數(shù)d1n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2

5、r2.key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止例49 38 65 97 76 13 27 30初始關(guān)鍵字38 49 65 76 13 27 30 97第一趟38 49 65 13 27 30 76第二趟38 49 13 27 30 65第三趟38 13 27 30 49第四趟13 27 30 38第五趟13 27 30第六趟38497

6、697139727973097137676762730136527653065131349493049273827383038v算法描述v算法評(píng)價(jià)時(shí)間復(fù)雜度v最好情況（正序）Y比較次數(shù)：n-1Y移動(dòng)次數(shù)：0v最壞情況（逆序）Y比較次數(shù)：)(21)(211nninniY移動(dòng)次數(shù)：)(23)(321nninni空間復(fù)雜度：S(n)=O(1)T(n)=O(n)Ch8_4.c快速排序v基本思想：通過一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序v排序過程：對(duì)rst中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，

7、設(shè)樞軸記錄rp=rs，x=rp.key初始時(shí)令i=s,j=t首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并和rp交換再從i所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄，和rp交換重復(fù)上述兩步，直至i=j為止再分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 974927ijijij4

8、965ji1349ij4997ijv算法描述v算法評(píng)價(jià)時(shí)間復(fù)雜度v最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)v最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n)空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸v最壞情況：S(n)=O(n)v一般情況：S(n)=O(log2n)T(n)=O(n)Ch8_5.cv8.3 選擇排序簡單選擇排序v排序過程首先通過n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換再通過n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束例初始： 49 38 65

9、 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序結(jié)束： 13 27 38 49 65 76 97v算法描述v算法評(píng)價(jià)時(shí)間復(fù)雜度v記錄移動(dòng)次數(shù)Y最好情況：0Y最壞情況：3(n-1)v比較次數(shù)：)(21)(211nninni空間復(fù)雜度：S(n)=O(1)T(n)

10、=O(n)Ch8_6.c堆排序v堆的定義：n個(gè)元素的序列(k1,k2,kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9） 例 （13，38，27，50，76，65，49，97）962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個(gè)元素的最小值或最大值v堆排序：將無序序列建成一個(gè)堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1個(gè)元素重又建成一個(gè)堆，則可得到n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列

11、，這個(gè)過程叫v堆排序需解決的兩個(gè)問題：如何由一個(gè)無序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？v第二個(gè)問題解決方法篩選方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738769713輸出：

12、13 27 384965502738769713輸出：13 27 387665502738499713輸出：13 27 38 495065762738499713輸出：13 27 38 499765762738495013輸出：13 27 38 49 506597762738495013輸出：13 27 38 49 509765762738495013輸出：13 27 38 49 50 657665972738495013輸出：13 27 38 49 50 659765762738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38

13、49 50 65 76 97算法描述v第一個(gè)問題解決方法方法：從無序序列的第n/2個(gè)元素（即此無序序列對(duì)應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選例 含8個(gè)元素的無序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097算法描述v算法評(píng)價(jià)時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)空間復(fù)雜度：S(n)=O(1)Ch8_7.cv8.4 歸并排序歸并將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表，叫2-路歸并排序

14、v排序過程設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列，每個(gè)子序列長度為1兩兩合并，得到n/2個(gè)長度為2或1的有序子序列再兩兩合并，如此重復(fù)，直至得到一個(gè)長度為n的有序序列為止例初始關(guān)鍵字： 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算法描述v算法評(píng)價(jià)時(shí)間復(fù)雜度：T(n)=O(nlog2n)空間復(fù)雜度：S(n)=O(n)Ch8_9.cv8.5 基數(shù)排序多關(guān)鍵字排序v定義：例 對(duì)52張撲克牌按以下次序排序：23A23A23A23A兩個(gè)

15、關(guān)鍵字：花色（ ） 面值（23A）并且“花色”地位高于“面值”v多關(guān)鍵字排序方法最高位優(yōu)先法（MSD)：先對(duì)最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個(gè)有序序列最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字排序，依次重復(fù)，直至對(duì)最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列MSD與LSD不同特點(diǎn)v按MSD排序，必須將序列逐層分割成若干子序列，然后對(duì)各子序列分別排序v按LSD排序

16、，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序鏈?zhǔn)交鶖?shù)排序v基數(shù)排序：借助“分配”和“收集”對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種方法v鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序v鏈?zhǔn)交鶖?shù)排序步驟設(shè)置10個(gè)隊(duì)列，fi和ei分別為第i個(gè)隊(duì)列的頭指針和尾指針第一趟分配對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至10個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對(duì)十位、百位進(jìn)行，最

17、后得到一個(gè)有序序列例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：算法描述v算法評(píng)價(jià)時(shí)間復(fù)雜度：v分配：T(n)=O(n)v收集：T(