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

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

2、序：簡(jiǎn)單選擇排序、堆排序歸并排序：2-路歸并排序,多路歸并基數(shù)排序排序基本操作比較兩個(gè)關(guān)鍵字大小將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置直接插入排序排序過(guò)程：整個(gè)排序過(guò)程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序算法描述：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é)果：算法評(píng)價(jià)時(shí)間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：若待排序記錄是隨機(jī)的，取平均值關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：T(n)=O(n)空間復(fù)雜度

4、：S(n)=O(1)穩(wěn)定性：穩(wěn)定折半插入排序排序過(guò)程：用折半查找方法確定插入位置的排序叫例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 )算法描述算法評(píng)價(jià)時(shí)間復(fù)雜度：T(n)=O(n)空間復(fù)雜度：S(n)=O(1)Ch8_2.c排序過(guò)程首先通過(guò)n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換再通過(guò)n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換重復(fù)上述操作，共進(jìn)行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; 算法評(píng)價(jià)時(shí)間復(fù)雜度T(n)=O(n)空間復(fù)雜度S(n)=O(1)記錄移動(dòng)次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)：穩(wěn)定性：不穩(wěn)定排序過(guò)程將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字

7、進(jìn)行比較，若為逆序a0a1，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類(lèi)推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置重復(fù)上述過(guò)程，直到“在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作”為止3.3 冒泡排序例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第五趟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; 算法評(píng)價(jià)時(shí)間復(fù)雜度 T(n)=O(n)最好情況（正序）比較次數(shù)：n-1移動(dòng)次數(shù)：0最壞情況（逆序）比較次數(shù)：移動(dòng)次數(shù)：空間復(fù)雜度：S(n)=O(1)穩(wěn)定性：穩(wěn)定排序過(guò)程：先取一個(gè)正整數(shù)d1n，

9、把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹?。增量常用公式：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希爾排序特點(diǎn)子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列希爾排序可提高排序速度，因?yàn)榉纸M后n值減小，n更小，而T(n

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

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

13、j，設(shè)樞軸記錄t=alow初始時(shí)令i=low,j=up首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于t的記錄，并放在i位置上，i指針加1再?gòu)膇所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于t的記錄，并放在j位置上，j指針加1重復(fù)上述兩步，直至i=j為止，將t放在i(j)上再分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止3.6 快速排序例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijtji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序： ( 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);算法評(píng)價(jià)時(shí)間復(fù)雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n)空間

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

16、進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字排序，依次重復(fù)，直至對(duì)最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列MSD與LSD不同特點(diǎn)按MSD排序，必須將序列逐層分割成若干子序列，然后對(duì)各子序列分別排序按LSD排序，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過(guò)關(guān)鍵字比較，而通過(guò)若干次分配與收集實(shí)現(xiàn)排序鏈?zhǔn)交鶖?shù)排序基數(shù)排序：借助“分配”和“收集”對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種方法鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序鏈?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)

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

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