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

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

2、插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序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、結果：v算法評價時間復雜度v若待排序記錄按關鍵字從小到大排列(正序)Y關鍵字比較次數(shù)：112nniY記錄移動次數(shù)：)1(222nniv若待排序記錄按關鍵字從大到小排列(逆序)Y關鍵字比較次數(shù)：2)1)(2(2nniniY記錄移動次數(shù)：2)1)(4()1(2nniniv若待排序記錄是隨機的，取平均值Y關鍵字比較次數(shù)：42nY記錄移動次數(shù)：42nT(n)=O(n)空間復雜度：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算法評價時間復雜度：T(n)=O(n)空間復雜度：S(n)=O(1)Ch8_2.c希爾排序(縮小增量法)v排序過程：先取一個正整數(shù)d1n，把所有相隔d1的記錄放一組，組內(nèi)進行直接插入排序；然后取d2

5、r2.key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止第一趟冒泡排序，結果關鍵字最大的記錄被安置在最后一個記錄上對前n-1個記錄進行第二趟冒泡排序，結果使關鍵字次大的記錄被安置在第n-1個記錄位置重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止例49 38 65 97 76 13 27 30初始關鍵字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算法評價時間復雜度v最好情況（正序）Y比較次數(shù)：n-1Y移動次數(shù)：0v最壞情況（逆序）Y比較次數(shù)：)(21)(211nninniY移動次數(shù)：)(23)(321nninni空間復雜度：S(n)=O(1)T(n)=O(n)Ch8_4.c快速排序v基本思想：通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄進行排序，以達到整個序列有序v排序過程：對rst中記錄進行一趟快速排序，附設兩個指針i和j，

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

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

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

11、，這個過程叫v堆排序需解決的兩個問題：如何由一個無序序列建成一個堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？v第二個問題解決方法篩選方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結點，將得到新的堆，稱這個從堆頂至葉子的調(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第一個問題解決方法方法：從無序序列的第n/2個元素（即此無序序列對應的完全二叉樹的最后一個非終端結點）起，至第一個元素止，進行反復篩選例 含8個元素的無序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097算法描述v算法評價時間復雜度：最壞情況下T(n)=O(nlogn)空間復雜度：S(n)=O(1)Ch8_7.cv8.4 歸并排序歸并將兩個或兩個以上的有序表組合成一個新的有序表，叫2-路歸并排序

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

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

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

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