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ì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序無(wú)序”的記錄序列調(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個(gè)記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作操作稱作排序排序。排序算法的穩(wěn)定性：排序算法的穩(wěn)定性： 如果待排序的序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，若經(jīng)過(guò)排序這些記錄的相對(duì)次序保持不變，則稱這種排序算法是穩(wěn)定穩(wěn)定的；經(jīng)過(guò)排序這些記錄的相對(duì)次序發(fā)生了改變，則稱這種排

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

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

5、以此方法增加記錄的有序子序列的長(zhǎng)度。4. 歸并類歸并類通過(guò)“歸并歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長(zhǎng)度。5. 其它方法其它方法待排記錄的數(shù)據(jù)類型定義如下待排記錄的數(shù)據(jù)類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長(zhǎng)度待排順序表最大長(zhǎng)度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; / 順序表長(zhǎng)度順序表長(zhǎng)度 SqList; / 順序表類型順序表類型 10. 2 插插 入入 排排 序序一趟直接插入排序的基本思想： 把把n n個(gè)記錄的序列劃分為已排序部分和個(gè)記錄的序列劃分為已排序部分和未排序部分，即在涉及第未排序部分，即在涉及第i i個(gè)記錄個(gè)記錄R Ri i時(shí)時(shí), ,（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無(wú)序序列 Ri.n有序序列R1.i無(wú)序序列 Ri+1.n實(shí)現(xiàn)實(shí)現(xiàn)“一趟插入排序一趟插入排序”可分三步進(jìn)行：可分三步進(jìn)行：3將Ri 插入插入(復(fù)制)到Rj+1的位置上。2將Rj+1.i-1中的所有記錄記錄均后移后移 一個(gè)位置；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插入位置插入位置 對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時(shí)

9、實(shí)現(xiàn)記錄向后移動(dòng)；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)整個(gè)序列的排序。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）簡(jiǎn)單插入排序每一趟執(zhí)行后的序列狀態(tài)簡(jiǎn)單插入排序每一趟執(zhí)行后的序列狀態(tài): :監(jiān)視哨監(jiān)視哨void InsertionSort ( SqList &L ) / 對(duì)順序表對(duì)順序表 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í)間分析時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作基本操作有兩個(gè)：(2) “移動(dòng)移動(dòng)”記錄。(1) “比較比較”序列中兩個(gè)關(guān)鍵字的大??；對(duì)于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆

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

13、.i-1 是一個(gè)按關(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對(duì)于折半插入排序，其，其時(shí)間復(fù)雜度時(shí)間復(fù)雜度為為O(n2)折半插入排序適用于當(dāng)待排序記錄的數(shù)量很大時(shí)，可大幅度降低關(guān)鍵字的比較次數(shù)。 三、希爾排序三、希爾排序(又稱縮小增量排

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

16、進(jìn)行插入排序。其中，其中，d d 稱為增量，它的值在排序過(guò)程中從大到稱為增量，它的值在排序過(guò)程中從大到小逐漸縮小，直至最后一趟排序小逐漸縮小，直至最后一趟排序減為減為 1 1。例如：將 n 個(gè)記錄分成 d 個(gè)子序列： 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是序列中最大的記錄。是序列中最大的記錄。 再?gòu)脑購(gòu)腞1R1開(kāi)始兩兩比較開(kāi)始兩兩比較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個(gè)記錄序列按關(guān)鍵字有序。個(gè)記錄序列按關(guān)鍵字有序。假設(shè)在排序過(guò)程中，記錄序列R1.n的狀態(tài)為：第 i 趟起泡排序無(wú)序序列R1.n-i+1有序序列 Rn-i+2.nn-i+1無(wú)序序列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)按前面給出的算法，對(duì)具有個(gè)按前面給出的算法，對(duì)具有個(gè)n n記錄的記錄的待排序序列要執(zhí)行待排序序列要執(zhí)行n-1n-1趟冒泡排序。從上例趟冒泡排序。從上例中我們發(fā)現(xiàn)，執(zhí)行到第中我們發(fā)現(xiàn)，執(zhí)行到第3 3趟后記錄序列已經(jīng)趟后記錄序列已經(jīng)有序，后面的有序，后面的3 3趟冒泡趟冒泡“空跑空跑”沒(méi)有發(fā)沒(méi)有發(fā)生交換。因此應(yīng)該對(duì)算法

22、加以改進(jìn)：能生交換。因此應(yīng)該對(duì)算法加以改進(jìn)：能“記住記住”每趟加工時(shí)是否發(fā)生了每趟加工時(shí)是否發(fā)生了“交換交換”，若某一趟未發(fā)生若某一趟未發(fā)生“交換交換”，表示此時(shí)記錄，表示此時(shí)記錄序列已經(jīng)有序，應(yīng)結(jié)束排序過(guò)程。序列已經(jīng)有序，應(yīng)結(jié)束排序過(guò)程。改進(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)過(guò)一趟“起泡”，“i 減一”，但并不是每趟都如此。因此應(yīng)該對(duì)算法進(jìn)但并不是每趟都如此。因此應(yīng)該對(duì)算法進(jìn)一步加以改進(jìn)：一步加以改進(jìn)： “ “記住記住”本趟進(jìn)行過(guò)交換本趟進(jìn)行過(guò)交換的最后一個(gè)記錄的位置，那么，在下一躺的最后一個(gè)記錄的位置，那么，在下一躺起泡時(shí)，就可減少比較次數(shù)。起泡時(shí)，就可減少比較次數(shù)。注意注意: :2. 一般情況下，每經(jīng)過(guò)一趟“起泡”，“i 減一”，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i; j+) if (Rj+1.key 1) / while / BubbleSorti = n;i = lastEx

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

25、列中逆序有序）： 需進(jìn)行需進(jìn)行n-1趟起泡趟起泡“比較比較”的次數(shù)：的次數(shù)：0“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：n-12) 1() 1(2nnini2) 1(3) 1(32nnini起泡排序總的起泡排序總的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為為O(nO(n2 2) ) 目標(biāo)：目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動(dòng)移動(dòng)至該記錄之前至該記錄之前，反之，凡關(guān)鍵字大于樞軸關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后移動(dòng)至該記錄之后。致使一趟排序一趟排序之后，記錄的無(wú)序序列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 可見(jiàn)，經(jīng)過(guò)“一次劃分一次劃分” ，將關(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)整過(guò)程中，設(shè)立了兩個(gè)指針： 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;三、快速排序三、快速排序 首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分一次劃分”，之后分別分別對(duì)分割所得兩個(gè)子序列“遞歸遞歸”進(jìn)行進(jìn)行快速排序快速排序。無(wú) 序 的 記 錄 序 列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸樞軸一次劃分分別進(jìn)行快速排序void QSort (RedType & R, int s, int t ) / 對(duì)記錄序列對(duì)記錄序列Rs.t進(jìn)行快速排序進(jìn)行快速排序 if (s t-1) / 長(zhǎng)度大于長(zhǎng)度大于1 / QSort pivotloc = Partition(R, s, t); / 對(duì)對(duì) Rs.t

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

31、個(gè)記錄進(jìn)行快排所需時(shí)間： 其中 Tpass(n)為對(duì) n 個(gè)記錄進(jìn)行一次劃分所需時(shí)間。 若待排序列中記錄的關(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é)論: 快速排序的時(shí)間復(fù)雜度為快速排序的時(shí)間復(fù)雜度為O(nlogn)由此可得快速排序所需時(shí)間的平均值為： 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判驎r(shí)，快速排

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

33、錄，并和第中選出關(guān)鍵字最小的記錄，并和第i i（1in)1in)個(gè)記錄交換之。個(gè)記錄交換之。 對(duì)對(duì)L.r1.n中記錄進(jìn)行簡(jiǎn)單選擇排中記錄進(jìn)行簡(jiǎn)單選擇排序的算法為：序的算法為：令令i從從1至至n-1,進(jìn)行進(jìn)行n-1趟選趟選擇操作。擇操作。 假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序列R1.i-1無(wú)序序列 Ri.n 第 i 趟簡(jiǎn)單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無(wú)序序列 Ri+1.n簡(jiǎn)單選擇排序簡(jiǎ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）簡(jiǎn)單選擇排序每一趟執(zhí)行后的序列狀態(tài)：簡(jiǎn)單選擇排序每一趟執(zhí)行后的序列狀態(tài)：簡(jiǎn)單選擇排序的算法描述如下：void SelectSort (Elem R, int n ) / 對(duì)記錄序列對(duì)記錄序列R1.n作簡(jiǎn)單選擇排序。作簡(jiǎn)單選擇排序。 for (i=1; in; +i) / 選擇第選擇第 i 小的記錄，并交換到位小的記錄，并交換到位 / SelectSortj = SelectMinKey(R, i);

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

36、首先對(duì)首先對(duì)n n個(gè)記錄的關(guān)鍵字進(jìn)行兩兩個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，然后在其中比較，然后在其中n/2n/2個(gè)較小者之間再個(gè)較小者之間再進(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。 樹(shù)形選擇排序的時(shí)間復(fù)雜度分析：樹(shù)形選擇排序的時(shí)間復(fù)雜度分析： 由于含由于含n個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)的深度個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)的深度為為 log2n +1次，則在樹(shù)形選擇排序中，除了最次，則在樹(shù)形選擇排序中，除了最小關(guān)鍵字之外，每選擇一個(gè)次小關(guān)鍵字僅需進(jìn)小關(guān)鍵字之外，每選擇一個(gè)次小關(guān)鍵字僅需進(jìn)行行 log2

38、n 次比較，因此，次比較，因此，樹(shù)形選擇排序的樹(shù)形選擇排序的時(shí)間時(shí)間復(fù)雜度復(fù)雜度為為O(nlog2n)。 這種排序方法尚有輔助存儲(chǔ)空間較多，和這種排序方法尚有輔助存儲(chǔ)空間較多，和“最大值最大值”進(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ù)列視作完全二叉樹(shù)，則 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。1236276549817355403498例如例如:是堆是堆14不不 堆排序即是利用堆排序即是利用堆的特性堆的特性對(duì)記錄序?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)過(guò)篩選 如何由一個(gè)無(wú)序序列如何由一個(gè)無(wú)序序列“建堆建堆”？實(shí)現(xiàn)堆排序需要解決兩個(gè)問(wèn)題實(shí)現(xiàn)堆排序需要解決兩個(gè)問(wèn)題: 如何在輸出堆頂元素之后，調(diào)如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？整剩余元素成為一個(gè)新的堆？定義堆類型為定義堆類型為:typedef SqList HeapType; / 堆采用順序表表示之堆采用順序表表示之如何在輸出堆頂元素之后，調(diào)整如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？剩

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

42、要對(duì)它進(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 也成為一個(gè)大頂堆也成為一個(gè)大頂堆 / HeapAdjustrc = Rs; / 暫存暫存 Rs for ( j=2*s; j= Rj.key ) break; / 再作再作“根根”和和“子樹(shù)根子樹(shù)根”之間的比之間的比較，較， / 若若“=”成立，則說(shuō)明已找到成

43、立，則說(shuō)明已找到 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; / 左左/右右“子樹(shù)根子樹(shù)根”之間先進(jìn)行相互比較之間先進(jìn)行相互比較 / 令令 j 指示關(guān)鍵字較大記錄的位置指示關(guān)鍵字較大記錄的位置10.5 歸歸 并并 排排 序序 歸并排序的過(guò)程基于下列基本基本思想思想進(jìn)行： 將兩個(gè)或兩個(gè)以上的有序子序列 “歸并” 為一個(gè)有序序列。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰位置相鄰的記錄有序子

44、序列歸并為一個(gè)一個(gè)記錄的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n這個(gè)操作對(duì)順序表而言，是輕而易舉的。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歸并排序的算法歸并排序的算法 如果記錄無(wú)序序列 Rs.t 的兩部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。 由此，應(yīng)該先分別對(duì)這兩部分進(jìn)行 2-路歸并排序。2-2-路歸并排序的過(guò)程路歸并排序的過(guò)程初始狀態(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) / 對(duì)順序表對(duì)順序表 L 作作2-路歸并排序路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort 容

48、易看出，對(duì) n 個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為(nlogn)。即： 每一趟歸并的時(shí)間復(fù)雜度為 O(n)， 總共需進(jìn)行 log2n 趟。 基數(shù)排序基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來(lái)實(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 個(gè)記錄的序列個(gè)記錄的序列 R1, R2, ，Rn對(duì)關(guān)鍵字對(duì)關(guān)鍵字 (Ki0, Ki1,Kid-1) ) 有序有序是指： 其中其中: : K0 被稱為被稱為 “最主最主”位關(guān)鍵字位關(guān)鍵字Kd-1 被稱為被稱為 “最次最次”位關(guān)鍵字位關(guān)鍵字 對(duì)于序列中任

49、意兩個(gè)記錄 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法 先對(duì)先對(duì)K0進(jìn)行排序進(jìn)行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對(duì) K1 進(jìn)行排序，.， 依次類推，直至最后直至最后對(duì)最次位關(guān)鍵字排序完成為止對(duì)最次位關(guān)鍵字排序完成為止。最高位優(yōu)先最高位優(yōu)先MSD法 先對(duì) Kd-1 進(jìn)行排序，然后對(duì) Kd-2 進(jìn)行排序，依次類推，直至對(duì)最主位直至

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

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

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

53、指針相鏈，構(gòu)成一個(gè)鏈表； “分配分配” ” 時(shí)，按當(dāng)前時(shí)，按當(dāng)前“關(guān)鍵字位關(guān)鍵字位”所取值，所取值，將記錄分配到不同的將記錄分配到不同的 “ “鏈隊(duì)列鏈隊(duì)列” ” 中，每個(gè)隊(duì)列中記中，每個(gè)隊(duì)列中記錄的錄的 “ “關(guān)鍵字位關(guān)鍵字位” ” 相同；相同； “收集收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表將各隊(duì)列首尾相鏈成一個(gè)鏈表; ; 對(duì)每個(gè)關(guān)鍵字位均重復(fù)對(duì)每個(gè)關(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