數(shù)據(jù)結(jié)構(gòu)第9章

1、9.1 9.1 概述概述9.2 9.2 插入類排序插入類排序9.3 9.3 交換類排序法交換類排序法9.4 9.4 選擇類排序法選擇類排序法9.5 9.5 歸并類排序歸并類排序9.6 9.6 分配類排序分配類排序9.7 9.7 外部排序外部排序第九章第九章 排序排序 9.8 9.8 總結(jié)與提高總結(jié)與提高一、排序的定義一、排序的定義 排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組其目的是將一組“無(wú)序無(wú)序”的記錄序列調(diào)整的記錄序列調(diào)整為為“有序有序”的記錄序列。的記錄序列。例如：例如：將如下序列將如下序列52, 49, 80, 36, 14, 58, 61, 2

2、3, 97, 75調(diào)整為調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 979.1 9.1 排序的基本概念排序的基本概念設(shè)含設(shè)含 n 個(gè)記錄的序列為個(gè)記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 記錄關(guān)鍵字相互之間可以進(jìn)行比較，即存記錄關(guān)鍵字相互之間可以進(jìn)行比較，即存在關(guān)系在關(guān)系 ： Kp1Kp2Kpn按此關(guān)系將上述記錄序列調(diào)整為按此關(guān)系將上述記錄序列調(diào)整為 Rp1, Rp2, ，Rpn 的操作稱作的操作稱作排序。排序。定義：定義： 設(shè)待排序記錄序列中有關(guān)鍵字相設(shè)待排序記錄序列中有關(guān)鍵字相等的記錄等的記錄

3、, 即即ki=kj(ij), 且在排序前且在排序前Ri領(lǐng)先于領(lǐng)先于Rj. 若排序后若排序后可以保證可以保證Ri仍領(lǐng)先于仍領(lǐng)先于Rj, 則則所用的排序方法稱為所用的排序方法稱為穩(wěn)定的穩(wěn)定的; 若排序后若排序后不能保證不能保證Ri仍領(lǐng)先于仍領(lǐng)先于Rj, 則則所用的排序方法稱為所用的排序方法稱為不穩(wěn)定的不穩(wěn)定的.二、穩(wěn)定的排序和不穩(wěn)定的排序二、穩(wěn)定的排序和不穩(wěn)定的排序例如：例如： 排序前排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后必有結(jié)果：若排序后必有結(jié)果： ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是則稱該排序方法是穩(wěn)

4、定穩(wěn)定的的; ;若排序后可能得結(jié)果：若排序后可能得結(jié)果： ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是則稱該排序方法是不穩(wěn)定不穩(wěn)定的。的。 若若整個(gè)排序過(guò)程不需要訪問(wèn)外存整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類排序問(wèn)題便能完成，則稱此類排序問(wèn)題為內(nèi)部為內(nèi)部排序。排序。 反之反之, 若參加排序的記錄數(shù)量很若參加排序的記錄數(shù)量很大大, 整個(gè)序列的排序過(guò)程整個(gè)序列的排序過(guò)程不可能在內(nèi)不可能在內(nèi)存存 中完成中完成，則稱此類排序問(wèn)題，則稱此類排序問(wèn)題為外為外部排序部排序。三、內(nèi)部排序和外部排序三、內(nèi)部排序和外部排序1、順序存儲(chǔ)：移動(dòng)記錄實(shí)現(xiàn)排序；、順序存儲(chǔ)：移

5、動(dòng)記錄實(shí)現(xiàn)排序； 2、(靜態(tài)靜態(tài))鏈表：修改指針鏈表：修改指針(游標(biāo)游標(biāo))實(shí)實(shí) 現(xiàn)排序；現(xiàn)排序； 3、地址向量：移動(dòng)地址實(shí)現(xiàn)排序；、地址向量：移動(dòng)地址實(shí)現(xiàn)排序； (又稱地址排序又稱地址排序) 四、內(nèi)部排序的存儲(chǔ)方式四、內(nèi)部排序的存儲(chǔ)方式 本課程我們重點(diǎn)討論在順序存儲(chǔ)結(jié)構(gòu)本課程我們重點(diǎn)討論在順序存儲(chǔ)結(jié)構(gòu)上，各種排序方法的實(shí)現(xiàn)。上，各種排序方法的實(shí)現(xiàn)。排序算法的性能指標(biāo)n執(zhí)行時(shí)間和所需要的輔助空間n算法本身的復(fù)雜程度9.2 9.2 插入類排序插入類排序 將無(wú)序序列中的記錄將無(wú)序序列中的記錄一個(gè)一個(gè)的一個(gè)一個(gè)的 “插入插入”到有序序列中的到有序序列中的恰當(dāng)恰當(dāng)位置，以位置，以逐漸增加有序序列的長(zhǎng)度逐

6、漸增加有序序列的長(zhǎng)度K(K=1 N),從而實(shí)現(xiàn)排序。從而實(shí)現(xiàn)排序。基本思想：基本思想： 有序序列r1.i-1ri無(wú)序序列 ri.n有序序列r1.i無(wú)序序列 ri+1.n找位置找位置插入插入一趟插入排序的基本過(guò)程：實(shí)現(xiàn)實(shí)現(xiàn)“一趟插入排序一趟插入排序”可分三步進(jìn)行：可分三步進(jìn)行：3插入：插入：將將ri 插入插入(復(fù)制復(fù)制)到到rj+1的的位置上。位置上。2后移：后移：將將rj+1.i-1中的所有記錄均中的所有記錄均后移一個(gè)位置；后移一個(gè)位置；1查找查找插入位置：插入位置：在在r1.i-1中查找中查找ri的插入位置的插入位置j+1 ： r1.j.key ri.key rj+1.i-1.key；直接插

7、入排序直接插入排序（基于順序查找）（基于順序查找）不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）利用 “順序查找順序查找”實(shí)現(xiàn)“在r1.i-1中查找查找ri的插入位置的插入位置”算法的實(shí)現(xiàn)：算法的實(shí)現(xiàn)：一、直接插入排序一、直接插入排序1. 從從ri-1起向前進(jìn)行順序查找，起向前進(jìn)行順序查找， 循環(huán)結(jié)束確定循環(huán)結(jié)束確定ri的插入位置為的插入位置為 j +1;r0jrij=i-1插入位置插入位置2. 將所有將所有 j+1i-1 的記錄向后移動(dòng)的記錄向后移動(dòng) 1位

8、位; jjj3. 將將r0(原原ri)“插入插入”到到j(luò)+1的位置的位置。監(jiān)視哨設(shè)置在監(jiān)視哨設(shè)置在r0； 可以在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；可以在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；r0=ri; for(j=i-1;r0.keyrj.key;j-)； return j+1;r0jrij= i-1上述循環(huán)結(jié)束后可以直接進(jìn)行上述循環(huán)結(jié)束后可以直接進(jìn)行“插入插入”插入位置插入位置方法的改進(jìn)方法的改進(jìn):令令 i = 2,3, n, 可實(shí)現(xiàn)整個(gè)序列的排序。可實(shí)現(xiàn)整個(gè)序列的排序。Void InsertSort(RecordList L, )for(i=2；i=L.length; i+) L.r0=L.ri; fo

9、r(j=i-1;L.r0.keyL.rj.key;j-) L.rj+1=L.rj;L.rj+1=L.r0 ;算法：算法：穩(wěn)定？穩(wěn)定？改進(jìn)后的直接插入排序nvoid InsertSort(RecordList L)for(i=2;i=L.length;i+) if(L.ri.keyL.ri-1.key) L.r0=L.ri; for(j=i-1;L.r0.keyL.rj.key;j+) L.rj+1=L.rj; L.rj+1=L.r0; 實(shí)現(xiàn)內(nèi)部排序的實(shí)現(xiàn)內(nèi)部排序的基本操作基本操作有兩個(gè)：有兩個(gè)：（2）“移動(dòng)移動(dòng)”記錄。記錄。（1）“比較比較”序列中兩個(gè)關(guān)鍵字的序列中兩個(gè)關(guān)鍵字的 大小；大小；時(shí)

10、間復(fù)雜度分析：時(shí)間復(fù)雜度分析：對(duì)于直接插入排序?qū)τ谥苯硬迦肱判颍鹤詈玫那闆r最好的情況(關(guān)鍵字在記錄序列中順序有序關(guān)鍵字在記錄序列中順序有序):“比較比較”的次數(shù)：的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較比較”的次數(shù)：的次數(shù)：0“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)： 1 = n-1ni=2 (i+1) =ni=2(n+4)(n- -1)2 (i+1) =ni=2(n+4)(n- -1)2 所以，時(shí)間復(fù)雜度為所以，時(shí)間復(fù)雜度為O(n2) 因?yàn)橐驗(yàn)?r1.i-1 是一個(gè)按關(guān)鍵字有序是一個(gè)按關(guān)鍵字有序的序列的序列, 則可以利用

11、則可以利用折半查找折半查找實(shí)現(xiàn)在實(shí)現(xiàn)在“r1.i-1中查找中查找 ri的插入位置的插入位置”, 如如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉Ｋ藢?shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。它只能只能減少查找減少查找的次數(shù)的次數(shù)不能減少移動(dòng)不能減少移動(dòng)的次的次數(shù)數(shù), 因此與查找后移同時(shí)實(shí)現(xiàn)的直接插因此與查找后移同時(shí)實(shí)現(xiàn)的直接插入排序比較入排序比較, 改進(jìn)不大。改進(jìn)不大。自學(xué)！自學(xué)！ 二、折半插入排序二、折半插入排序ilowhighmmlowlowhighilowhighmhighmhighmlow例如例如:再如再如:插入插入位置位置插入插入位置位置14 36 49 52 80 58 61 23 97 75L.r14

12、36 49 52 58 61 80 23 97 75L.rm折半插入排序算法 void BiInsertSort(RecordList L) for(i=2;i=L.length;i+) if(L.ri.keyL.ri-1.key) L.r0=L.ri; low=1；high=i-1； while(low=high) mid=(low+high)/2; if(L.r0.key=low;j-) L.rj+1=L.rj; L.rlow=L.r0; 由于由于插入排序的效率取決于插入排序的效率取決于:記錄的個(gè)數(shù)記錄的個(gè)數(shù)及記錄的原始序；及記錄的原始序； “宏觀宏觀”調(diào)整調(diào)整：先先“跳躍式跳躍式”的分組

13、進(jìn)行排序的分組進(jìn)行排序, 使得整個(gè)序列使得整個(gè)序列“基本有序基本有序”。(每組記錄少每組記錄少) “微觀微觀”調(diào)整調(diào)整：在整個(gè)序列在整個(gè)序列“基本有序基本有序”后后, 再進(jìn)行直接插入排序使整個(gè)序列再進(jìn)行直接插入排序使整個(gè)序列“完全有完全有序序”。（記錄的原始序。（記錄的原始序優(yōu)優(yōu)）三三、希爾排序希爾排序(縮小增量排序縮小增量排序)所以所以希爾排序的基本思想為：希爾排序的基本思想為：對(duì)待排記錄對(duì)待排記錄序列先作序列先作“宏觀宏觀”調(diào)整，再作調(diào)整，再作“微觀微觀”調(diào)整。調(diào)整。將記錄序列將記錄序列跳躍式的跳躍式的分成若干組，分別對(duì)每組進(jìn)分成若干組，分別對(duì)每組進(jìn)行行插入排序，組數(shù)不斷減少，最后僅剩一組

14、。插入排序，組數(shù)不斷減少，最后僅剩一組。其中其中, d 稱為增量稱為增量, 它的值在排序過(guò)程中從它的值在排序過(guò)程中從大到小逐漸縮小大到小逐漸縮小, ,直至最后一趟排序直至最后一趟排序減為減為 1 . . 例如：將例如：將 n 個(gè)記錄個(gè)記錄 r1, r2rd, r1+d,r2+dr2d, r1+2d rn 分成分成 d 個(gè)子序列：個(gè)子序列： r1， r1+d， r1+2d， , r1+kd r2， r2+d， r2+2d， , r2+kd rd, r2d, r3d, , r(k+1)d 具體做法：具體做法：例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序，設(shè)增

15、量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 希爾排序算法 void ShellInsert(RecordList L, int dk) for(i=dk+1;i=L.length;i+) if(L.ri.key0&(L.r0.keyL.rj.key);j-=dk) L.rj+dk=L.rj; L.rj+dk=L.r0; nvoid ShellSort(Recor

16、dList L, int dlta, int t) for(k=0;kL.length;t+) ShellInsert(L,dltak); 希爾排序的時(shí)間復(fù)雜度分析是一個(gè)希爾排序的時(shí)間復(fù)雜度分析是一個(gè)數(shù)學(xué)上尚未解決的難題。數(shù)學(xué)上尚未解決的難題。增量序列增量序列d1.t的設(shè)計(jì)至關(guān)重要，目前沒有統(tǒng)一的設(shè)計(jì)至關(guān)重要，目前沒有統(tǒng)一定論，以經(jīng)驗(yàn)為主。定論，以經(jīng)驗(yàn)為主。 以經(jīng)驗(yàn)，當(dāng)以經(jīng)驗(yàn)，當(dāng)n在一定范圍內(nèi)時(shí)，在一定范圍內(nèi)時(shí)，希爾希爾排序的比較與移動(dòng)次數(shù)約為：排序的比較與移動(dòng)次數(shù)約為：n1.3,當(dāng)當(dāng)n時(shí)時(shí):比較與移動(dòng)次數(shù)約為比較與移動(dòng)次數(shù)約為n(log2n)2。9.3 9.3 交換類排序法交換類排序法一、一

17、、 起泡排序起泡排序二、二、 快速排序快速排序三、三、 快速排序的時(shí)間分析快速排序的時(shí)間分析假設(shè)在排序過(guò)程中，記錄序列假設(shè)在排序過(guò)程中，記錄序列r1.n的狀態(tài)為：的狀態(tài)為：一一 趟起泡排序趟起泡排序無(wú)序序列r1.i有序序列 ri+1.ni無(wú)序序列r1.i-1有序序列 ri.n對(duì)無(wú)序序列，比較對(duì)無(wú)序序列，比較(交交換換)相鄰記錄，可將關(guān)相鄰記錄，可將關(guān)鍵字最大的記錄鍵字最大的記錄交換交換到到 i 的位置上的位置上有序序列大于無(wú)序序列有序序列大于無(wú)序序列一、一、 起泡排序起泡排序算法一：void BubbleSort(RecordList L); flag=1; for( i=1; i=L.len

18、gth-1&flag; i+) flag=0; flag=1; for (j=1; jL.length-i ; j+) if (L.rj+1.key 1) laste:=1; for (j=1; ji; j+) if (rj+1.key rj.key) x=rj; rj=rj+1; rj+1=x; laste:= j; 記下進(jìn)行交換的記錄位置記下進(jìn)行交換的記錄位置 i:= laste; 本趟最后一次進(jìn)行交換的記錄位置本趟最后一次進(jìn)行交換的記錄位置 5231978注意注意: :2. 算法一每經(jīng)過(guò)一趟“起泡”則“i i減1”， 但算法二并不是每趟如此。例如例如:25531579 89i=7

19、i=613i=21. 起泡排序的結(jié)束條件為， 最后一趟沒有進(jìn)行最后一趟沒有進(jìn)行“交換記錄交換記錄”。lastelaste1132最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進(jìn)行一趟起泡只需進(jìn)行一趟起泡“比較比較”的次數(shù)：的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： 需進(jìn)行需進(jìn)行n-1趟起泡趟起泡“比較比較”的次數(shù)：的次數(shù)：0“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：n-1(i -1) =ni=2n (n-1)23(i -1) =ni=23n (n-1)2 所以，時(shí)間復(fù)雜度為所以，時(shí)間復(fù)雜

20、度為O(n2)時(shí)間分析時(shí)間分析: : 起泡排序一趟之后，使最大的記錄定起泡排序一趟之后，使最大的記錄定位到位到最后最后,如果一趟之后可使某記錄如果一趟之后可使某記錄(任意任意)定位在它定位在它應(yīng)處的位置應(yīng)處的位置(在有序序列中在有序序列中),而而將其余的無(wú)序序列以它為將其余的無(wú)序序列以它為樞軸樞軸,分成兩部分成兩部分分,比它小的放在它的前面比它小的放在它的前面,比它大的的放比它大的的放在它的后面在它的后面,下一趟分別對(duì)前后的子序列下一趟分別對(duì)前后的子序列排序排序,顯然可加快速度。顯然可加快速度。這就是快速排序這就是快速排序二、快速排序二、快速排序目標(biāo)：目標(biāo)：找一個(gè)記錄，找一個(gè)記錄，以它的關(guān)鍵字

21、作為以它的關(guān)鍵字作為“樞軸樞軸”，凡凡關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均的記錄均移移動(dòng)至該記錄之前，動(dòng)至該記錄之前，反之，凡反之，凡關(guān)鍵字大于樞關(guān)鍵字大于樞軸軸的記錄均的記錄均移動(dòng)至該記錄之后移動(dòng)至該記錄之后。致使致使一趟排序一趟排序之后，記錄的無(wú)序序列之后，記錄的無(wú)序序列rs.t將將分割成兩部分分割成兩部分：rs.i-1和和ri+1.t，且且 rj.key ri.key rj.key (sji-1) 樞軸樞軸 (i+1jt)。一趟快速排序（一次劃分）一趟快速排序（一次劃分）lowhigh設(shè)設(shè) rs=52 為樞軸為樞軸 將將 rhigh.key 和樞軸的關(guān)鍵字進(jìn)行比較，和樞軸的關(guān)鍵字進(jìn)行比較

22、， 要求要求 rhigh.key 樞軸的關(guān)鍵字樞軸的關(guān)鍵字 將將 rlow.key 和和 樞軸的關(guān)鍵字進(jìn)行比較，樞軸的關(guān)鍵字進(jìn)行比較， 要求要求 rlow.key 樞軸的關(guān)鍵字樞軸的關(guān)鍵字highlowhighlow52498036145861972375strs 52highhighhighlowlow23801452例如例如可見，經(jīng)過(guò)可見，經(jīng)過(guò)“一次劃分一次劃分”，將關(guān)鍵字序列，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 變?yōu)樽優(yōu)? 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過(guò)程中，設(shè)立了兩個(gè)指針：

23、在調(diào)整過(guò)程中，設(shè)立了兩個(gè)指針： low 和和high，它們的初值分別為：，它們的初值分別為： s 和和 t， 之后逐漸減小之后逐漸減小 high，增加，增加 low，并保證，并保證 rhigh.key52，和，和 rlow.key52, ,否否則進(jìn)行記錄的則進(jìn)行記錄的“交換交換”( (實(shí)際只需賦值實(shí)際只需賦值) )。一趟快速排序算法一趟快速排序算法int QKpass(RecordList L, int low, int high) /*本算法對(duì)本算法對(duì)rs.t進(jìn)行一趟快速排序進(jìn)行一趟快速排序*/ L.r0=L.rlow; while (lowhigh) /*low用用i表示表示, high用

24、用j表示表示*/while (low=L.r0.key) -high; L.rlow=L.rhigh; while (lowhigh)&(rlow.key=L.r0.key) +low; L.rhigh=L.rlow; L.rlow=L.r0; return low; 首先對(duì)無(wú)序的序列進(jìn)行首先對(duì)無(wú)序的序列進(jìn)行“一次劃分一次劃分”,之之后后分別分別對(duì)分割所得兩個(gè)子序列對(duì)分割所得兩個(gè)子序列“遞歸遞歸”進(jìn)進(jìn)行快速排序行快速排序。無(wú) 序 的 記 錄 序 列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸樞軸一次劃分分別進(jìn)行快速排序快速排序過(guò)程快速排序過(guò)程void QKSort(RecordList L

25、, int low, int high); /*對(duì)記錄序列對(duì)記錄序列rs.t進(jìn)行快速排序進(jìn)行快速排序*/ if (low high) pos=QKpass(L,low,high); /*對(duì)對(duì) rs.t 進(jìn)行一趟劃分進(jìn)行一趟劃分,pos為樞軸為樞軸*/ QKsort(L,low,pos-1); /*對(duì)低子序列遞歸排序?qū)Φ妥有蛄羞f歸排序*/ QKsort(L,pos+1,high); /*對(duì)高子序列遞歸排序?qū)Ω咦有蛄羞f歸排序*/ 快速排序算法快速排序算法穩(wěn)定？穩(wěn)定？假設(shè)假設(shè)一次劃分所得樞軸位置一次劃分所得樞軸位置 i=k，則，則對(duì)對(duì)n 個(gè)記錄進(jìn)行快速排序所需時(shí)間：個(gè)記錄進(jìn)行快速排序所需時(shí)間：其中其

26、中 Tpass(n)為對(duì)為對(duì) n 個(gè)記錄進(jìn)行一次劃分個(gè)記錄進(jìn)行一次劃分所需時(shí)間。所需時(shí)間。 若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則則 k 取取 1 至至 n 中任意一值的可能性相同。中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)三、快速排序的時(shí)間分析三、快速排序的時(shí)間分析設(shè)設(shè)Tavg(0)b , Tavg(1)b , c,b為常數(shù)為常數(shù)則用數(shù)學(xué)歸納法可證明：則用數(shù)學(xué)歸納法可證明：Tavg (n)2 n (b+c) ln (n)結(jié)論結(jié)論: 快速排序的時(shí)間復(fù)雜度為快速排序的時(shí)間復(fù)雜度為O(nlogn)由此可得快速排

27、序所需時(shí)間的由此可得快速排序所需時(shí)間的平均值平均值為：為：Tavg (n) = = cn + + Tavg (k- -1)+Tavg (n- -k)nk=1n1= = cn + + Tavg (i)n-1i=1n2 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判颍瑫r(shí)，快速排序?qū)⑼懟癁槠鹋菖判颍鋾r(shí)間其時(shí)間復(fù)雜度為復(fù)雜度為O(n2)。 為避免出現(xiàn)這種情況，為避免出現(xiàn)這種情況，需在第一次劃分需在第一次劃分之前，進(jìn)行之前，進(jìn)行“予處理予處理”，即：即： 先對(duì)先對(duì) rs.key, rt.key 和和 r (s+t)/2 .key進(jìn)行相互比較，然后進(jìn)行相

28、互比較，然后取取關(guān)鍵字為關(guān)鍵字為 “中間中間” 的記錄的記錄為樞軸為樞軸記錄。記錄。9.4 9.4 選擇類排序法選擇類排序法一、簡(jiǎn)一、簡(jiǎn) 單單 選選 擇擇 排排 序序二、樹二、樹 形形 選選 擇擇 排排 序序三、堆三、堆 排排 序序一、簡(jiǎn)單選擇排序一、簡(jiǎn)單選擇排序假設(shè)排序過(guò)程中假設(shè)排序過(guò)程中, 待排記錄序列的狀態(tài)為：待排記錄序列的狀態(tài)為：有序序列有序序列r1.i-1無(wú)序序列無(wú)序序列 ri.n 第第 i 趟趟簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序從中選出從中選出關(guān)鍵字最小的記錄關(guān)鍵字最小的記錄有序序列有序序列r1.i無(wú)序序列無(wú)序序列 ri+1.n有序序列有序序列小于小于無(wú)序序列無(wú)序序列簡(jiǎn)單選擇排序算法簡(jiǎn)單選擇

29、排序算法void SelectSort(RecordList L) for ( i=1 ; i=L.length; i+) k=i； for ( j=i+1 ; j= L.length-1; j+) if (L.rj.key L.rk.key ) k=j； if ( k!=i) t= ri； ri= rk； rk=t; 穩(wěn)定？穩(wěn)定？時(shí)間性能分析時(shí)間性能分析 對(duì)對(duì) n 個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，所需進(jìn)行的所需進(jìn)行的 關(guān)鍵字間的比較次數(shù)關(guān)鍵字間的比較次數(shù) 總計(jì)為：總計(jì)為：移動(dòng)記錄的次數(shù)移動(dòng)記錄的次數(shù)：最小值為最小值為 0 最大值為最大值為3(n-1) 。2) 1()(11-=

30、-=nninni二、樹形選擇排序二、樹形選擇排序 是一種按是一種按錦標(biāo)賽錦標(biāo)賽的思想進(jìn)行排序的的思想進(jìn)行排序的方法。方法。 選擇時(shí)兩兩比較選擇時(shí)兩兩比較,第一輪小者為勝第一輪小者為勝者再進(jìn)行第二輪比較者再進(jìn)行第二輪比較,逐層向上直到比逐層向上直到比出冠軍為最小者。出冠軍為最小者。 比較的過(guò)程是一個(gè)二叉樹結(jié)構(gòu)比較的過(guò)程是一個(gè)二叉樹結(jié)構(gòu),其其中記錄了互相之間的比較結(jié)果中記錄了互相之間的比較結(jié)果,利用此利用此結(jié)果再比較很快會(huì)得到第二第三結(jié)果再比較很快會(huì)得到第二第三 。 01 02 03 04 05 06 07 08 01 03 05 06 01 05 01 按錦標(biāo)賽規(guī)則，按錦標(biāo)賽規(guī)則，05將成為將成

31、為亞軍亞軍，顯然，顯然不合理不合理。解決。解決的方法是在的方法是在01奪冠奪冠之后，之后，01退出，退出，01參加過(guò)的比賽重參加過(guò)的比賽重新進(jìn)行新進(jìn)行（再篩選）。（再篩選）。020202如此，第二、第三如此，第二、第三 各名次的結(jié)果才真實(shí)、各名次的結(jié)果才真實(shí)、合理。合理。 由此，引出堆排序方法由此，引出堆排序方法(空間、時(shí)間效率更高空間、時(shí)間效率更高)三、堆排序三、堆排序堆是滿足下列性質(zhì)的數(shù)列堆是滿足下列性質(zhì)的數(shù)列r1, r2, ，rn：或或+122iiiirrrr+122iiiirrrr堆的定義堆的定義:(小頂堆小頂堆)(大頂堆大頂堆)rir2i r2i+1 可將該數(shù)列視作按層次存儲(chǔ)的完全二

32、叉樹，可將該數(shù)列視作按層次存儲(chǔ)的完全二叉樹，則則 r2i 是是 ri 的左孩子；的左孩子； r2i+1 是是 ri 的右孩子。的右孩子。例如例如:341236276549817355409812, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49是堆是堆是小頂堆是小頂堆不不1412, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆 可利用可利用堆的特性堆的特性(首元素最小或最大首元素最小或最大)對(duì)記錄序列進(jìn)行排序！對(duì)記錄序列進(jìn)行排序！堆排序的特征堆排序的特征 堆排序是在排序過(guò)程中，將向量中堆排序是在排序過(guò)程中，將向量中存儲(chǔ)的

33、數(shù)據(jù)看成一棵完全二叉樹存儲(chǔ)的數(shù)據(jù)看成一棵完全二叉樹, ,利用完利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇關(guān)鍵字最小的記錄，即內(nèi)在關(guān)系來(lái)選擇關(guān)鍵字最小的記錄，即待排序記錄仍采用向量數(shù)組方式存儲(chǔ)，待排序記錄仍采用向量數(shù)組方式存儲(chǔ)，并非采用樹的存儲(chǔ)結(jié)構(gòu)，僅僅是采用完并非采用樹的存儲(chǔ)結(jié)構(gòu)，僅僅是采用完全二叉樹順序結(jié)構(gòu)的特征進(jìn)行分析處理。全二叉樹順序結(jié)構(gòu)的特征進(jìn)行分析處理。 堆排序堆排序即是利用即是利用堆的特性堆的特性對(duì)記錄序列對(duì)記錄序列進(jìn)行排序的一種排序方法進(jìn)行排序的一種排序方法,過(guò)程如下：過(guò)程如下：1、對(duì)給定序列建堆；、對(duì)給定序列建堆； 2、輸出堆頂；、

34、輸出堆頂；(首元素與尾元素交換首元素與尾元素交換)3、對(duì)剩余元素重建堆；、對(duì)剩余元素重建堆；(篩選首元素篩選首元素)4、重復(fù)、重復(fù)2，3，直至所有元素輸出。，直至所有元素輸出。1、如何由一個(gè)無(wú)序序列、如何由一個(gè)無(wú)序序列“建堆建堆”？問(wèn)題問(wèn)題:2、輸出堆頂后如何、輸出堆頂后如何“重建堆重建堆” ？?jī)蓚€(gè)問(wèn)題均可歸結(jié)為兩個(gè)問(wèn)題均可歸結(jié)為“篩選篩選”問(wèn)題？問(wèn)題？建大頂堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交換 9898 和 1212重新調(diào)整為大頂堆 81, 73, 49, 64,

35、36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 經(jīng)過(guò)篩選 繼續(xù)重復(fù)，可的有序序列。12, 73, 49, 64, 36, 27, 40, 55, 81, 98 交換 8181 和 1212例如：例如： 所謂所謂“篩選篩選”指的是，對(duì)一棵左指的是，對(duì)一棵左/右子樹均為右子樹均為堆堆的完全二叉樹，的完全二叉樹，“調(diào)整調(diào)整”根結(jié)點(diǎn)根結(jié)點(diǎn)使整個(gè)二叉樹也成為一個(gè)堆使整個(gè)二叉樹也成為一個(gè)堆。堆堆堆堆篩選篩選814973556412362740是大頂堆是大頂堆但98 和12 互換后(去掉98), 不不為堆。因此，需要對(duì)它進(jìn)行“篩選篩

36、選”(調(diào)整12)。981298比較比較比較981281736412建初堆也是一個(gè)建初堆也是一個(gè)“篩選篩選”的過(guò)程！的過(guò)程！例如例如: 建初堆建初堆是從最后一個(gè)有孩子的結(jié)點(diǎn)開始，往是從最后一個(gè)有孩子的結(jié)點(diǎn)開始，往前逐個(gè)結(jié)點(diǎn)進(jìn)行前逐個(gè)結(jié)點(diǎn)進(jìn)行“篩選篩選”的過(guò)程。的過(guò)程。40554973816436122798例如給定的關(guān)鍵字序列為例如給定的關(guān)鍵字序列為: 40, 55 ,49, 73, 12 ,27, 98, 81, 64, 36123681734998817355 現(xiàn)在，左現(xiàn)在，左/ /右子樹都已經(jīng)調(diào)整為堆，最后只要右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹是個(gè)調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉

37、樹是個(gè)“堆堆”即可。即可。98494064361227篩選算法篩選算法void HeapAdjust（RecordList L, int s，int ） /* 調(diào)整調(diào)整rk，使整個(gè)序列，使整個(gè)序列rk.m滿足堆的性質(zhì)滿足堆的性質(zhì) */ t= L.rs ； for(j=2*s;j=m;j*=2) if (jm & L.rj.key L.rj+1.key ) j=j+1； if ( t.key= 1 ; i-) HeapAdjust(L，i，L.length) ； 堆排序算法堆排序算法void HeapSort（RecordList L） /* 進(jìn)行堆排序進(jìn)行堆排序*/ CreatHeap

38、(L)； for ( i=L.length ; i= 2 ; i-) L.r0=L.r1; L.r1= L.ri; L.ri=L.r0; /* 將堆頂記錄和堆中最后一個(gè)記錄互換將堆頂記錄和堆中最后一個(gè)記錄互換 */ HeapAdjust(L，1，i-1)； 穩(wěn)定？穩(wěn)定？堆排序時(shí)間復(fù)雜度分析：堆排序時(shí)間復(fù)雜度分析：1. 對(duì)深度為對(duì)深度為 k 的堆，的堆，“篩選篩選”所需進(jìn)行的關(guān)鍵字所需進(jìn)行的關(guān)鍵字 比較的次數(shù)至多為比較的次數(shù)至多為2(k-1)；3. 重建堆重建堆 n-1 次，所需進(jìn)行的關(guān)鍵字比較的次數(shù)次，所需進(jìn)行的關(guān)鍵字比較的次數(shù) 不超過(guò)：不超過(guò)：(n-1)*2 log2n ; 因此，因此，堆排

39、序的時(shí)間復(fù)雜度為堆排序的時(shí)間復(fù)雜度為( (最壞情況最壞情況):):O(n* log2n + (n-1)*2 log2n )= O(nlogn)。2. n 個(gè)關(guān)鍵字的堆深度為個(gè)關(guān)鍵字的堆深度為 log2n +1, 初建初建堆堆所需所需 進(jìn)行的關(guān)鍵字比較的次數(shù)至多為：進(jìn)行的關(guān)鍵字比較的次數(shù)至多為：n* log2n ;9.5 9.5 歸并排序歸并排序歸并排序的過(guò)程基于下列歸并排序的過(guò)程基于下列基本思想基本思想進(jìn)行：進(jìn)行： 將兩個(gè)或兩個(gè)以上的有序子序列將兩個(gè)或兩個(gè)以上的有序子序列 “歸并歸并” 為一個(gè)有序序列。為一個(gè)有序序列。在內(nèi)部排序中，通常采用的是在內(nèi)部排序中，通常采用的是2-路歸并路歸并排序。即

40、：排序。即：將兩個(gè)位置相鄰的有序子序列將兩個(gè)位置相鄰的有序子序列歸并為一個(gè)有序的序列歸并為一個(gè)有序的序列。有有 序序 序序 列列 rl.n有序子序列有序子序列 rl.m有序子序列有序子序列 rm+1.n這個(gè)操作對(duì)順序表而言，是輕而易舉的。這個(gè)操作對(duì)順序表而言，是輕而易舉的。歸歸并并例：(19) (13) (05) (27) (01) (26) (31) (16) (13,19) (05,27) (01,26) (16,31) (05,13,19,27) (01,16,26,31) (01,05,13,16,19,26,27,31)52, 23, 80, 36, 68, 14 52, 23, 8

41、0 36, 68, 14 52, 23 80 52 23, 52 23, 52, 80 36, 68 14 36 68 36, 68 14, 36, 68 14, 23, 36, 52, 68, 8023完整的歸并排序過(guò)程為：先分組再歸并。完整的歸并排序過(guò)程為：先分組再歸并。2-2-路歸并排序算法路歸并排序算法void MergeSort ( RecordList RecordList L L, RecordList , RecordList CopyLCopyL， int right, int leftint right, int left) int middle; if (leftrigh

42、t) middle=(left+right)/2； MergeSort(L，CopyL， left, middle)； MergeSort(L，CopyL, middle+1, right)； Merge (L，CopyL，left，right， middle)；穩(wěn)定？穩(wěn)定？合并算法合并算法void MergeSort ( RecordList RecordList L L, RecordList , RecordList CopyLCopyL， int right, int leftint right, int left)int i,p1,p2; for(i=left;i=right;i+)

43、 CopyL.ri=L.ri;i=left；p1=left； p2=middle+1； while ( (p1=middle)&(p2=right) ) if ( CopyL.rp1.key=CopyL.rp2.key ) L.ri=CopyL.rp1 ；p1+； else L.ri=CopyL.rp2 ；p2+； i+； while( p1=middle ) L.ri =CopyL.rp1；i+; p1+; while( p2=right ) L.ri =CopyL.rp2；i+;p2+; 自然歸并排序歸并排序的復(fù)雜度分析：歸并排序的復(fù)雜度分析：容易看出，對(duì)容易看出，對(duì) n 個(gè)記錄進(jìn)

44、行歸并排序的個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為(nlogn)。即：即： 每一趟歸并的時(shí)間復(fù)雜度為每一趟歸并的時(shí)間復(fù)雜度為 O(n)， 總共需進(jìn)行總共需進(jìn)行 log2n 趟。趟。 歸并排序的空間復(fù)雜度較高，需要有長(zhǎng)歸并排序的空間復(fù)雜度較高，需要有長(zhǎng)度為度為n的輔助數(shù)組，即為的輔助數(shù)組，即為O(n)。9.6 9.6 分配類排序分配類排序基數(shù)排序是一種基數(shù)排序是一種借助借助“多關(guān)鍵字排序多關(guān)鍵字排序”的思想來(lái)實(shí)現(xiàn)的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排序單關(guān)鍵字排序”的內(nèi)部的內(nèi)部排序算法。排序算法。多關(guān)鍵字的排序多關(guān)鍵字的排序基數(shù)排序基數(shù)排序 n 個(gè)記錄的序列個(gè)記錄的序列 R1, R2, ，Rn 對(duì)關(guān)鍵字

45、對(duì)關(guān)鍵字 (Ki0, Ki1, ,Kid-1) ) 有序有序是指是指： 其中其中: : K0 被稱為被稱為 “最主最主/ /最高最高”位關(guān)鍵字位關(guān)鍵字Kd-1 被稱為被稱為 “最次最次/ /最低最低”位關(guān)鍵字位關(guān)鍵字 對(duì)于序列中任意兩個(gè)記錄對(duì)于序列中任意兩個(gè)記錄Ri 和和 Rj (1ijn) 都都滿足滿足下列下列(詞典詞典)有序有序關(guān)系：關(guān)系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) ) 一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序 實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種方法實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種方法: :最低位優(yōu)先最低位優(yōu)先LSD法法最高位優(yōu)先最高位優(yōu)先MSD

46、法以撲克牌排序?yàn)槔該淇伺婆判驗(yàn)槔? : 將撲克牌的排序看成由將撲克牌的排序看成由花色花色和和面值面值兩個(gè)關(guān)鍵字兩個(gè)關(guān)鍵字進(jìn)行排序的問(wèn)題。若規(guī)定花色和面值的順序如下：進(jìn)行排序的問(wèn)題。若規(guī)定花色和面值的順序如下： 花色：梅花花色：梅花 方塊方塊 紅桃紅桃 黑桃黑桃； 面值：面值：A23A2310JQK10JQK； 花色的優(yōu)先級(jí)高于面值；花色的優(yōu)先級(jí)高于面值；則一副牌從小到大的順序?yàn)椋簞t一副牌從小到大的順序?yàn)椋?A,A,2,2, ,K K；A,A,2,2, ,K K； A,A,2,2, ,K K；A,A,2,2, ,K K。撲克牌的排序過(guò)程撲克牌的排序過(guò)程 訪法一訪法一(LSD) ： 訪法二訪法二

47、(MSD)： 先先按按K0進(jìn)行排序進(jìn)行排序，并按，并按K0 的不的不同值將記錄序列同值將記錄序列分成若干子序列分成若干子序列，之后之后再再分別分別按按 K1 進(jìn)行排序進(jìn)行排序，.， 依次類推依次類推, 直至最后直至最后分別分別按最次位按最次位關(guān)鍵字關(guān)鍵字Kd-1排序完成為止排序完成為止。最高位優(yōu)先最高位優(yōu)先MSD法： 先按先按Kd-1 進(jìn)行排序進(jìn)行排序，然后按然后按 Kd-2 進(jìn)進(jìn)行行穩(wěn)定的穩(wěn)定的排序，依次類推，直至按最主排序，依次類推，直至按最主位關(guān)鍵字位關(guān)鍵字K0 排序完成為止排序完成為止。 LSDLSD排序過(guò)程中不需要根據(jù)排序過(guò)程中不需要根據(jù) “前一個(gè)前一個(gè)” 關(guān)鍵字的排序結(jié)果，將記錄序

48、列分割成若關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(gè)子序列。干個(gè)子序列。最低位優(yōu)先最低位優(yōu)先LSD法：法：例例: :學(xué)生記錄含三個(gè)關(guān)鍵字學(xué)生記錄含三個(gè)關(guān)鍵字: :系別系別、班號(hào)班號(hào)和和班內(nèi)的序列號(hào)班內(nèi)的序列號(hào)，其中以，其中以系別系別為最主位關(guān)鍵字。為最主位關(guān)鍵字。 無(wú)序序列無(wú)序序列對(duì)對(duì)K2排序排序?qū)?duì)K1排序排序?qū)?duì)K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序過(guò)程如下的排序過(guò)程

49、如下: :二、基數(shù)排序二、基數(shù)排序 當(dāng)當(dāng)每個(gè)關(guān)鍵字的每個(gè)關(guān)鍵字的取值范圍相同取值范圍相同時(shí)，其排時(shí)，其排序可采用序可采用“分配分配”而非而非“比較比較”的方法進(jìn)的方法進(jìn)行。行。對(duì)于數(shù)字型或字符型的對(duì)于數(shù)字型或字符型的單關(guān)鍵字單關(guān)鍵字，可可以看成是由以看成是由多個(gè)多個(gè)數(shù)位數(shù)位或或多個(gè)多個(gè)字符字符構(gòu)成的多構(gòu)成的多關(guān)鍵字，而此時(shí)關(guān)鍵字，而此時(shí)每個(gè)每個(gè)“關(guān)鍵字關(guān)鍵字”的的取值范取值范圍圍是原關(guān)鍵字的是原關(guān)鍵字的基數(shù)。基數(shù)。 對(duì)于數(shù)字型或字符型的對(duì)于數(shù)字型或字符型的“多關(guān)鍵字多關(guān)鍵字” ,可用可用LSD法，并法，并采用采用 “分配分配- -收集收集”再再“分分配配- -收集收集”的辦法實(shí)現(xiàn)的辦法實(shí)現(xiàn)排序

50、排序, 這就是這就是基數(shù)基數(shù)排序排序。例如：例如：對(duì)下列這組關(guān)鍵字對(duì)下列這組關(guān)鍵字 369，367，167，239，237，138，230，139 首先按其首先按其 “個(gè)位數(shù)個(gè)位數(shù)” 取值取值 “分配分配” 成成 10 組，之后按從組，之后按從 0 至至 9 的順序?qū)⒏鹘M的順序?qū)⒏鹘M “收集收集” 在一起；在一起； 然后按其然后按其 “十位數(shù)十位數(shù)” 取值取值 “分配分配” 成成 10 組，之后再按從組，之后再按從 0 至至 9 的順序?qū)⒏鹘M的順序?qū)⒏鹘M“收集收集” 起來(lái)；起來(lái)； 最后按其最后按其 “百位數(shù)百位數(shù)” 取值取值 “分配分配” 成成 10 組，之后再按從組，之后再按從 0 至至 9

51、 的順序?qū)⒏鹘M的順序?qū)⒏鹘M“收集收集” 起來(lái)。起來(lái)。 實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，可采用鏈表作存儲(chǔ)結(jié)構(gòu)?？臻g，可采用鏈表作存儲(chǔ)結(jié)構(gòu)。待排序記錄以鏈表為存儲(chǔ)結(jié)構(gòu)；待排序記錄以鏈表為存儲(chǔ)結(jié)構(gòu)；“分配分配” 時(shí)，按時(shí)，按當(dāng)前當(dāng)前“關(guān)鍵字位關(guān)鍵字位”將記錄將記錄分分 配到不同的配到不同的 “鏈隊(duì)列鏈隊(duì)列” 中，每個(gè)隊(duì)列中中，每個(gè)隊(duì)列中記記 錄的錄的 當(dāng)前當(dāng)前“關(guān)鍵字位關(guān)鍵字位” 相同；相同；“收集收集”時(shí)，時(shí)，將各隊(duì)列將各隊(duì)列按關(guān)鍵字從小到大按關(guān)鍵字從小到大首首 尾相鏈尾相鏈構(gòu)成一個(gè)新鏈表構(gòu)成一個(gè)新鏈表; ;按按LSDLSD對(duì)每個(gè)關(guān)鍵字位重復(fù)對(duì)每個(gè)關(guān)鍵字位

52、重復(fù)2 、3, , 便可獲便可獲 得有序序列。得有序序列。具體方法：具體方法：p369367167239237138230139進(jìn)行第一次分配進(jìn)行第一次分配進(jìn)行第一次收集進(jìn)行第一次收集p230230 367 167237367167237138369239139369 239139138 f0 r0f7 r7f8 r8f9 r9例如：例如：進(jìn)行第二次分配進(jìn)行第二次分配p230237138239139p230367167237138369239139230 237138239139367 167369367167369進(jìn)行第二次收集 f3 r3 f6 r6 進(jìn)行第三次收集進(jìn)行第三次收集p2302

53、37138239139367167369進(jìn)行第三次分配進(jìn)行第三次分配138 139167230 237239367 369p138139167230237239367369已得到記錄的有序序列已得到記錄的有序序列f1 r1f2 r2f3 r3 基數(shù)排序的時(shí)間復(fù)雜度為基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd)其中：分配為其中：分配為O(n) 收集為收集為O(rd)(rd為為“基基”) d為為“分配分配-收集收集”的趟數(shù)的趟數(shù)9.7 外部排序1. 插入類插入類直接插入排序直接插入排序和和希爾排序希爾排序2. 交換類交換類起泡排序起泡排序和和快速排序快速排序。3. 選擇類選擇類4. 歸并類歸并類5.

54、分配類分配類基數(shù)排序基數(shù)排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序和和堆排序堆排序 歸并排序歸并排序9.8 9.8 算法總結(jié)算法總結(jié)排序方法排序方法 平均時(shí)間平均時(shí)間 最壞時(shí)間最壞時(shí)間 輔助空間輔助空間 穩(wěn)定性穩(wěn)定性簡(jiǎn)單排序簡(jiǎn)單排序 O(n2) O(n2) O(1) 穩(wěn)定穩(wěn)定希爾排序希爾排序 O(n3/2) O(dk) 非穩(wěn)定非穩(wěn)定快速排序快速排序 O(nlogn) O(n2) O(logn) 非穩(wěn)定非穩(wěn)定 堆排序堆排序 O(nlogn) O(nlogn) O(1) 非穩(wěn)定非穩(wěn)定歸并排序歸并排序 O(nlogn) O(nlogn) O(n) 穩(wěn)定穩(wěn)定基數(shù)排序基數(shù)排序 O(d*n) O(d*n) O(rd)

55、穩(wěn)定穩(wěn)定一、性能比較一、性能比較通過(guò)分析和比較，可以得出以下結(jié)論：通過(guò)分析和比較，可以得出以下結(jié)論：簡(jiǎn)單排序一般只用于簡(jiǎn)單排序一般只用于n n值較小的情況；值較小的情況；歸并排序適用于歸并排序適用于n n值較大的情況；值較大的情況；基數(shù)排序適用于基數(shù)排序適用于n n值很大而關(guān)鍵字的位數(shù)值很大而關(guān)鍵字的位數(shù)d d較較小的序列；小的序列；快速排序是排序方法中最快速排序是排序方法中最“快快”的方法。的方法。 本章討論的各種排序方法，除基數(shù)排序本章討論的各種排序方法，除基數(shù)排序外，其它方法都是外，其它方法都是基于基于“比較比較”進(jìn)行排序進(jìn)行排序的排序方法。的排序方法。 可以證明可以證明, 這類排序法這

56、類排序法可能達(dá)到的最快可能達(dá)到的最快的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為O(nlogn)。(基數(shù)排序不是基于 “比較關(guān)鍵字”的排序方法，所以它不受這個(gè)限制。)二、內(nèi)部排序時(shí)間復(fù)雜度下限分析二、內(nèi)部排序時(shí)間復(fù)雜度下限分析 例如例如:對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹如下：如下：K1K3K1K2K1K3K2K3K2 K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2樹上的樹上的每一次每一次“比較比較”都是都是必要必要的的;樹上的樹上的葉子葉子代表代表所有可能的排序結(jié)果所有可能的排序結(jié)果。nynnnn 一般而言一般而言, 對(duì)對(duì)n個(gè)關(guān)鍵字進(jìn)行排序個(gè)關(guān)鍵字進(jìn)行排序

57、, 可得可得到的結(jié)果有到的結(jié)果有n! 種種(n! 個(gè)葉子個(gè)葉子), 由于含由于含n! 個(gè)個(gè)葉子的二叉樹的深度不小于葉子的二叉樹的深度不小于 log2(n!) +1, 所以對(duì)所以對(duì) n 個(gè)關(guān)鍵字進(jìn)行排序的比較次數(shù)至個(gè)關(guān)鍵字進(jìn)行排序的比較次數(shù)至少是少是 log2(n!) nlog2n (斯蒂林近似公式斯蒂林近似公式)。 所以所以, 基于基于“比較關(guān)鍵字比較關(guān)鍵字”進(jìn)行排序進(jìn)行排序的的排序方法排序方法, 可能達(dá)到的最快的時(shí)間復(fù)雜度可能達(dá)到的最快的時(shí)間復(fù)雜度為為 O(nlogn)。 了解排序的定義和各種排序方法的特點(diǎn)。了解排序的定義和各種排序方法的特點(diǎn)。 熟練掌握各種排序方法及各種排序方法排熟練掌握各

58、種排序方法及各種排序方法排序時(shí)每趟的變化過(guò)程。序時(shí)每趟的變化過(guò)程。 插入排序（插入排序（希爾希爾）；交換排序（）；交換排序（快速快速）；）； 選擇排序（選擇排序（堆堆）；）； 歸并排序；歸并排序； 基于基于“分配分配- -收集收集”的基數(shù)排序。的基數(shù)排序。9.8 9.8 總結(jié)與提高總結(jié)與提高 2、掌握各種排序方法的時(shí)間復(fù)雜度掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從的分析方法。能從“關(guān)鍵字間的比較次關(guān)鍵字間的比較次數(shù)數(shù)”分析排序算法的平均情況和最壞情分析排序算法的平均情況和最壞情況的時(shí)間性能。況的時(shí)間性能。 按平均時(shí)間復(fù)雜度劃分按平均時(shí)間復(fù)雜度劃分, ,內(nèi)部排序可分內(nèi)部排序可分為三類：為三類

59、：O(n2) 的簡(jiǎn)單排序方法、的簡(jiǎn)單排序方法、O(nlogn)的高效排序方法和的高效排序方法和O(dn)的基數(shù)排序方法。的基數(shù)排序方法。 3理解排序方法理解排序方法“穩(wěn)定穩(wěn)定”或或“不穩(wěn)定不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。的排序方法必須是穩(wěn)定的。 4. 了解外部排序的基本過(guò)程及其時(shí)間了解外部排序的基本過(guò)程及其時(shí)間分析分析。典型例題：典型例題：例例1 1 ：設(shè)有：設(shè)有1000010000個(gè)元素，要求找出最小的個(gè)元素，要求找出最小的1010個(gè)，個(gè)，選擇合適的排序方法。選擇合適的排序方法。例例2 2： n=7時(shí)，給出快速排序最好情況的

60、初始序列。時(shí)，給出快速排序最好情況的初始序列。堆排序！堆排序！ 4，1，3，2，6，5，7 例例3 3 哈希排序：設(shè)有哈希排序：設(shè)有300300個(gè)記錄，其關(guān)鍵字均為個(gè)記錄，其關(guān)鍵字均為小于小于10001000的正整數(shù)，且互不相等。設(shè)計(jì)一排序的正整數(shù)，且互不相等。設(shè)計(jì)一排序方法，比較移動(dòng)次數(shù)盡可能少。方法，比較移動(dòng)次數(shù)盡可能少。設(shè)置輔助數(shù)組設(shè)置輔助數(shù)組b1.999,b1.999,按哈希法將記錄分配按哈希法將記錄分配, ,再回收再回收例例4 荷蘭國(guó)旗問(wèn)題：荷蘭國(guó)旗問(wèn)題： 設(shè)有一個(gè)僅由紅、白、藍(lán)三種顏色的色設(shè)有一個(gè)僅由紅、白、藍(lán)三種顏色的色條組成的序列，要求在條組成的序列，要求在O(n) O(n) 的時(shí)間內(nèi)將其排的時(shí)間內(nèi)將其排列成荷蘭國(guó)旗。列