Chapter10——排序

1、第十章第十章排序排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較10.8 外部排序外部排序10.1 概概 述述一、排序的定義一、排序的定義二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類三、內(nèi)部排序方法的分類一、什么是排序？一、什么是排序？ 排序是計算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序無序”的記錄序列調(diào)整為的記錄序列調(diào)整為“有序有序”的記錄序列。例如：將下列關(guān)鍵字序列52, 49, 80, 36, 14, 58,

2、61, 23, 97, 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97一般情況下，假設(shè)含n個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作操作稱作排序排序。排序算法的穩(wěn)定性：排序算法的穩(wěn)定性： 如果待排序的序列中，存在多個具有相同關(guān)鍵字的記錄，若經(jīng)過排序這些記錄的相對次序保持不變，則稱這種排序算法是穩(wěn)定穩(wěn)定的；經(jīng)過排序這些記錄的相對次序發(fā)生了改變，則稱這種排

3、序算法是不穩(wěn)定不穩(wěn)定的。二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序 待排序記錄存放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程，為內(nèi)部排序內(nèi)部排序； 若待排序記錄的數(shù)量很大，以至內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程，為外部排序外部排序。三、內(nèi)部排序的方法三、內(nèi)部排序的方法內(nèi)部排序的過程是一個逐步擴(kuò)大逐步擴(kuò)大記錄的有序序列長度有序序列長度的過程。經(jīng)過一趟排序經(jīng)過一趟排序有序序列區(qū)無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū) 按排序過程中依據(jù)的不同原則按排序過程中依據(jù)的不同原則 插入排序插入排序 交換排序交換排序 選擇排序選擇排序 歸并排序歸并排序 基數(shù)排序基數(shù)排序 按排序

4、過程所需的工作量按排序過程所需的工作量 簡單的排序方法，其時間復(fù)雜度為簡單的排序方法，其時間復(fù)雜度為O(n2) 先進(jìn)的排序方法，其時間復(fù)雜度為先進(jìn)的排序方法，其時間復(fù)雜度為O(nlogn) 基數(shù)排序，其時間復(fù)雜度為基數(shù)排序，其時間復(fù)雜度為O(d.n)1. 插入類插入類將無序子序列中的一個或幾個記錄“插入插入”到有序序列中，從而增加記錄的有序子序列的長度。2. 交換類交換類通過“交換交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。3. 選擇類選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，

5、以此方法增加記錄的有序子序列的長度。4. 歸并類歸并類通過“歸并歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。5. 其它方法其它方法待排記錄的數(shù)據(jù)類型定義如下待排記錄的數(shù)據(jù)類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長度待排順序表最大長度typedef int KeyType; / 關(guān)鍵字類型為整數(shù)類型關(guān)鍵字類型為整數(shù)類型typedef struct KeyType key; / 關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng) InfoType otherinfo; / 其它數(shù)據(jù)項(xiàng)其它數(shù)據(jù)項(xiàng) RcdType; / 記錄類型記錄類型typedef struct RcdType

6、 rMAXSIZE+1; / r0閑置閑置 int length; / 順序表長度順序表長度 SqList; / 順序表類型順序表類型 10. 2 插插 入入 排排 序序一趟直接插入排序的基本思想： 把把n n個記錄的序列劃分為已排序部分和個記錄的序列劃分為已排序部分和未排序部分，即在涉及第未排序部分，即在涉及第i i個記錄個記錄R Ri i時時, ,（R R1 1, . . . ,R, . . . ,Ri-1i-1）是已排好的有序部分，）是已排好的有序部分，（R Ri i,R,Ri+1i+1, . . . ,R, . . . ,Rn n）屬于未排序部分。）屬于未排序部分。找出找出RiRi在此

7、有序序列中應(yīng)插入的位置，將在此有序序列中應(yīng)插入的位置，將RiRi插入。原位置上的記錄至插入。原位置上的記錄至RiRi均順序后移均順序后移一位。一位。有序序列R1.i-1Ri無序序列 Ri.n有序序列R1.i無序序列 Ri+1.n實(shí)現(xiàn)實(shí)現(xiàn)“一趟插入排序一趟插入排序”可分三步進(jìn)行：可分三步進(jìn)行：3將Ri 插入插入(復(fù)制)到Rj+1的位置上。2將Rj+1.i-1中的所有記錄記錄均后移后移 一個位置；1在R1.i-1中查找查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；直接插入排序直接插入排序（基于順序查找）（基于順序查找）不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的不同的具體實(shí)現(xiàn)方法

8、導(dǎo)致不同的算法描述算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）一、直接插入排序一、直接插入排序利用 “順序查找順序查找”實(shí)現(xiàn)“在R1.i-1中查找查找Ri的插入位置”算法的實(shí)現(xiàn)要點(diǎn)：算法的實(shí)現(xiàn)要點(diǎn)：從Ri-1起向前進(jìn)行順序查找， 監(jiān)視哨設(shè)置在R0；R0 = Ri; / 設(shè)置設(shè)置“哨兵哨兵”循環(huán)結(jié)束表明Ri的插入位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從后往前找從后往前找j=i-1插入位置插入位置 對于在查找過程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時

9、實(shí)現(xiàn)記錄向后移動；for (j=i-1; R0.keyRj.key; -j) Rj+1 = Rj ; R0jRij= i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置插入位置令 i = 2，3，, n, 實(shí)現(xiàn)整個序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; 直接插入排序示例直接插入排序示例 初始狀態(tài)初始狀態(tài) 18 12 10 12 30 16 第第1趟（趟（i=2） (12) 12 18 10 12 30 16 第第2趟（趟（i=3） (10) 10 12 18 12 30 16 第第3趟（趟

10、（i=4） (12) 10 12 12 18 30 16 第第4趟（趟（i=5） (30) 10 12 12 18 30 16 第第5趟（趟（i=6） (16) 10 12 12 16 18 30待排序記錄序列為待排序記錄序列為(18(18，1212，1010，1212，3030，1616）簡單插入排序每一趟執(zhí)行后的序列狀態(tài)簡單插入排序每一趟執(zhí)行后的序列狀態(tài): :監(jiān)視哨監(jiān)視哨void InsertionSort ( SqList &L ) / 對順序表對順序表 L 作直接插入排序作直接插入排序 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.ke

11、y) / InsertSortL.r0 = L.ri; / 復(fù)制為監(jiān)視哨復(fù)制為監(jiān)視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移記錄后移L.rj+1 = L.r0; / 插入到正確位置插入到正確位置內(nèi)部排序的時間分析時間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作基本操作有兩個：(2) “移動移動”記錄。(1) “比較比較”序列中兩個關(guān)鍵字的大小；對于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆

12、序有序）：“比較”的次數(shù)：112nni02) 1)(4() 1(2nnini“移動”的次數(shù)：“移動”的次數(shù)：2) 1)(4() 1(2nnini對于直接插入排序：其其時間復(fù)雜度時間復(fù)雜度為為O(n2)適用于當(dāng)待排序記錄的數(shù)量很小時 一般情況下，待排序記錄是隨機(jī)的，即一般情況下，待排序記錄是隨機(jī)的，即待排序列中的記錄可能出現(xiàn)的各種排列的概待排序列中的記錄可能出現(xiàn)的各種排列的概率相同，則可取最小值和最大值的平均值，率相同，則可取最小值和最大值的平均值，作為直接插入排序時所需進(jìn)行關(guān)鍵字的比較作為直接插入排序時所需進(jìn)行關(guān)鍵字的比較次數(shù)和移動記錄的次數(shù)，約為次數(shù)和移動記錄的次數(shù)，約為n24. 因?yàn)?R1

13、.i-1 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找折半查找實(shí)現(xiàn)“在R1.i-1中查找查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩逭郯氩迦肴肱判?。二、折半插入排序二、折半插入排序void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移記錄后移L.rhigh+1 = L.r0; / 插入插入low = 1; high = i-1;while (low=high) m = (low+high)/

14、2; / 折半折半if (L.r0.key L.rm.key) high = m-1; / 插入點(diǎn)在低半?yún)^(qū)插入點(diǎn)在低半?yún)^(qū)else low = m+1; / 插入點(diǎn)在高半?yún)^(qū)插入點(diǎn)在高半?yún)^(qū)14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r對于折半插入排序，其，其時間復(fù)雜度時間復(fù)雜度為為O(n2)折半插入排序適用于當(dāng)待排序記錄的數(shù)量很大時，可大幅度降低關(guān)鍵字的比較次數(shù)。 三、希爾排序三、希爾排序(又稱縮小增量排

15、序又稱縮小增量排序) 基本思想：對待排記錄序列先作基本思想：對待排記錄序列先作“宏宏觀觀”調(diào)整，再作調(diào)整，再作“微觀微觀”調(diào)整。調(diào)整。 所謂所謂“宏觀宏觀”調(diào)整，指的是，調(diào)整，指的是，“跳躍跳躍式式”的插入排序。即先將整個待排記錄序列分的插入排序。即先將整個待排記錄序列分割成若干子序列分別進(jìn)行直接插入排序，割成若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄待整個序列中的記錄“基本有序基本有序”時，再時，再對全體記錄進(jìn)行一次直接插入排序。對全體記錄進(jìn)行一次直接插入排序。 具體做法為：具體做法為：將記錄序列分成若干子序列，分別對每個子將記錄序列分成若干子序列，分別對每個子序列進(jìn)行插入排序。序列

16、進(jìn)行插入排序。其中，其中，d d 稱為增量，它的值在排序過程中從大到稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序小逐漸縮小，直至最后一趟排序減為減為 1 1。例如：將 n 個記錄分成 d 個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 初始關(guān)鍵字初始關(guān)鍵字 49 38 65 97 76 13 27 49 55 04 49 13 38 27 65 49 97 55 76 04 二趟排序結(jié)果二趟排序結(jié)果 13 04 49 38 27 49 55 65 97 76設(shè)增量設(shè)增量 d =5設(shè)增量設(shè)

17、增量 d =3設(shè)增量設(shè)增量 d =1一趟排序結(jié)果一趟排序結(jié)果 13 27 49 55 04 49 38 65 97 76 13 55 38 76 27 04 65 49 49 97三趟排序結(jié)果三趟排序結(jié)果 04 13 27 38 49 49 55 65 76 97void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置記錄后移，查找插入位置 L.rj+dk = L.r0; / 插入插入

18、 / if / ShellInsertvoid ShellSort (SqList &L, int dlta, int t) / 增量為增量為dlta 的希爾排序的希爾排序 for (k=0; k Ri+1.key,Ri.key Ri+1.key,則交換則交換RiRi和和Ri+1Ri+1的位置。第一趟全部比較完畢的位置。第一趟全部比較完畢后后RnRn是序列中最大的記錄。是序列中最大的記錄。 再從再從R1R1開始兩兩比較開始兩兩比較RiRi和和Ri+1 Ri+1 (i=1,2,.,n-2) (i=1,2,.,n-2) 的關(guān)鍵字的大小，若的關(guān)鍵字的大小，若Ri.key Ri+1.keyRi.key

19、 Ri+1.key則交換則交換RiRi和和Ri+1Ri+1的位置。第二趟全部比較完畢后的位置。第二趟全部比較完畢后Rn-1Rn-1是序是序列中次大記錄。列中次大記錄。 如此反復(fù)，進(jìn)行如此反復(fù)，進(jìn)行n-1n-1趟冒泡排序后所有待排序趟冒泡排序后所有待排序的的n n個記錄序列按關(guān)鍵字有序。個記錄序列按關(guān)鍵字有序。假設(shè)在排序過程中，記錄序列R1.n的狀態(tài)為：第 i 趟起泡排序無序序列R1.n-i+1有序序列 Rn-i+2.nn-i+1無序序列R1.n-i有序序列 Rn-i+1.n比較相鄰記錄，將關(guān)關(guān)鍵字最大的記錄交換鍵字最大的記錄交換到 n-i+1 的位置上冒泡排序示例冒泡排序示例初始狀態(tài) 65 9

20、7 76 13 27 49 58 第1趟（j=16）65 76 13 27 49 58 97第2趟（j=15）65 13 27 49 58 76 97第3趟（j=14）13 27 49 58 65 76 97第4趟（j=13）13 27 49 58 65 76 97第5趟（j=12）13 27 49 58 65 76 97第6趟（j=1） 13 27 49 58 65 76 97設(shè)待排記錄序列的關(guān)鍵字為設(shè)待排記錄序列的關(guān)鍵字為(65,97,76,13,27,49,58)(65,97,76,13,27,49,58)冒泡排序每一趟執(zhí)行后的序列狀態(tài)如下：冒泡排序每一趟執(zhí)行后的序列狀態(tài)如下：冒泡排序算

21、法冒泡排序算法void bubblesort(Elem R , int n) / 設(shè)待排記錄放在設(shè)待排記錄放在R1R1到到RnRn中中 for(i=1;in;i+) for(j=1;jRj+1.key) Swap(Rj, Rj+1); /交換元素交換元素 冒泡排序的改進(jìn)冒泡排序的改進(jìn)按前面給出的算法，對具有個按前面給出的算法，對具有個n n記錄的記錄的待排序序列要執(zhí)行待排序序列要執(zhí)行n-1n-1趟冒泡排序。從上例趟冒泡排序。從上例中我們發(fā)現(xiàn)，執(zhí)行到第中我們發(fā)現(xiàn)，執(zhí)行到第3 3趟后記錄序列已經(jīng)趟后記錄序列已經(jīng)有序，后面的有序，后面的3 3趟冒泡趟冒泡“空跑空跑”沒有發(fā)沒有發(fā)生交換。因此應(yīng)該對算法

22、加以改進(jìn)：能生交換。因此應(yīng)該對算法加以改進(jìn)：能“記住記住”每趟加工時是否發(fā)生了每趟加工時是否發(fā)生了“交換交換”，若某一趟未發(fā)生若某一趟未發(fā)生“交換交換”，表示此時記錄，表示此時記錄序列已經(jīng)有序，應(yīng)結(jié)束排序過程。序列已經(jīng)有序，應(yīng)結(jié)束排序過程。改進(jìn)的冒泡排序算法改進(jìn)的冒泡排序算法void bubblesort(Elem R , int n) i=n; flag=1; while(i1)&flag); flag=0; for(j=1;jRj+1.key)Swap(Rj, Rj+1); flag=1; i -; 冒泡排序的進(jìn)一步改進(jìn)冒泡排序的進(jìn)一步改進(jìn)按前面給出的改進(jìn)算法，按前面給出的改進(jìn)算法，一般情

23、況下，每經(jīng)過一趟“起泡”，“i 減一”，但并不是每趟都如此。因此應(yīng)該對算法進(jìn)但并不是每趟都如此。因此應(yīng)該對算法進(jìn)一步加以改進(jìn)：一步加以改進(jìn)： “ “記住記住”本趟進(jìn)行過交換本趟進(jìn)行過交換的最后一個記錄的位置，那么，在下一躺的最后一個記錄的位置，那么，在下一躺起泡時，就可減少比較次數(shù)。起泡時，就可減少比較次數(shù)。注意注意: :2. 一般情況下，每經(jīng)過一趟“起泡”，“i 減一”，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i; j+) if (Rj+1.key 1) / while / BubbleSorti = n;i = lastEx

24、changeIndex; / 本趟進(jìn)行過交換的本趟進(jìn)行過交換的 / 最后一個記錄的位置最后一個記錄的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下記下進(jìn)行交換的記錄位置進(jìn)行交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;時間分析時間分析: :最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進(jìn)行一趟起泡只需進(jìn)行一趟起泡“比較比較”的次數(shù)：的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序

25、列中逆序有序）： 需進(jìn)行需進(jìn)行n-1趟起泡趟起泡“比較比較”的次數(shù)：的次數(shù)：0“移動移動”的次數(shù)：的次數(shù)：“移動移動”的次數(shù)：的次數(shù)：n-12) 1() 1(2nnini2) 1(3) 1(32nnini起泡排序總的起泡排序總的時間復(fù)雜度時間復(fù)雜度為為O(nO(n2 2) ) 目標(biāo)：目標(biāo)：找一個記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動移動至該記錄之前至該記錄之前，反之，凡關(guān)鍵字大于樞軸關(guān)鍵字大于樞軸的記錄均移動至該記錄之后移動至該記錄之后。致使一趟排序一趟排序之后，記錄的無序序列Rs.t將分分割成兩部分割成兩部分：Rs.i-1和Ri+1.t，且 Rj.k

26、ey Ri.key Rj.key (sji-1) 樞軸樞軸 (i+1jt)。二、一趟快速排序（一次劃分）二、一趟快速排序（一次劃分）52 49 80 36 14 58 61 97 23 75stlowhigh設(shè)設(shè) Rs=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關(guān)鍵字進(jìn)行比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進(jìn)行比較，要求Rlow.key 樞軸的關(guān)鍵字high23low8014low52例如例如R052lowhighlowhighhighhigh 可見，經(jīng)過“一次劃分一次劃分” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58

27、, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過程中，設(shè)立了兩個指針： low 和high，它們的初值分別為： s 和 t， 之后逐漸減小 high，增加 low，并保證 Rhigh.key52，和 Rlow.key52,否則進(jìn)行記錄的“交換”。int Partition (RedType& R, int low, int high) pivotkey = Rlow.key; while (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhig

28、h & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 返回樞軸所在位置返回樞軸所在位置 / Partitionint Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸樞軸 while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索從右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索

29、從左向右搜索Rhigh = Rlow;Rlow = R0; return low;三、快速排序三、快速排序 首先對無序的記錄序列進(jìn)行“一次劃分一次劃分”，之后分別分別對分割所得兩個子序列“遞歸遞歸”進(jìn)行進(jìn)行快速排序快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸樞軸一次劃分分別進(jìn)行快速排序void QSort (RedType & R, int s, int t ) / 對記錄序列對記錄序列Rs.t進(jìn)行快速排序進(jìn)行快速排序 if (s t-1) / 長度大于長度大于1 / QSort pivotloc = Partition(R, s, t); / 對對 Rs.t

30、進(jìn)行一次劃分進(jìn)行一次劃分 QSort(R, s, pivotloc-1); / 對低子序列遞歸排序，對低子序列遞歸排序，pivotloc是樞軸位置是樞軸位置 QSort(R, pivotloc+1, t); / 對高子序列遞歸排序?qū)Ω咦有蛄羞f歸排序void QuickSort( SqList & L) / 對順序表進(jìn)行快速排序?qū)樞虮磉M(jìn)行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調(diào)用函數(shù) Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。四、快速排序的時間分析四、快速排序的時間分析假設(shè)一次劃分所得樞軸位置 i=k，則對n

31、個記錄進(jìn)行快排所需時間： 其中 Tpass(n)為對 n 個記錄進(jìn)行一次劃分所需時間。 若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則 k 取 1 至 n 中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)nkavgavgavgknTkTnCnnT1)() 1(1)(設(shè) Tavg(1)b則可得結(jié)果：) 1ln() 1)(22()(nncbnTavg結(jié)論結(jié)論: 快速排序的時間復(fù)雜度為快速排序的時間復(fù)雜度為O(nlogn)由此可得快速排序所需時間的平均值為： 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判驎r，快速排

32、序?qū)⑼懟癁槠鹋菖判?，其時間復(fù)雜度為O(n2)。 為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前，進(jìn)行“予處理予處理”，即： 先對 R(s).key, R(t).key 和 R(s+t)/2.key，進(jìn)行相互比較，然后取取關(guān)鍵字為 “三者之中三者之中”的記錄為樞軸為樞軸記錄。10.4 選選 擇擇 排排 序序簡簡 單單 選選 擇擇 排排 序序堆堆 排排 序序樹樹 形形 選選 擇擇 排排 序序一、簡單選擇排序一、簡單選擇排序基本思想基本思想： 一躺簡單選擇排序的操作為：通過一躺簡單選擇排序的操作為：通過n-in-i次關(guān)鍵字間的比較，從次關(guān)鍵字間的比較，從n-i+1n-i+1個記錄個記錄中選出關(guān)鍵字最小的記

33、錄，并和第中選出關(guān)鍵字最小的記錄，并和第i i（1in)1in)個記錄交換之。個記錄交換之。 對對L.r1.n中記錄進(jìn)行簡單選擇排中記錄進(jìn)行簡單選擇排序的算法為：序的算法為：令令i從從1至至n-1,進(jìn)行進(jìn)行n-1趟選趟選擇操作。擇操作。 假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列R1.i-1無序序列 Ri.n 第 i 趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n簡單選擇排序簡單選擇排序初始狀態(tài)初始狀態(tài) 2 7 2 4 3 1 第第1趟（趟（i=1）1 7 2 4 3 2第第2趟（趟（i=2）1 2 7 4 3 2 第第3趟（趟（i=3）1 2 2 4 3 7

34、第第4趟（趟（i=4）1 2 2 3 4 7 第第5趟（趟（i=5）1 2 2 3 4 7待排序記錄序列的關(guān)鍵字序列為（待排序記錄序列的關(guān)鍵字序列為（2 2，7 7，2 2，4 4，3 3，1 1）簡單選擇排序每一趟執(zhí)行后的序列狀態(tài)：簡單選擇排序每一趟執(zhí)行后的序列狀態(tài)：簡單選擇排序的算法描述如下：void SelectSort (Elem R, int n ) / 對記錄序列對記錄序列R1.n作簡單選擇排序。作簡單選擇排序。 for (i=1; in; +i) / 選擇第選擇第 i 小的記錄，并交換到位小的記錄，并交換到位 / SelectSortj = SelectMinKey(R, i);

35、 / 在在 Ri.n 中選擇關(guān)鍵字最小的記錄中選擇關(guān)鍵字最小的記錄if (i!=j) RiRj; / 與第與第 i 個記錄交換個記錄交換時間性能分析時間性能分析 對 n 個記錄進(jìn)行簡單選擇排序，所需進(jìn)行的 關(guān)鍵字間的比較次數(shù)關(guān)鍵字間的比較次數(shù) 總計為：移動記錄的次數(shù)移動記錄的次數(shù)，最小值為 0, 最大值為3(n-1) 。2) 1()(11nninni其時間復(fù)雜度為其時間復(fù)雜度為O(nO(n2 2) )二、樹形選擇排序二、樹形選擇排序 樹形選擇排序樹形選擇排序又稱又稱錦標(biāo)賽排序錦標(biāo)賽排序，是，是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。方法?；舅枷耄夯舅枷耄?

36、首先對首先對n n個記錄的關(guān)鍵字進(jìn)行兩兩個記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中比較，然后在其中n/2n/2個較小者之間再個較小者之間再進(jìn)行兩兩比較，如此重復(fù)，直至選出最進(jìn)行兩兩比較，如此重復(fù)，直至選出最小關(guān)鍵字的記錄為止。小關(guān)鍵字的記錄為止。384965977613274938651327381313選出選出最小關(guān)鍵字最小關(guān)鍵字13例：例： 49 38 65 97 76 13 27 493849659776274938657627382727 將葉結(jié)點(diǎn)中的最小關(guān)鍵字將葉結(jié)點(diǎn)中的最小關(guān)鍵字(13)改為最大改為最大值，然后修改該葉子結(jié)點(diǎn)到根的路徑上各值，然后修改該葉子結(jié)點(diǎn)到根的路徑上各結(jié)點(diǎn)的關(guān)鍵字

37、，則根結(jié)點(diǎn)的關(guān)鍵字即為次結(jié)點(diǎn)的關(guān)鍵字，則根結(jié)點(diǎn)的關(guān)鍵字即為次小關(guān)鍵字。由此選出小關(guān)鍵字。由此選出次小關(guān)鍵字次小關(guān)鍵字27。38496597764938657649384938 同理，可依次選出從小到大的所有關(guān)同理，可依次選出從小到大的所有關(guān)鍵字。居鍵字。居第三的關(guān)鍵字為第三的關(guān)鍵字為38。 樹形選擇排序的時間復(fù)雜度分析：樹形選擇排序的時間復(fù)雜度分析： 由于含由于含n個葉子結(jié)點(diǎn)的完全二叉樹的深度個葉子結(jié)點(diǎn)的完全二叉樹的深度為為 log2n +1次，則在樹形選擇排序中，除了最次，則在樹形選擇排序中，除了最小關(guān)鍵字之外，每選擇一個次小關(guān)鍵字僅需進(jìn)小關(guān)鍵字之外，每選擇一個次小關(guān)鍵字僅需進(jìn)行行 log2

38、n 次比較，因此，次比較，因此，樹形選擇排序的樹形選擇排序的時間時間復(fù)雜度復(fù)雜度為為O(nlog2n)。 這種排序方法尚有輔助存儲空間較多，和這種排序方法尚有輔助存儲空間較多，和“最大值最大值”進(jìn)行多余的比較等特點(diǎn)。進(jìn)行多余的比較等特點(diǎn)。 為了彌補(bǔ)這一缺點(diǎn)，可采用另一形式的選為了彌補(bǔ)這一缺點(diǎn)，可采用另一形式的選擇排序擇排序堆排序。堆排序。三、堆排序三、堆排序堆是滿足下列性質(zhì)的數(shù)列r1, r2, ，rn：或或122iiiirrrr122iiiirrrr堆的定義堆的定義:12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例如例如:是是小頂堆小頂堆12, 36, 2

39、7, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆(小頂堆小頂堆)(大頂堆大頂堆)rir2i r2i+1 若將該數(shù)列視作完全二叉樹，則 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。1236276549817355403498例如例如:是堆是堆14不不 堆排序即是利用堆排序即是利用堆的特性堆的特性對記錄序?qū)τ涗浶蛄羞M(jìn)行排序的一種排序方法。列進(jìn)行排序的一種排序方法。例如：例如：建大頂堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交換 98

40、和 12重新調(diào)整為大頂堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 經(jīng)過篩選 如何由一個無序序列如何由一個無序序列“建堆建堆”？實(shí)現(xiàn)堆排序需要解決兩個問題實(shí)現(xiàn)堆排序需要解決兩個問題: 如何在輸出堆頂元素之后，調(diào)如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？整剩余元素成為一個新的堆？定義堆類型為定義堆類型為:typedef SqList HeapType; / 堆采用順序表表示之堆采用順序表表示之如何在輸出堆頂元素之后，調(diào)整如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個新的堆？剩

41、余元素成為一個新的堆？ 假設(shè)在輸出堆頂元素之后，以假設(shè)在輸出堆頂元素之后，以堆中最后一個元素替代之，此時，堆中最后一個元素替代之，此時，根結(jié)點(diǎn)的左右子樹均為堆，則僅需根結(jié)點(diǎn)的左右子樹均為堆，則僅需自上至下進(jìn)行調(diào)整即可。自堆頂至自上至下進(jìn)行調(diào)整即可。自堆頂至葉子的調(diào)整過程為葉子的調(diào)整過程為“篩選篩選”。 所謂“篩選篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整調(diào)整”根根結(jié)點(diǎn)結(jié)點(diǎn)使整個二叉樹也成為一個堆。堆堆篩選篩選98814973556412362740例如例如:是大頂堆是大頂堆12但在但在 98 98 和和 12 12 進(jìn)行互換之后，它就進(jìn)行互換之后，它就不不是堆了，是堆了，因此，需

42、要對它進(jìn)行“篩選”。98128173641298比較比較比較void HeapAdjust (RcdType &R, int s, int m) / 已知已知 Rs.m中記錄的關(guān)鍵字除中記錄的關(guān)鍵字除 Rs 之外均之外均 / 滿足堆的特征，本函數(shù)自上而下調(diào)整滿足堆的特征，本函數(shù)自上而下調(diào)整 Rs 的的 / 關(guān)鍵字，使關(guān)鍵字，使 Rs.m 也成為一個大頂堆也成為一個大頂堆 / HeapAdjustrc = Rs; / 暫存暫存 Rs for ( j=2*s; j= Rj.key ) break; / 再作再作“根根”和和“子樹根子樹根”之間的比之間的比較，較， / 若若“=”成立，則說明已找到成

43、立，則說明已找到 rc 的插的插 / 入位置入位置 s ，不需要繼續(xù)往下調(diào)整，不需要繼續(xù)往下調(diào)整Rs = Rj; s = j; / 否則記錄上移，尚需繼續(xù)往下調(diào)整否則記錄上移，尚需繼續(xù)往下調(diào)整if ( jm & Rj.keyRj+1.key ) +j; / 左左/右右“子樹根子樹根”之間先進(jìn)行相互比較之間先進(jìn)行相互比較 / 令令 j 指示關(guān)鍵字較大記錄的位置指示關(guān)鍵字較大記錄的位置10.5 歸歸 并并 排排 序序 歸并排序的過程基于下列基本基本思想思想進(jìn)行： 將兩個或兩個以上的有序子序列 “歸并” 為一個有序序列。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰位置相鄰的記錄有序子

44、序列歸并為一個一個記錄的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n這個操作對順序表而言，是輕而易舉的。void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有序的記錄序列將有序的記錄序列 SRi.m 和和 SRm+1.n / 歸并為有序的記錄序列歸并為有序的記錄序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 將將SR中記錄由小到大地并入中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk =

45、 SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 將剩余的將剩余的 SRi.m 復(fù)制到復(fù)制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的將剩余的 SRj.n 復(fù)制到復(fù)制到 TR歸并排序的算法歸并排序的算法 如果記錄無序序列 Rs.t 的兩部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。 由此，應(yīng)該先分別對這兩部分進(jìn)行 2-路歸并排序。2-2-路歸并排序的過程路歸并排序的過程初始狀態(tài)初始狀態(tài) 25 57 4837 1292 86第

46、趟歸并第趟歸并 25 57 37 48 12 92 86第趟歸并第趟歸并 25 374857 128692第趟歸并第趟歸并 12 253748578692待排記錄序列為待排記錄序列為(25,57,48,37,12,92,86)(25,57,48,37,12,92,86)路歸并排序每一趟執(zhí)行后的序列狀態(tài)路歸并排序每一趟執(zhí)行后的序列狀態(tài): :void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將將SRs.t 歸并排序?yàn)闅w并排序?yàn)?TR1s.t if (s= =t) TR1s=SRs; else / Msort m = (s+t)/2; /

47、 將將SRs.t平分為平分為SRs.m和和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將遞歸地將SRs.m歸并為有序的歸并為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地遞歸地SRm+1.t歸并為有序的歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將將TR2s.m和和TR2m+1.t歸并到歸并到TR1s.tvoid MergeSort (SqList &L) / 對順序表對順序表 L 作作2-路歸并排序路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort 容

48、易看出，對 n 個記錄進(jìn)行歸并排序的時間復(fù)雜度為(nlogn)。即： 每一趟歸并的時間復(fù)雜度為 O(n)， 總共需進(jìn)行 log2n 趟。 基數(shù)排序基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。多關(guān)鍵字的排序多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序10.6 基基 數(shù)數(shù) 排排 序序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序 n 個記錄的序列個記錄的序列 R1, R2, ，Rn對關(guān)鍵字對關(guān)鍵字 (Ki0, Ki1,Kid-1) ) 有序有序是指： 其中其中: : K0 被稱為被稱為 “最主最主”位關(guān)鍵字位關(guān)鍵字Kd-1 被稱為被稱為 “最次最次”位關(guān)鍵字位關(guān)鍵字 對于序列中任

49、意兩個記錄 Ri 和 Rj(1ijn) 都滿足滿足下列(詞典詞典)有序有序關(guān)系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) ) 實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法: :最低位優(yōu)先最低位優(yōu)先LSD法法最高位優(yōu)先最高位優(yōu)先MSD法 先對先對K0進(jìn)行排序進(jìn)行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進(jìn)行排序，.， 依次類推，直至最后直至最后對最次位關(guān)鍵字排序完成為止對最次位關(guān)鍵字排序完成為止。最高位優(yōu)先最高位優(yōu)先MSD法 先對 Kd-1 進(jìn)行排序，然后對 Kd-2 進(jìn)行排序，依次類推，直至對最主位直至

50、對最主位關(guān)鍵字關(guān)鍵字 K0 排序完成為止排序完成為止。 排序過程中不需要根據(jù) “前一個” 關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(“前一個”關(guān)鍵字不同的)子序列。最低位優(yōu)先最低位優(yōu)先LSD法法例如例如: :學(xué)生記錄含三個關(guān)鍵字:系別系別、班號班號和班內(nèi)的序列號班內(nèi)的序列號，其中以系別為最主位關(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

51、,2,30LSD的排序過程如下:二、鏈?zhǔn)交鶖?shù)排序二、鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按的取值范圍相同，則按LSD法進(jìn)行排序時，可法進(jìn)行排序時，可以采用以采用“分配分配- -收集收集”的方法，其好處是不需要的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。進(jìn)行關(guān)鍵字間的比較。對于數(shù)字型或字符型的對于數(shù)字型或字符型的單關(guān)鍵字單關(guān)鍵字，可以，可以看看成成是由多個數(shù)位或多個字符構(gòu)成的是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字多關(guān)鍵字，此時可以此時可以采用采用這種這種“分配分配- -收集收集”的辦法的辦法進(jìn)行排進(jìn)行排序序，稱作基數(shù)排序法稱作基數(shù)排序

52、法。例如：例如：對下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個位數(shù)” 取值分別為 0, 1, , 9 “分配分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “收集收集” 在一起； 然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“收集收集” ” 在一起； 最后按其“百位數(shù)”重復(fù)一遍上述操作。在計算機(jī)上實(shí)現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： 待排序記錄以指針相鏈，構(gòu)成一個鏈表；待排序記錄以

53、指針相鏈，構(gòu)成一個鏈表； “分配分配” ” 時，按當(dāng)前時，按當(dāng)前“關(guān)鍵字位關(guān)鍵字位”所取值，所取值，將記錄分配到不同的將記錄分配到不同的 “ “鏈隊(duì)列鏈隊(duì)列” ” 中，每個隊(duì)列中記中，每個隊(duì)列中記錄的錄的 “ “關(guān)鍵字位關(guān)鍵字位” ” 相同；相同； “收集收集”時，按當(dāng)前關(guān)鍵字位取值從小到大時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個鏈表將各隊(duì)列首尾相鏈成一個鏈表; ; 對每個關(guān)鍵字位均重復(fù)對每個關(guān)鍵字位均重復(fù) 2) 和和 3) 兩步。兩步。例如：p369367167239237138230139進(jìn)行第一次分配進(jìn)行第一次分配進(jìn)行第一次收集進(jìn)行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138369239139369 239139138進(jìn)行第二次分配進(jìn)行第二次分配p230237138239139p230367167237138369239139f3 r3f6 r6230 237138239139367 167369367167369進(jìn)行第二次收集 進(jìn)行第三次收集之后便得到記錄的有序序列進(jìn)行第三次收集之后便得到記錄的有序序列f1 r1p230237138239139367167369進(jìn)行第三次分配進(jìn)行第三次分配f2 r2f3 r3138 139167230