數(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é)與提高一、排序的定義一、排序的定義 排序是計算機內(nèi)經(jīng)常進(jìn)行的一種操作，排序是計算機內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組其目的是將一組“無序無序”的記錄序列調(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 個記錄的序列為個記錄的序列為 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)定的。的。 若若整個排序過程不需要訪問外存整個排序過程不需要訪問外存便能完成，則稱此類排序問題便能完成，則稱此類排序問題為內(nèi)部為內(nèi)部排序。排序。 反之反之, 若參加排序的記錄數(shù)量很若參加排序的記錄數(shù)量很大大, 整個序列的排序過程整個序列的排序過程不可能在內(nèi)不可能在內(nèi)存存 中完成中完成，則稱此類排序問題，則稱此類排序問題為外為外部排序部排序。三、內(nèi)部排序和外部排序三、內(nèi)部排序和外部排序1、順序存儲：移動記錄實現(xiàn)排序；、順序存儲：移

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

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

7、入排序直接插入排序（基于順序查找）（基于順序查找）不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）利用 “順序查找順序查找”實現(xiàn)“在r1.i-1中查找查找ri的插入位置的插入位置”算法的實現(xiàn)：算法的實現(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 的記錄向后移動的記錄向后移動 1位

8、位; jjj3. 將將r0(原原ri)“插入插入”到到j(luò)+1的位置的位置。監(jiān)視哨設(shè)置在監(jiān)視哨設(shè)置在r0； 可以在查找的同時實現(xiàn)記錄向后移動；可以在查找的同時實現(xiàn)記錄向后移動；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, 可實現(xiàn)整個序列的排序?？蓪崿F(xiàn)整個序列的排序。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; 實現(xiàn)內(nèi)部排序的實現(xiàn)內(nèi)部排序的基本操作基本操作有兩個：有兩個：（2）“移動移動”記錄。記錄。（1）“比較比較”序列中兩個關(guān)鍵字的序列中兩個關(guān)鍵字的 大??；大?。粫r

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

11、則可以利用折半查找折半查找實現(xiàn)在實現(xiàn)在“r1.i-1中查找中查找 ri的插入位置的插入位置”, 如如此實現(xiàn)的插入排序為折半插入排序。它此實現(xiàn)的插入排序為折半插入排序。它只能只能減少查找減少查找的次數(shù)的次數(shù)不能減少移動不能減少移動的次的次數(shù)數(shù), 因此與查找后移同時實現(xiàn)的直接插因此與查找后移同時實現(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; 由于由于插入排序的效率取決于插入排序的效率取決于:記錄的個數(shù)記錄的個數(shù)及記錄的原始序；及記錄的原始序； “宏觀宏觀”調(diào)整調(diào)整：先先“跳躍式跳躍式”的分組

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

14、。插入排序，組數(shù)不斷減少，最后僅剩一組。其中其中, d 稱為增量稱為增量, 它的值在排序過程中從它的值在排序過程中從大到小逐漸縮小大到小逐漸縮小, ,直至最后一趟排序直至最后一趟排序減為減為 1 . . 例如：將例如：將 n 個記錄個記錄 r1, r2rd, r1+d,r2+dr2d, r1+2d rn 分成分成 d 個子序列：個子序列： 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); 希爾排序的時間復(fù)雜度分析是一個希爾排序的時間復(fù)雜度分析是一個數(shù)學(xué)上尚未解決的難題。數(shù)學(xué)上尚未解決的難題。增量序列增量序列d1.t的設(shè)計至關(guān)重要，目前沒有統(tǒng)一的設(shè)計至關(guān)重要，目前沒有統(tǒng)一定論，以經(jīng)驗為主。定論，以經(jīng)驗為主。 以經(jīng)驗，當(dāng)以經(jīng)驗，當(dāng)n在一定范圍內(nèi)時，在一定范圍內(nèi)時，希爾希爾排序的比較與移動次數(shù)約為：排序的比較與移動次數(shù)約為：n1.3,當(dāng)當(dāng)n時時:比較與移動次數(shù)約為比較與移動次數(shù)約為n(log2n)2。9.3 9.3 交換類排序法交換類排序法一、一

17、、 起泡排序起泡排序二、二、 快速排序快速排序三、三、 快速排序的時間分析快速排序的時間分析假設(shè)在排序過程中，記錄序列假設(shè)在排序過程中，記錄序列r1.n的狀態(tài)為：的狀態(tài)為：一一 趟起泡排序趟起泡排序無序序列r1.i有序序列 ri+1.ni無序序列r1.i-1有序序列 ri.n對無序序列，比較對無序序列，比較(交交換換)相鄰記錄，可將關(guān)相鄰記錄，可將關(guān)鍵字最大的記錄鍵字最大的記錄交換交換到到 i 的位置上的位置上有序序列大于無序序列有序序列大于無序序列一、一、 起泡排序起泡排序算法一：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)過一趟“起泡”則“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“移動移動”的次數(shù)：的次數(shù)：“移動移動”的次數(shù)：的次數(shù)：n-1(i -1) =ni=2n (n-1)23(i -1) =ni=23n (n-1)2 所以，時間復(fù)雜度為所以，時間復(fù)雜

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

21、作為以它的關(guān)鍵字作為“樞軸樞軸”，凡凡關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均的記錄均移移動至該記錄之前，動至該記錄之前，反之，凡反之，凡關(guān)鍵字大于樞關(guān)鍵字大于樞軸軸的記錄均的記錄均移動至該記錄之后移動至該記錄之后。致使致使一趟排序一趟排序之后，記錄的無序序列之后，記錄的無序序列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)過可見，經(jīng)過“一次劃分一次劃分”，將關(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)整過程中，設(shè)立了兩個指針：

23、在調(diào)整過程中，設(shè)立了兩個指針： low 和和high，它們的初值分別為：，它們的初值分別為： s 和和 t， 之后逐漸減小之后逐漸減小 high，增加，增加 low，并保證，并保證 rhigh.key52，和，和 rlow.key52, ,否否則進(jìn)行記錄的則進(jìn)行記錄的“交換交換”( (實際只需賦值實際只需賦值) )。一趟快速排序算法一趟快速排序算法int QKpass(RecordList L, int low, int high) /*本算法對本算法對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; 首先對無序的序列進(jìn)行首先對無序的序列進(jìn)行“一次劃分一次劃分”,之之后后分別分別對分割所得兩個子序列對分割所得兩個子序列“遞歸遞歸”進(jìn)進(jìn)行快速排序行快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸樞軸一次劃分分別進(jìn)行快速排序快速排序過程快速排序過程void QKSort(RecordList L

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

26、中 Tpass(n)為對為對 n 個記錄進(jìn)行一次劃分個記錄進(jìn)行一次劃分所需時間。所需時間。 若待排序列中記錄的關(guān)鍵字是隨機分布的，若待排序列中記錄的關(guān)鍵字是隨機分布的，則則 k 取取 1 至至 n 中任意一值的可能性相同。中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)三、快速排序的時間分析三、快速排序的時間分析設(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é)論: 快速排序的時間復(fù)雜度為快速排序的時間復(fù)雜度為O(nlogn)由此可得快速排

27、序所需時間的由此可得快速排序所需時間的平均值平均值為：為：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)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判颍瑫r，快速排序?qū)⑼懟癁槠鹋菖判颍鋾r間其時間復(fù)雜度為復(fù)雜度為O(n2)。 為避免出現(xiàn)這種情況，為避免出現(xiàn)這種情況，需在第一次劃分需在第一次劃分之前，進(jìn)行之前，進(jìn)行“予處理予處理”，即：即： 先對先對 rs.key, rt.key 和和 r (s+t)/2 .key進(jìn)行相互比較，然后進(jìn)行相

28、互比較，然后取取關(guān)鍵字為關(guān)鍵字為 “中間中間” 的記錄的記錄為樞軸為樞軸記錄。記錄。9.4 9.4 選擇類排序法選擇類排序法一、簡一、簡 單單 選選 擇擇 排排 序序二、樹二、樹 形形 選選 擇擇 排排 序序三、堆三、堆 排排 序序一、簡單選擇排序一、簡單選擇排序假設(shè)排序過程中假設(shè)排序過程中, 待排記錄序列的狀態(tài)為：待排記錄序列的狀態(tài)為：有序序列有序序列r1.i-1無序序列無序序列 ri.n 第第 i 趟趟簡單選擇排序簡單選擇排序從中選出從中選出關(guān)鍵字最小的記錄關(guān)鍵字最小的記錄有序序列有序序列r1.i無序序列無序序列 ri+1.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)定？時間性能分析時間性能分析 對對 n 個記錄進(jìn)行簡單選擇排序，個記錄進(jìn)行簡單選擇排序，所需進(jìn)行的所需進(jìn)行的 關(guān)鍵字間的比較次數(shù)關(guān)鍵字間的比較次數(shù) 總計為：總計為：移動記錄的次數(shù)移動記錄的次數(shù)：最小值為最小值為 0 最大值為最大值為3(n-1) 。2) 1()(11-=

30、-=nninni二、樹形選擇排序二、樹形選擇排序 是一種按是一種按錦標(biāo)賽錦標(biāo)賽的思想進(jìn)行排序的的思想進(jìn)行排序的方法。方法。 選擇時兩兩比較選擇時兩兩比較,第一輪小者為勝第一輪小者為勝者再進(jìn)行第二輪比較者再進(jìn)行第二輪比較,逐層向上直到比逐層向上直到比出冠軍為最小者。出冠軍為最小者。 比較的過程是一個二叉樹結(jié)構(gòu)比較的過程是一個二叉樹結(jié)構(gòu),其其中記錄了互相之間的比較結(jié)果中記錄了互相之間的比較結(jié)果,利用此利用此結(jié)果再比較很快會得到第二第三結(jié)果再比較很快會得到第二第三 。 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參加過的比賽重參加過的比賽重新進(jìn)行新進(jìn)行（再篩選）。（再篩選）。020202如此，第二、第三如此，第二、第三 各名次的結(jié)果才真實、各名次的結(jié)果才真實、合理。合理。 由此，引出堆排序方法由此，引出堆排序方法(空間、時間效率更高空間、時間效率更高)三、堆排序三、堆排序堆是滿足下列性質(zhì)的數(shù)列堆是滿足下列性質(zhì)的數(shù)列r1, r2, ，rn：或或+122iiiirrrr+122iiiirrrr堆的定義堆的定義:(小頂堆小頂堆)(大頂堆大頂堆)rir2i r2i+1 可將該數(shù)列視作按層次存儲的完全二

32、叉樹，可將該數(shù)列視作按層次存儲的完全二叉樹，則則 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不是堆不是堆 可利用可利用堆的特性堆的特性(首元素最小或最大首元素最小或最大)對記錄序列進(jìn)行排序！對記錄序列進(jìn)行排序！堆排序的特征堆排序的特征 堆排序是在排序過程中，將向量中堆排序是在排序過程中，將向量中存儲的

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

34、輸出堆頂；(首元素與尾元素交換首元素與尾元素交換)3、對剩余元素重建堆；、對剩余元素重建堆；(篩選首元素篩選首元素)4、重復(fù)、重復(fù)2，3，直至所有元素輸出。，直至所有元素輸出。1、如何由一個無序序列、如何由一個無序序列“建堆建堆”？問題問題:2、輸出堆頂后如何、輸出堆頂后如何“重建堆重建堆” ？兩個問題均可歸結(jié)為兩個問題均可歸結(jié)為“篩選篩選”問題？問題？建大頂堆 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)過篩選 繼續(xù)重復(fù)，可的有序序列。12, 73, 49, 64, 36, 27, 40, 55, 81, 98 交換 8181 和 1212例如：例如： 所謂所謂“篩選篩選”指的是，對一棵左指的是，對一棵左/右子樹均為右子樹均為堆堆的完全二叉樹，的完全二叉樹，“調(diào)整調(diào)整”根結(jié)點根結(jié)點使整個二叉樹也成為一個堆使整個二叉樹也成為一個堆。堆堆堆堆篩選篩選814973556412362740是大頂堆是大頂堆但98 和12 互換后(去掉98), 不不為堆。因此，需要對它進(jìn)行“篩選篩

36、選”(調(diào)整12)。981298比較比較比較981281736412建初堆也是一個建初堆也是一個“篩選篩選”的過程！的過程！例如例如: 建初堆建初堆是從最后一個有孩子的結(jié)點開始，往是從最后一個有孩子的結(jié)點開始，往前逐個結(jié)點進(jìn)行前逐個結(jié)點進(jìn)行“篩選篩選”的過程。的過程。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ào)整根結(jié)點，使整個二叉

37、樹是個“堆堆”即可。即可。98494064361227篩選算法篩選算法void HeapAdjust（RecordList L, int s，int ） /* 調(diào)整調(diào)整rk，使整個序列，使整個序列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; /* 將堆頂記錄和堆中最后一個記錄互換將堆頂記錄和堆中最后一個記錄互換 */ HeapAdjust(L，1，i-1)； 穩(wěn)定？穩(wěn)定？堆排序時間復(fù)雜度分析：堆排序時間復(fù)雜度分析：1. 對深度為對深度為 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ù) 不超過：不超過：(n-1)*2 log2n ; 因此，因此，堆排

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

40、：排序。即：將兩個位置相鄰的有序子序列將兩個位置相鄰的有序子序列歸并為一個有序的序列歸并為一個有序的序列。有有 序序 序序 列列 rl.n有序子序列有序子序列 rl.m有序子序列有序子序列 rm+1.n這個操作對順序表而言，是輕而易舉的。這個操作對順序表而言，是輕而易舉的。歸歸并并例：(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完整的歸并排序過程為：先分組再歸并。完整的歸并排序過程為：先分組再歸并。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ù)雜度分析：容易看出，對容易看出，對 n 個記錄進(jìn)

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

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

46、法以撲克牌排序為例以撲克牌排序為例: : 將撲克牌的排序看成由將撲克牌的排序看成由花色花色和和面值面值兩個關(guān)鍵字兩個關(guān)鍵字進(jìn)行排序的問題。若規(guī)定花色和面值的順序如下：進(jìn)行排序的問題。若規(guī)定花色和面值的順序如下： 花色：梅花花色：梅花 方塊方塊 紅桃紅桃 黑桃黑桃； 面值：面值：A23A2310JQK10JQK； 花色的優(yōu)先級高于面值；花色的優(yōu)先級高于面值；則一副牌從小到大的順序為：則一副牌從小到大的順序為： A,A,2,2, ,K K；A,A,2,2, ,K K； A,A,2,2, ,K K；A,A,2,2, ,K K。撲克牌的排序過程撲克牌的排序過程 訪法一訪法一(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排序過程中不需要根據(jù)排序過程中不需要根據(jù) “前一個前一個” 關(guān)鍵字的排序結(jié)果，將記錄序

48、列分割成若關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個子序列。干個子序列。最低位優(yōu)先最低位優(yōu)先LSD法：法：例例: :學(xué)生記錄含三個關(guān)鍵字學(xué)生記錄含三個關(guān)鍵字: :系別系別、班號班號和和班內(nèi)的序列號班內(nèi)的序列號，其中以，其中以系別系別為最主位關(guān)鍵字。為最主位關(guān)鍵字。 無序序列無序序列對對K2排序排序?qū)1排序排序?qū)0排序排序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的排序過程如下的排序過程

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

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

51、 的順序?qū)⒏鹘M的順序?qū)⒏鹘M“收集收集” 起來。起來。 實現(xiàn)基數(shù)排序時，為減少所需輔助存儲實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，可采用鏈表作存儲結(jié)構(gòu)?？臻g，可采用鏈表作存儲結(jié)構(gòu)。待排序記錄以鏈表為存儲結(jié)構(gòu)；待排序記錄以鏈表為存儲結(jié)構(gòu)；“分配分配” 時，按時，按當(dāng)前當(dāng)前“關(guān)鍵字位關(guān)鍵字位”將記錄將記錄分分 配到不同的配到不同的 “鏈隊列鏈隊列” 中，每個隊列中中，每個隊列中記記 錄的錄的 當(dāng)前當(dāng)前“關(guān)鍵字位關(guān)鍵字位” 相同；相同；“收集收集”時，時，將各隊列將各隊列按關(guān)鍵字從小到大按關(guān)鍵字從小到大首首 尾相鏈尾相鏈構(gòu)成一個新鏈表構(gòu)成一個新鏈表; ;按按LSDLSD對每個關(guān)鍵字位重復(fù)對每個關(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ù)排序的時間復(fù)雜度為基數(shù)排序的時間復(fù)雜度為O(d(n+rd)其中：分配為其中：分配為O(n) 收集為收集為O(rd)(rd為為“基基”) d為為“分配分配-收集收集”的趟數(shù)的趟數(shù)9.7 外部排序1. 插入類插入類直接插入排序直接插入排序和和希爾排序希爾排序2. 交換類交換類起泡排序起泡排序和和快速排序快速排序。3. 選擇類選擇類4. 歸并類歸并類5.

54、分配類分配類基數(shù)排序基數(shù)排序簡單選擇排序簡單選擇排序和和堆排序堆排序 歸并排序歸并排序9.8 9.8 算法總結(jié)算法總結(jié)排序方法排序方法 平均時間平均時間 最壞時間最壞時間 輔助空間輔助空間 穩(wěn)定性穩(wě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)定一、性能比較一、性能比較通過分析和比較，可以得出以下結(jié)論：通過分析和比較，可以得出以下結(jié)論：簡單排序一般只用于簡單排序一般只用于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á)到的最快的時間復(fù)雜度為的時間復(fù)雜度為O(nlogn)。(基數(shù)排序不是基于 “比較關(guān)鍵字”的排序方法，所以它不受這個限制。)二、內(nèi)部排序時間復(fù)雜度下限分析二、內(nèi)部排序時間復(fù)雜度下限分析 例如例如:對三個關(guān)鍵字進(jìn)行排序的判定樹對三個關(guān)鍵字進(jìn)行排序的判定樹如下：如下：K1K3K1K2K1K3K2K3K2 K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2樹上的樹上的每一次每一次“比較比較”都是都是必要必要的的;樹上的樹上的葉子葉子代表代表所有可能的排序結(jié)果所有可能的排序結(jié)果。nynnnn 一般而言一般而言, 對對n個關(guān)鍵字進(jìn)行排序個關(guān)鍵字進(jìn)行排序

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

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

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

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