數(shù)據(jù)結(jié)構(gòu)第3章內(nèi)部排序課件

1、第三章 內(nèi)部排序主要教學目標： 掌握插入排序、交換排序、選擇排序、歸并排序的方法及其時間復雜度分析；了解基數(shù)排序方法及其性能分析方法理解教學方法及教學手段： 理論講授與上機實踐相結(jié)合教學重點及難點：各種排序算法及時間復雜度分析排序定義將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列叫排序分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對外存進行訪問的排序按穩(wěn)定性穩(wěn)定的 若ki=kj,（ij）若排序后一定ij不穩(wěn)定的若ki=kj,（ij）若排序后不一定ij按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排

2、序：簡單選擇排序、堆排序歸并排序：2-路歸并排序,多路歸并基數(shù)排序排序基本操作比較兩個關鍵字大小將記錄從一個位置移動到另一個位置直接插入排序排序過程：整個排序過程為n-1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序算法描述：void insertion_sort(int a ,int n) int i,j,t; for(i=1;i=0&taj;j-)aj+1=aj;aj+1=t; 3.1 插入排序例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97

3、 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)排序結(jié)果：算法評價時間復雜度若待排序記錄按關鍵字從小到大排列(正序)關鍵字比較次數(shù)：記錄移動次數(shù)：若待排序記錄按關鍵字從大到小排列(逆序)關鍵字比較次數(shù)：記錄移動次數(shù)：若待排序記錄是隨機的，取平均值關鍵字比較次數(shù)：記錄移動次數(shù)：T(n)=O(n)空間復雜度

4、：S(n)=O(1)穩(wěn)定性：穩(wěn)定折半插入排序排序過程：用折半查找方法確定插入位置的排序叫例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 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

5、70 85 )算法描述算法評價時間復雜度：T(n)=O(n)空間復雜度：S(n)=O(1)Ch8_2.c排序過程首先通過n-1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換再通過n-2次比較，從剩余的n-1個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換重復上述操作，共進行n-1趟排序后，排序結(jié)束3.2 選擇排序例初始： 49 38 65 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

6、四趟： 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 97算法描述:void selection_sort(int a ,int n) int i,j,k; for(i=0;in-1;i+) k=i; for(j=i+1;jaj) k=j;t=ai;ai=ak;ak=t; 算法評價時間復雜度T(n)=O(n)空間復雜度S(n)=O(1)記錄移動次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)：穩(wěn)定性：不穩(wěn)定排序過程將第一個記錄的關鍵字與第二個記錄的關鍵字

7、進行比較，若為逆序a0a1，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止第一趟冒泡排序，結(jié)果關鍵字最大的記錄被安置在最后一個記錄上對前n-1個記錄進行第二趟冒泡排序，結(jié)果使關鍵字次大的記錄被安置在第n-1個記錄位置重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止3.3 冒泡排序例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第五趟1

8、3 27 30第六趟38497697139727973097137676762730136527653065131349493049273827383038算法描述:void bubble_sort(int a ,int n) int i,j,t,tag=1; for(i=0;in-1&tag=1;i+)tag=0; for(j=0;jaj+1) t=aj; aj=aj+1; aj+1=t;tag=1; 算法評價時間復雜度 T(n)=O(n)最好情況（正序）比較次數(shù)：n-1移動次數(shù)：0最壞情況（逆序）比較次數(shù)：移動次數(shù)：空間復雜度：S(n)=O(1)穩(wěn)定性：穩(wěn)定排序過程：先取一個正整數(shù)d1n，

9、把所有相隔d1的記錄放一組，組內(nèi)進行直接插入排序；然后取d2d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止。增量常用公式：di+1=|di/2|3.4希爾排序(縮小增量法)取d3=1三趟分組：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例 初始：49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分組：49 38 65 97 76 13 27

10、 48 55 4取d2=3二趟分組：13 27 48 55 4 49 38 65 97 76算法描述Ch8_3.c例49 38 65 97 76 13 27 48 55 4#define T 3int d=5,3,1;ji49133827一趟排序：13 27 48 55 4 49 38 65 97 76jiji274jiji55ji38jijiji二趟排序：13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji764希爾排序特點子序列的構(gòu)成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列希爾排序可提高排序速度，因為分組后n值減小，n更小，而T(n

11、)=O(n),所以T(n)從總體上看是減小了關鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序增量序列取法無除1以外的公因子最后一個增量值必須為1穩(wěn)定性不穩(wěn)定歸并將兩個或兩個以上的有序表組合成一個新的有序表，叫有序結(jié)點序列的合并算法描述：1. i=l,j=m+1,k=l2.當i=m且j=n時若aiaj bk=bj,j+,k+3.若i=m 則bk=ai,i+,k+4.若j=n 則bk=bj,j+,k+3.5 合并排序（歸并排序）兩路合并排序排序過程設初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1兩兩合并，得到n/2個長度為2或1的有序子序列再兩兩合

12、并，如此重復，直至得到一個長度為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算法描述算法評價時間復雜度：T(n)=O(nlog2n)空間復雜度：S(n)=O(n)穩(wěn)定性：穩(wěn)定Ch8_9.c基本思想：通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄進行排序，以達到整個序列有序。排序過程：對alowup中記錄進行一趟快速排序，附設兩個指針i和

13、j，設樞軸記錄t=alow初始時令i=low,j=up首先從j所指位置向前搜索第一個關鍵字小于t的記錄，并放在i位置上，i指針加1再從i所指位置起向后搜索，找到第一個關鍵字大于t的記錄，并放在j位置上，j指針加1重復上述兩步，直至i=j為止，將t放在i(j)上再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄為止3.6 快速排序例初始關鍵字： 49 38 65 97 76 13 27 50 ijtji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 2

14、7 38 49 50 65 76 97ijijij65ji13ij97ij=492749算法描述void quick(int a ,int low,int up) int i,j,t;if(lowup)i=low,j=up,t=alow;while(i!=j)while(it) j-;if(ij) ai+=aj;while(ij&ai=t) i+if(ij) aj-=ai;ai=t;quick(a,low,i-1);quick(a,i+1,up);算法評價時間復雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n)空間

15、復雜度：需?？臻g以實現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)T(n)=O(n)多關鍵字排序定義：例 對52張撲克牌按以下次序排序：23A23A23A23A兩個關鍵字：花色（ ） 面值（23A）并且“花色”地位高于“面值”多關鍵字排序方法最高位優(yōu)先法（MSD)：先對最高位關鍵字k1（如花色）排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復，直至就每個子序列對最低位關鍵字kd排序；最后將所有子序列依次連接在一起成為一個有序序列3.6 基數(shù)排序最低位優(yōu)先法(LSD)：從最低位關鍵字kd起

16、進行排序，然后再對高一位的關鍵字排序，依次重復，直至對最高位關鍵字k1排序后，便成為一個有序序列MSD與LSD不同特點按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序按LSD排序，不必分成子序列，對每個關鍵字都是整個序列參加排序；并且可不通過關鍵字比較，而通過若干次分配與收集實現(xiàn)排序鏈式基數(shù)排序基數(shù)排序：借助“分配”和“收集”對單邏輯關鍵字進行排序的一種方法鏈式基數(shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序鏈式基數(shù)排序步驟設置10個隊列，fi和ei分別為第i個隊列的頭指針和尾指針第一趟分配對最低位關鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關

17、鍵字的個位相同第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表重復上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位進行，最后得到一個有序序列例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505

18、269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：算法描述算法評價時間復雜度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n記錄數(shù) d關鍵字數(shù) rd關鍵字取值范圍 空間復雜度：S(n)=2rd個隊列指針+n個指針域空間Ch8_10.c初始狀態(tài)：1278109063