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

1、第8章 排序24 七月 2022本章概述 排序是計算機程序設(shè)計中的一種重要操作，它是對數(shù)據(jù)元素序列建立某種有序排列的過程。有序的表或文件便于查找，如有序的順序表可以采用效率較高的折半查找法，而無序的順序表則只能采用效率較低的順序查找法，又如建造樹表本身也是一個排序的過程。所以，對各種排序方法的學(xué)習(xí)和研究，尤其是高效地排序，是計算機應(yīng)用的一個重要課題。24 七月 20228.1 基本概念 排序(sorting)是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。 1.排序的定義 假設(shè)含n個記錄的序列為：R1,R2,Rn(8-1)其相應(yīng)

2、的關(guān)鍵字序列為： K1,K2,Kn24 七月 2022 需確定1,2,n的一種排列p1,p2,pn,使其相應(yīng)的關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系Kp1 Kp2 Kpn 即使（8-1）的序列成為一個按關(guān)鍵字有序的排列Rp1,Rp2 ,Rpn 這樣的一種操作稱為排序。24 七月 20222.穩(wěn)定排序法與非穩(wěn)定排序法關(guān)鍵字：一個記錄中可以標識該數(shù)據(jù)項的值。關(guān)鍵字分主關(guān)鍵字和次關(guān)鍵字兩種。主關(guān)鍵字：數(shù)據(jù)元素值不同時該關(guān)鍵字的值也一定不同。主關(guān)鍵字是能夠唯一區(qū)分各個不同數(shù)據(jù)元素的關(guān)鍵字。不滿足主關(guān)鍵字定義的關(guān)鍵字稱為次關(guān)鍵字。24 七月 2022 3.內(nèi)部排序與外部排序 根據(jù)排序過程中涉及的存儲器不

3、同，可將排序方法分為兩大類：(1) 內(nèi)部排序：指待排序記錄存放在計算機隨機存儲器中進行排序的過程。(2)外部排序：指待排序記錄的數(shù)量很大，以致于內(nèi)存一次不能容納全部記錄，在排序的過程中尚需對外存進行訪問的排序過程。24 七月 2022 按排序依據(jù)的原則不同，可將內(nèi)部排序大致可分為：插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序五類。 按內(nèi)部排序過程中所需的工作量來區(qū)分，可分為以下3類：(1) 簡單的排序方法，其時間復(fù)雜度為O(n2)。(2)先進的排序方法,其時間復(fù)雜度為O(nlogn)。(3)基數(shù)排序方法，其時間復(fù)雜度為O(dn)。24 七月 2022 外部排序的方法主要是多路平衡歸并的實現(xiàn)

4、。在排序過程中需要進行如下兩種基本操作：(1) 比較兩個關(guān)鍵字的大小。(2) 將記錄從一個位置移動到另一個位置。24 七月 2022 4.待排序記錄的存儲方式 待排序記錄可有以下3種存儲方式：(1) 待排序的一組記錄存放在地址連續(xù)的一組存儲單元上。記錄之間的次序關(guān)系由其存儲位置決定，實現(xiàn)排序必須移動記錄。(2) 一組待排序記錄存放在靜態(tài)鏈表中，記錄之間的次序關(guān)系由指針指示，則實現(xiàn)排序不需要移動記錄，僅需修改指針即可。這種存儲方式下實現(xiàn)的排序又稱鏈表排序。24 七月 2022(3) 待排序記錄本身存儲在一組地址連續(xù)的存儲單元內(nèi)，同時另設(shè)一個指示各個記錄存儲位置的地址向量，在排序過程中不移動記錄本

5、身，而移動地址向量中的這些記錄的“地址”，在排序結(jié)束后再按照地址向量中的值調(diào)整記錄的存儲位置。這種存儲方式下實現(xiàn)的排序又稱地址排序。24 七月 2022 本章連續(xù)的存儲待排序記錄，設(shè)關(guān)鍵字為整型。定義如下：#define MAXSIZE 20/ 存儲空間的最大值typedef int KeyType;/ 定義關(guān)鍵字類型為整型typedef structKeyType key;/ 關(guān)鍵字域InfoType otherinfo;/ 其他數(shù)據(jù)項 RedType;/ 記錄類型 typedef struct RedType rMAXSIZE+1;/ r0閑置或用作監(jiān)視哨單元int length ;/ 順

6、序表長度 SqList;/ 順序表類型24 七月 20228.2 插入排序 插入排序的基本思想： 從初始有序的子集合開始，不斷地把新的數(shù)據(jù)元素插入到已排列有序的子集合的合適位置上，使子集合中數(shù)據(jù)元素的個數(shù)不斷增多，當(dāng)子集合等于集合時，插入排序算法結(jié)束。常用的插入排序方法有直接插入排序、折半插入排序、表插入排序和希爾排序。 本節(jié)介紹直接插入排序和希爾排序兩種插入排序方法。24 七月 2022 直接插入排序（straight insertion sort）的基本思想： 每次只考慮一個待排序的元素，用這個元素同已經(jīng)排序好的其他元素逐一進行比較，在找到適當(dāng)?shù)奈恢煤?，將此元素插入，從而得到一個新的有序表

7、，然后再選擇下一個待排序的元素。8.2.1 直接插入排序24 七月 2022 【例8-1】 已知一組待排序的記錄的初始序列為36, 45, 60, 92, 78, 12, 25, 45，用直接插入排序法對其進行排序。 算法思想：前4個記錄已按關(guān)鍵字遞增的排序，構(gòu)成含有4個記錄的有序序列36,45,60,92。現(xiàn)將關(guān)鍵字為78的第5個記錄插入其中，形成新的有序序列，首先在有序序列中進行查找比較。24 七月 2022 確定插入位置。假設(shè)從右向左依次比較，由于6078n，則排序完成，否則轉(zhuǎn)到(4)。24 七月 2022 執(zhí)行具體過程如算法8.1所示。void InsertSort(SqList &L

8、) / 對順序表L進行直接插入排序for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)/需將L.ri插入有序表L.r0=L.ri;/ 制為哨兵for(j=i-1;L.r0.keyL.rj.key;-j)L.rj+1 = L.rj;/記錄后移L.rj+1 = L.r0;/插入到正確位置/InserSort算法8.124 七月 2022 【例8-1】中直接插入排序的過程如下圖所示，圖中用箭頭指明相應(yīng)的數(shù)據(jù)元素在排序過程中的位置變化，同時為了檢測穩(wěn)定性，在后一個“45”上加上了“”符號。24 七月 2022 算法分析： 直接插入排序算法的時間復(fù)雜度分析可分最好、最

9、壞和平均三種情況來考慮。 (1)最好的情況：原始數(shù)據(jù)元素集合已全部排好序。這時算法中內(nèi)層for循環(huán)的循環(huán)次數(shù)每次均為0。這樣，外層for循環(huán)中每次數(shù)據(jù)元素的比較次數(shù)均為1。因此，整個排序過程中的比較次數(shù)為n-1，沒有賦值操作。所以直接插入排序算法最好情況下的時間復(fù)雜度為O(n)。24 七月 2022 (2)最壞的情況：原始數(shù)據(jù)元素集合為反序排列。時間復(fù)雜度為O(n2)。在反序情況下，由于第i個記錄找到相應(yīng)插入位置需要比較i次，所以從第2到第n個記錄共需比較的總次數(shù)為：每次首先要將ri移到r0，故每趟移動比比較多一次，則記錄移動的總次數(shù)為：24 七月 2022 因此，直接插入排序算法最壞情況下的

10、時間復(fù)雜度為O(n2)。 (3)平均情況：平均情況下，參加排序的原始記錄關(guān)鍵字是隨機排列的，則數(shù)據(jù)元素的期望比較次數(shù)和期望移動次數(shù)約為n2/4。因此，直接插入排序算法的期望時間復(fù)雜度為O(n2)。24 七月 2022 可見，原始數(shù)據(jù)元素集合越接近有序，直接插入排序算法的時間效率越高，其時間效率位O(n)O(n2)。直接插入排序所需的輔助空間是一個監(jiān)視哨，其作用是暫時存放待插入的元素，故空間復(fù)雜度為O(1)。 顯然，直接插入排序算法是一種簡單的、穩(wěn)定的、易實現(xiàn)的排序算法，但當(dāng)記錄數(shù)n很大時，不適合進行直接插入排序。24 七月 2022 希爾排序（Shells sort）又稱“縮小增量排序”（di

11、minishing increment sort），1959年由希爾（D.L.Shell）提出的一種排序方法，它在時間效率上比其他的插入排序方法有了較大的提高。 它的基本思想是：把待排序的記錄分成若干個小組，然后對同一組內(nèi)的記錄進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。8.2.2 希爾排序24 七月 2022 希爾排序的過程如下：以d1(0d1d2）為增量，重復(fù)上述步驟，直到di=1,把所有n個元素放在一個組內(nèi)，進行直接插入排序為止。該次排序結(jié)束時，這個序列的排序工作完成。24 七月 2022 希爾排序?qū)嶋H上是對直接插入排序的一種改進。待排序的原始序

12、列越接近有序或者記錄個數(shù)越少，則直接插入排序算法的時間效率就越高。 在希爾排序中，開始增量比較大，分組較多，每個組內(nèi)記錄個數(shù)較少，因而記錄的比較次數(shù)和移動次數(shù)都比較少，在小組內(nèi)用直接插入排序的時間效率很高。盡管增量逐漸變小，分組越來越少，每個組內(nèi)記錄個數(shù)逐漸增多，但同時記錄越來越接近有序，因而記錄的比較次數(shù)和移動次數(shù)越來越少，從而使直接插入排序的時間效率越來越高。24 七月 2022 在希爾排序中，增量序列的選取到目前為止尚未得到一個最佳值，但最后一次排序時的增量必為1。一般選取增量序列的規(guī)則是：取di+1為 ，最簡單的方法是取di+1= 【例8-2】 已知一組待排序的記錄的初始序列為36,4

13、5, 60, 92, 78, 12, 25, 45,18,2,用希爾排序法對其進行排序，并給出排序的過程。24 七月 2022解：希爾排序的過程如下圖所示。在圖中，同一連線上的關(guān)鍵字表明它們所屬的記錄是放在同一組中的，選取增量序列為：d1=5，d2=3，d3=1，同時用“”標記后一個45來檢測排序的穩(wěn)定性。24 七月 2022 希爾排序算法的具體實現(xiàn)如算法8.2所示。void ShellInsert(SqList &L,int d,int t)/對順序表L作希爾排序for(k=0;kt;+k) /參數(shù)t為希爾排序趟數(shù)for (i=dk+1;i=L.length;+i)/一趟增量為dk的插入排序

14、 if(L.ri.key0)&(L.r0.keyL.r2.key,則將兩個記錄交換。然后比較第2個和第3個記錄的關(guān)鍵字；以此類推，直到第n-1個記錄和第n個記錄的關(guān)鍵字進行比較交換，這個過程稱為一趟冒泡。(2)然后進行第二趟冒泡排序，即對2n個記錄進行同樣操作，則關(guān)鍵字次大的記錄被安置在第n-1條記錄的位置上。(3)重復(fù)對前n-i（i1）條記錄進行相同的操作，每次操作都將關(guān)鍵字次大的記錄安置到第n-i條記錄的位置上，直至沒有記錄需要交換為止。24 七月 2022 一般地，冒泡排序的第i趟排序只需要從L.r1到L.rn-i+1條記錄依次比較相鄰的兩個記錄的關(guān)鍵字，并在出現(xiàn)前一條記錄的關(guān)鍵字大于后

15、一條記錄的關(guān)鍵字的時候進行交換，其結(jié)果就是將這n-i+1條記錄中關(guān)鍵字最大的記錄移到第n-i+1條記錄的位置上。整個冒泡排序的過程最多需要進行k(1kn)趟。24 七月 2022 【例8-3】 已知一組待排序的記錄的初始序列為78, 45, 60, 36, 25, 45,12, 92，用冒泡排序法對其進行排序。解：冒泡排序的過程如下圖所示。其中后一個45用“”標記，來檢查排序的穩(wěn)定性。24 七月 2022在冒泡排序過程中，關(guān)鍵字較小的記錄好比水中的氣泡逐趟向上浮，關(guān)鍵字較大的記錄好比石塊往下沉，每一趟中都有一塊大“石塊”沉到水底，圖中用加粗字體標記。 若在排序過程中，當(dāng)前的排序序列已經(jīng)有序，就

16、無須再繼續(xù)比較，可提前結(jié)束排序過程，為此在實際的冒泡算法中引入一個整型量flag，在每一次排序之前，先將它置為0，若在一次排序中交換了記錄，則將它置為1。當(dāng)一次排序結(jié)束時，再檢查flag，若flag仍為0，則未曾交換過記錄，此時可以提前終止算法。24 七月 2022 冒泡排序算法的具體實現(xiàn)如算法8.3所示。 算法分析： 冒泡排序是一種穩(wěn)定的排序方法，算法的執(zhí)行時間與原始記錄的有序程度有很大關(guān)系，如果原始記錄已經(jīng)是正序序列，比較次數(shù)為n-1次，交換次數(shù)為0；如果原始記錄是反序排列，則總的比較次數(shù)為n(n-1)/2次，交換次數(shù)為3n(n-1)/2。所以算法的平均時間復(fù)雜度為O(n2)，空間復(fù)雜度為

17、O(1)。24 七月 2022 快速排序（quick sort）是對冒泡排序的一種改進。它的基本思想：通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，直至整個序列有序。8.3.2 快速排序24 七月 2022 1快速排序過程 快速排序在待排序的n個記錄中任取一個記錄（如取第一個記錄），以該記錄的鍵值為標準，將所有記錄分為兩組（一般都是無序的），使得第一組中各記錄的鍵值均小于或等于該鍵值，第二組中各記錄的鍵值均大于該鍵值，然后把該記錄排在這兩組的中間（這也是該記錄最終的位置），稱為一趟快速排序（或一次劃分）。對所分

18、成的兩組再分別重復(fù)上述方法，直到所有記錄都排在適當(dāng)位置為止。24 七月 2022 快速排序的思想：(1)先將待排序序列的第一個記錄L.r1復(fù)制到L.r0。(2)確定支點i的位置：將所有關(guān)鍵字比L.ri.key小的記錄安置到i位置之前，將所有關(guān)鍵字比L.ri.key大的記錄安置到i位置之后。最后以i位置作為分界線，將序列L.r1,L.rn分割成兩個子序列L.r1,L.r2,L.ri-1和L.ri+1,L.ri+2,L.rn。前一個子序列中的記錄的關(guān)鍵字都比L.ri.key小，后一個序列中的記錄關(guān)鍵字都比L.ri.key大。(3)將L.r0復(fù)制到L.ri中。(4)對被分割的兩個序列重復(fù)進行(1)和

19、(2)步驟，直到每個序列的記錄數(shù)都為1，達到整個序列有序。24 七月 2022 【例8-4】 已知一組待排序的記錄的初始序列為45, 45, 60, 36, 25, 78,12, 92，用快速排序法對其進行排序。 解：取初始序列的第一個記錄為排序支點，其關(guān)鍵字記為pivotkey，將其復(fù)制到L.r0中。設(shè)i和j用于存儲序列向后和向前搜索的位置。從j位置開始向序列的前部搜索，如果L.rj.keypivotkey，則用L.ri 和關(guān)鍵字為pivotkey的記錄進行交換，直到i和j相等完成一趟排序。在形成的子序列中，分別以子序列的第一個記錄為排序支點，重復(fù)上述步驟，直到兩個子序列中的記錄數(shù)為1，達到

20、整個序列有序。排序過程如下圖所示。24 七月 2022 2快速排序的一趟排序算法 快速排序是通過遞歸的方法實現(xiàn)的，在一趟快速排序算法中，附設(shè)兩個整型變量low和high，其初值分別為第一趟排序序列的上下限，設(shè)支點記錄的關(guān)鍵字為pivotkey，則首先從high位置起向前搜索找到第一個關(guān)鍵字小于pivotkey的記錄和支點記錄進行交換，然后從low位置起向后搜索，找到第一個關(guān)鍵字大于pivotkey的記錄和支點記錄進行交換，重復(fù)上述兩個步驟直到low=high為止。 快速排序的一趟排序具體實現(xiàn)如算法8.4所示。24 七月 2022 3.快速排序的遞歸算法 快速排序算法需要對兩個子序列分別使用快速

21、排序。 遞歸形式的快速排序算法如算法8.5和算法8.6所示。24 七月 2022void QSort(SqList &L,int low,int high)對順序表的子序列L.rlow.high進行快速排序int pivotloc;if(lowhigh)子序列的長度應(yīng)該大于1 pivotloc=Partition(L,low,high);將序列L.rlow.high分成兩個子序列，返回支點位置 QSort(L,low,pivotloc-1);對低端子序列進行遞歸的快速排序 QSort(L,pivotloc+1,high);對高端子序列進行遞歸的快速排序 QSort算法8.524 七月 2022

22、void QuickSort(SqList &L)對順序表L作快速排序QSort(L,1,L.length);QuickSort算法8.6 算法分析：快速排序并沒有每次比較都進行交換，只是移動一個數(shù)據(jù)，待所選出的元素找到合適的位置才存入，因此排序速度快。24 七月 2022 快速排序的執(zhí)行時間和排序支點的選取有關(guān)，若支點的關(guān)鍵字能把當(dāng)前記錄從中間分成兩個相等的子區(qū)間，則運行效率最高；若記錄有序，且支點的關(guān)鍵字在記錄的首或尾時，即只有一個子區(qū)間，該算法就退化成冒泡排序法，此種情況為最壞的情況，其算法的時間復(fù)雜度為O(n2)。 快速排序的平均時間復(fù)雜度為O(nlog2n)，它是一種不穩(wěn)定的排序方法

23、。24 七月 20228.4 選擇排序 選擇排序（selection sort）就是每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。選擇排序中最簡單的就是簡單選擇排序（simple selection sort）。24 七月 2022 算法思想：對于表L中的n條記錄進行簡單選擇排序，對于第i趟選擇就是從n-i+1（i=1,2,n-1）個記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個記錄。 【例8-5】 已知一組待排序的記錄的初始序列為45, 45, 60, 36, 25, 78,12, 92，用簡單選擇排序法對其排序。8.4

24、.1 簡單選擇排序24 七月 2022 解：第一趟，從待排序的序列中，選擇關(guān)鍵字最小的一個記錄與第一個記錄進行交換。第二趟，從其余的序列中選擇關(guān)鍵字次小的記錄與第二個記錄進行交換，以此類推，直到所有記錄排序完成。排序過程如下圖所示。24 七月 2022 簡單選擇排序的算法實現(xiàn)如算法8.7所示。void SelectSort(SqList &L)/對順序表L進行簡單選擇排序for(i=0;iL.length-1;i+) /選擇第i+1小的記錄，并和第i+1位置的記錄交換k=i;for(j=i+1;jL.rj.key)k=j; if(k!=i) /將第i+1個記錄與第k+1個記錄交換 t=L.ri

25、;L.ri=L.rk;L.rk=t;/SelectSort算法8.724 七月 2022 算法分析： 在簡單選擇排序中，記錄的比較次數(shù)與記錄關(guān)鍵字的初始狀態(tài)無關(guān)，無論關(guān)鍵字的初始狀態(tài)如何，每趟選擇排序都要進行n-i次比較，才能找出關(guān)鍵字最小的記錄。但記錄的移動次數(shù)與記錄關(guān)鍵字的初始狀態(tài)有關(guān)。在最好情況下，其初始記錄關(guān)鍵字為正序，每趟排序不用交換記錄，記錄移動次數(shù)為0次；平均情況下，記錄移動的次數(shù)會比較高。所以簡單選擇排序在最好情況和平均情況下，總的時間復(fù)雜度均為O(n2)，這是由它的比較次數(shù)決定的。簡單選擇排序只需要一個臨時單元交換記錄，因此，簡單選擇排序的空間復(fù)雜度為O(1)。24 七月 2

26、0228.4 選擇排序 在簡單選擇排序中，待排序的序列構(gòu)成一個線性表結(jié)構(gòu)，要從有n個數(shù)據(jù)元素的線性表中選擇出一個最小的數(shù)據(jù)元素需要比較n-1次。堆排序（heap sort）是對選擇排序的一種改進方法，屬于樹型排序法。在排序過程中，將R1.n看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用雙親結(jié)點和孩子結(jié)點間的內(nèi)在關(guān)系來選擇關(guān)鍵字最小的記錄。8.4.2 堆排序24 七月 2022 1.堆的概念 設(shè)有n個元素的序列K1, K2, , Kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。 （其中，i=1,2, ）24 七月 2022 堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不大于（或不小于）其左、右孩子的值。

27、 若序列K1, K2, , Kn是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值），分別稱為小根堆和大根堆。 例如，下列兩個序列為堆，對應(yīng)的完全二叉樹如下圖所示。24 七月 2022 序列92,78,60,36,45,25,45,12看成的完全二叉樹為一個大根堆，如圖 (a)所示。 序列12,25,45,45,36,78,60,92看成的完全二叉樹為一個小根堆，如圖 (b)所示。 根據(jù)堆的定義可以得知堆有如下兩個性質(zhì)： (1)大根堆的根結(jié)點是堆中值最大的數(shù)據(jù)元素，小根堆的根結(jié)點是堆中值最小的數(shù)據(jù)元素，稱堆的根結(jié)點元素為堆頂元素。24 七月 2022 (2) 對于大根堆，

28、從根結(jié)點到每個葉子結(jié)點的路徑上，數(shù)據(jù)元素組成的序列都是遞減有序的；對于小根堆，從根結(jié)點到每個葉子結(jié)點的路徑上，數(shù)據(jù)元素組成的序列都是遞增有序的。 2堆排序的方法 堆排序的算法思想： (1)以初始關(guān)鍵字序列建立堆。 (2)輸出堆頂最小元素。24 七月 2022(3) 調(diào)整余下的元素，使其成為一個新堆。(4) 重復(fù)(2),(3)步驟n 次，得到一個有序序列。 實現(xiàn)堆排序關(guān)鍵要解決兩個問題： （1）如何由一個無序序列建成一個堆。 將一個無序序列建成堆，可以反復(fù)進行“篩選”。將序列看成完全二叉樹，則最后一個非終端結(jié)點是第 個元素，“篩選”只需從第 個元素開始。24 七月 2022例如，下圖(a)中的完

29、全二叉樹表示一個8個元素的無序序列：45, 45, 60, 36, 25, 78,12, 92在圖(a)所示的例子中，篩選從第4個元素(第 個元素)開始，由于9236，故不需要交換，第3個元素6012，因此需要交換，交換后的狀態(tài)如圖(b)所示，同理第2個元素45被篩選之后序列如圖(c)所示。24 七月 2022此后，由于3625，需要交換，交換后的狀態(tài)如圖(d)所示。接下來篩選第1個元素，篩選后狀態(tài)如圖(e)所示。形成初始堆。 (2) 輸出堆頂元素后，如何調(diào)整余下的元素成為一個新堆。 輸出堆頂元素，并將剩下的元素調(diào)整成一個新堆的過程稱為“篩選”。24 七月 2022 下圖 (a)是一個初始堆，

30、將堆頂元素和堆中最后一個元素交換位置，然后輸出堆頂元素，如圖(b)所示。其余元素組成的完全二叉樹中，根結(jié)點的左、右子樹均為堆，只有根結(jié)點可能不符合堆的要求。首先根與左、右子樹的根結(jié)點的值進行比較，在圖 (b)中，由于左子樹的根結(jié)點的值小于右子樹的根結(jié)點的值且小于根結(jié)點的值，則將25與92進行交換，由于92被替換后破壞了24 七月 2022 左子樹的“堆”，則需要進行和上述相同的調(diào)整，直至葉子結(jié)點，調(diào)整后的狀態(tài)如圖 (c)所示，此時堆頂為n-1個元素的最小值，交換36和45的位置，調(diào)整后狀態(tài)如圖(d)所示。重復(fù)上述過程，將25和堆中的最后一個元素60交換輸出且進行調(diào)整，得到如圖(e)所示的新堆。

31、24 七月 2022 3堆排序的算法 在堆排序算法中，首先將待排序序列按照關(guān)鍵字建立一個大根堆，然后對序列中前n-1個記錄進行篩選，重新將其調(diào)整成為一個新的大根堆，如此重復(fù)下去直至排序結(jié)束。 堆排序的具體實現(xiàn)如算法8.8和算法8.9所示。24 七月 2022typedefSqListHeapType; 使用SqList類型的順序表存儲void HeapAdjust(HeapType &H,int s,int m)進行一次篩選操作，已知H.rs.m中的記錄關(guān)鍵字除H.rs.key外均滿足堆的定義，調(diào)整后H.rs.m滿足大根堆的要求int j;rc=H.rs;for(j=2*s;j=m;j*=2)

32、沿關(guān)鍵字較大的孩子結(jié)點向下篩選if(jm & (H.rj.key=H.rj.key)break; H.rs=H.rj;s=j;H.rs=rc;HeapAdjust算法8.824 七月 2022void HeapSort(HeapType &H)/對表H進行堆排序 for(i=H.length/2;i0;-i)/把H.r1.H.length建成大根堆 HeapAdjust(H,i,H.length); for(i=H.length;i1 ;i-)/調(diào)用篩選操作，將堆頂記錄和當(dāng)前未經(jīng)排序的序列H.r1.i中/的最后一個記錄交換后，將剩下的i-1個記錄調(diào)整成大根堆 rc=H.r1;H.r1=H.ri

33、;H.ri=rc; HeapAdjust(H,1,i-1);/將剩下的i-1個記錄調(diào)整成大根堆/HeapSort算法8.924 七月 2022 算法分析： 堆排序的時間主要由建立初始堆的時間和不斷調(diào)整重建新堆的時間這兩部分構(gòu)成。堆排序平均和最壞的時間復(fù)雜度均為O(nlog2n)，相對于快速排序來說，這是堆排序的最大優(yōu)點。堆排序只需一個輔助單元，其算法的空間復(fù)雜度為O(1)。堆排序是一種不穩(wěn)定的排序方法，這是因為在堆排序過程中，需要進行不相鄰記錄之間的交換和移動。堆排序是對簡單選擇排序的一種改進，它適合待排序的記錄數(shù)n比較大的情況。24 七月 20228.5 歸并排序 歸并排序（merging

34、sort）是逐步將多個有序子表經(jīng)過若干次歸并操作，最終合并成一個有序表的過程。所謂歸并（merge），就是將兩個或多個有序表合成一個有序表的過程。歸并的方式有多種，將兩個有序表合并成一個有序表則稱為二路歸并，同理，有三路歸并、四路歸并等。二路歸并排序是最常用的排序方法，它既適合內(nèi)排序，也適合外排序（更適合外排序）。本節(jié)將介紹二路歸并排序。24 七月 2022 二路歸并排序的基本思想：(1)將有n個原始記錄的無序表看成是由n個長度為1的有序子表組成的。(2)將相鄰的兩個有序子表進行歸并，也就是將第一個表和第二個表合并，第三個表和第四個表合并，以此類推，若最后只剩下一個表，則直接進入下一趟歸并，這

35、樣就得到 個長度為2或1的有序表，稱此為一趟歸并。(3) 重復(fù)執(zhí)行步驟(2)，直到歸并第 趟以后得到一個長度為n的有序表為止。24 七月 2022 【例8-6】 已知一組待排序的記錄的初始序列為36,45, 60, 92, 78, 12, 25, 45,18,2，用二路歸并排序方法對其進行排序。 解：二路歸并排序的過程如下圖所示，用標記后一個45來檢測排序的穩(wěn)定性。24 七月 2022 進行第一趟歸并時，共有10個有序子表，兩兩歸并后，共有5個有序子表； 經(jīng)過第二趟歸并之后，共有3個有序子表，其中前兩個有序子表長度為4，最后一個子表長度為2； 繼續(xù)執(zhí)行二路歸并，經(jīng)過第四趟歸并后，就得到一個長度

36、為10的有序表。24 七月 2022 從二路歸并排序的執(zhí)行過程可以看出，歸并排序包含以下兩種基本操作： (1)一次歸并：將兩個位置相鄰長度為L的有序子表合并成一個長度為2L的有序子表。 (2)一趟歸并：依次將m個長度為L的相鄰有序子表從左向右兩兩進行歸并，得到個數(shù)為 且長度為2L的相鄰有序子表。 二路歸并排序其具體實現(xiàn)如算法8.10所示。24 七月 2022void Merge（RcdType SR,RcdType &TR,int i,int m,int n）將有序的SRi.m和SRm+1.n歸并為有序的TRi.nfor(j=m+1,k=i;i=m & j=n;+k) 將SR中記錄由小到大地并

37、入TR if(SRi.key=SRj.key) TRk=SRi+; else TRk=SRj+;if(i=m)TRk.n=SRi.m; 將剩余的SRi.m復(fù)制到TRif(j=n)TRk.n=SRj.m; 將剩余的SRj.m復(fù)制到TRMerge算法8.1024 七月 2022 遞歸形式的二路歸并算法見算法8.11和算法8.12。void MSort（RcdType SR,RcdType &TR,int s,int t）將SRs.t歸并排序為TR1s.tif（s=t)TRs=SRs;elsem=(s+t)/2;將SRs.t平均分為SRs.m和SRm+1.tMSort(SR,TR2,s,m);遞歸地

38、將SRs.m歸并為有序的TR2s.mMSort(SR,TR2,m+1,t);遞歸地將SRm+1.t歸并為有序的TR2m+1.tMSort(TR2,TR1,s,m,t);將TR2s.m和TR2m+1.t歸并到TR1s.tMSort算法8.1124 七月 2022void MergeSort（SqList &L）對順序表L作歸并排序MSort(L.r,L.r,1,length);MergeSort算法8.12 算法分析： 二路歸并排序的時間復(fù)雜度等于歸并的趟數(shù)與每一趟時間復(fù)雜度的乘積。24 七月 2022 每趟歸并的時間復(fù)雜度為O(n)。所以，二路歸并排序總的時間復(fù)雜度為O(nlog2n)。二路歸

39、并排序的空間復(fù)雜度為O(n)，在常用的排序方法中，歸并排序是空間復(fù)雜度最差的一種排序方法。歸并排序是一種穩(wěn)定的排序方法，相對于時間復(fù)雜度均為O(nlog2n)的堆排序和快速排序來說，這是二路歸并排序方法的最大特點。24 七月 20228.6 基數(shù)排序 基數(shù)排序(radix sort)是一種借助多關(guān)鍵字排序思想對單邏輯關(guān)鍵字進行排序的方法。它不同于前面所述的各類排序方法，并不需要進行記錄關(guān)鍵字間的比較，它的排序過程是通過分配和收集來完成的，基數(shù)排序又稱為桶排序（bucket sort）或箱排序（bin sort）。24 七月 2022一般情況下，假設(shè)有n個記錄的序列：R1,R2,Rn且每個記錄R

40、i中含有d個關(guān)鍵字（ ）,則稱該序列對關(guān)鍵字（ ）有序是指：對于任意兩個記錄Ri和Rj（1ijn）都滿足下列有序關(guān)系：（ ）（ ）其中，K0稱為最高優(yōu)先位關(guān)鍵字，Kd-1稱為最低優(yōu)先位關(guān)鍵字。8.6.1 多關(guān)鍵字排序24 七月 2022 實現(xiàn)多關(guān)鍵字排序，通常有兩種方法：(1)最高位優(yōu)先（most signigicant digit first）法，簡稱MSD法：先對最高優(yōu)先位關(guān)鍵字K0進行排序，然后分別就每個子序列對關(guān)鍵字K1進行排序， 以此類推，最后將所有子序列依次連接在一起成為一個有序序列。(2)最低位優(yōu)先（least significantdigit first）法，簡稱LSD法：從最

41、低優(yōu)先位關(guān)鍵字Kd-1起進行排序，然后再對高一位的關(guān)鍵字Kd-2進行排序，依次重復(fù)，直至對K0進行排序后便成為一個有序序列。24 七月 2022 MSD和LSD兩種方法的不同特點如下： 若按MSD進行排序，必須將序列逐層分割成若干子序列，然后對各子序列分別進行排序； 而按LSD進行排序時，不用分成子序列，對每個關(guān)鍵字都是整個序列參加排序，但對Ki（0id-2）進行排序時，只能用穩(wěn)定的排序方法。 另一方面，按LSD進行排序時，在一定條件下，也可以不利用前面介紹過的方法來實現(xiàn)排序，而是通過若干次“分配”和“收集”來實現(xiàn)排序。 24 七月 2022 在某些排序的應(yīng)用中，關(guān)鍵字可以看成由若干個關(guān)鍵字復(fù)

42、合而成。例如，若關(guān)鍵字K是數(shù)值，且都在0K999范圍內(nèi)，可以把每一個位上的數(shù)字看成一個關(guān)鍵字，從而K可以分解成K0，K1，K2，其中，K0是百位數(shù)，K1是十位數(shù)，K2是個位數(shù)，并且Ki（i=0,1,2）在相同的取值范圍內(nèi)，因此按低位優(yōu)先排序非常方便，即只要從低位關(guān)鍵字起，按關(guān)鍵字的不同將序列中的記錄放置到rd個隊列中，再按照順序收集起來。如此重復(fù)d次（d為分解成的子關(guān)鍵字的個數(shù)）即可完成排序。 8.6.2 鏈式基數(shù)排序24 七月 2022 鏈式基數(shù)排序算法思想：（1）以靜態(tài)鏈表存儲n個待排記錄。（2）按最低位關(guān)鍵字進行分配，把n個記錄分配到rd個鏈隊列中，每個隊列中記錄關(guān)鍵字的最低位值相等，然

43、后再改變所有非空隊列的隊尾指針，令其指向下一個非空隊列的隊頭記錄，重新將rd個隊列中的記錄收集成一個鏈表。（3）對第二低位關(guān)鍵字進行分配、收集依次進行，直到對最高位關(guān)鍵字進行分配、收集，便可得到一個有序序列。 24 七月 2022 【例8-7】待排序序列為 128,689,792,056,482,396,521,730，使用鏈式基數(shù)排序法將其按照從小到大的順序排列。 解：首先將待排序的記錄以靜態(tài)鏈表存儲，表頭指向第一個記錄，如下圖(a)所示。24 七月 2022對最低數(shù)位（個位）上的關(guān)鍵字進行第一趟分配，改變記錄的指針將鏈表中的記錄分配到10個隊列中。重新將10個隊列中的記錄按從小到大進行收集

44、，形成一個鏈表，如下圖(b)所示。24 七月 2022 按第一趟的思路和方法對十位數(shù)進行分配與收集，就是第二趟，其結(jié)果如圖(c)所示。 24 七月 2022第三趟分配與收集是對百位數(shù)進行的，結(jié)果如圖(d)所示。 24 七月 2022 鏈表基數(shù)排序進行的分配和收集的趟數(shù)等于主關(guān)鍵字被分成的子關(guān)鍵字的個數(shù)。如在上題中，主關(guān)鍵字被分成的子關(guān)鍵字的個數(shù)是3，故需要進行3趟分配與收集，才能完成鏈式基數(shù)排序。 在描述算法之前先定義相關(guān)的數(shù)據(jù)類型如下。24 七月 2022為了簡單，假定主關(guān)鍵字已被分解成MAX_NUM_OF_KEY個子關(guān)鍵字，存儲在數(shù)組中#define MAX_NUM_OF_KEY 8 #d

45、efine RADIX 10 關(guān)鍵字的基數(shù)，在此是十進制整數(shù)的基數(shù)#define MAX_SIZE 10000 鏈表結(jié)點個數(shù)typedef struct 靜態(tài)鏈表結(jié)點結(jié)構(gòu)KeyType keysMAX_NUM_OF_KEY;子關(guān)鍵字數(shù)組DataType otheritems; 其他數(shù)據(jù)項int next; 鏈表指針SLCell;typedef struct靜態(tài)鏈表結(jié)構(gòu)，r0為表頭結(jié)點SLCell rMAX_SIZE;int keynum1; 記錄中，當(dāng)前關(guān)鍵字的個數(shù)int recnum; 當(dāng)前記錄的長度SLList;typedef int ArrTypeRADIX; 指針數(shù)組類型24 七月 2

46、022 鏈式基數(shù)排序的具體實現(xiàn)如算法8.13、算法8.14和算法8.15所示。 void Distribute(SLCell &r,int i,ArrType &f,ArrType &e) 鏈式基數(shù)排序中第i趟分配算法 本算法按第i個子關(guān)鍵字keyi建立RADIX個隊列，同一隊列中的記錄的keyi 值相同，f0.RADIX和e0.RADIX分別指向各個隊列中的隊頭和隊尾，對靜態(tài) 鏈表L進行第i趟分配，鏈表按照key0,key1,keyi-1對結(jié)點r進行排序 for(j=0;jRADIX;j+)fj=0; for(p=r0.next;p;p=rp.next)j=rp.keyi;if(!fj) f

47、j=p; 如果隊列j無元素，則隊頭指向該記錄else rei.next=p; 如果隊列已有元素，則記錄插到隊尾ej=p; Distribute算法8.1324 七月 2022void Collect(SLCell &r,int i,ArrType f,ArrType e) 鏈式基數(shù)排序中的第i趟收集算法 本算法對非空的各個隊列按照keyi從小到大將f0.RADIX-1依次鏈接成一個 新的鏈表for(j=0;!fj;j=Succ(j)查找第一個非空隊列，Succ為求后繼函數(shù) r0.next=fj; t=ej;while(jRADIX) for(j=Succ(j);jRADIX & !fj;j=S

48、ucc(j)繼續(xù)查找下一個非空隊列 if(fj) rt.next=fj;t=ej; rt.next=0;t指向最后一個非空隊列中的最后一個結(jié)點Collect算法8.1424 七月 2022void RadixSort(SLList &L)對L作基數(shù)排序，使L成為按關(guān)鍵字從小到大的有序靜態(tài)表， L.r0為頭結(jié)點for(i=0;iL.length;i+) L.ri.next=i+1; 構(gòu)建待排序鏈表L.rL.recnum.next=0;for(i=0;iL.keynum;i+) Distribute(L.r,i,f,e); 第i趟分配 Collect(L.r,i,f,e); 第i趟收集 Radix

49、Sort算法8.1524 七月 2022 算法分析： 對于n個記錄，每個記錄含有d個子關(guān)鍵字，每個子關(guān)鍵字的取值范圍為rd個值，則鏈式基數(shù)排序的時間復(fù)雜度為O(d(n+rd)，其中每一趟分配的時間復(fù)雜度為O(n)，每一趟收集的時間復(fù)雜度為O(rd)，整個排序需要進行d趟分配和收集。 24 七月 20228.7 外部排序 外部排序指的是大文件的排序，排序記錄的數(shù)量很大，以致內(nèi)存不能一次容納全部記錄，待排序的記錄仍有部分存儲在外存儲器上，那么在排序過程中則需要進行多次內(nèi)、外存之間的轉(zhuǎn)換。24 七月 2022 外部排序基本上由兩個相對獨立的階段組成： （1）按可用內(nèi)存大小，將外存上含n個記錄的文件分

50、成若干長度為l的子文件或段（segment），把這些子文件依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對它們進行排序，將排序后得到的有序子文件重新寫入外存，通常稱這些有序子文件為歸并段或順串。 （2）對這些歸并段進行逐趟歸并，使歸并段逐漸由小到大，直至得到整個有序文件為止。 第一個階段為內(nèi)部排序的操作，第二個階段為歸并的過程。 8.7.1 外部排序的方法24 七月 2022 內(nèi)存歸并排序在開始時是把數(shù)組中的每個元素均看作是長度為1的有序表，在歸并過程中，有序表的長度從1開始，依次呈2n增長，直至有序表的長度等于待排序的記錄數(shù)n為止。 對外存文件的歸并排序中，初始有序表的長度通常是從一個確定的長度開始，

51、這是為了能夠有效地減少歸并的趟數(shù)和訪問外存的次數(shù)，以提高外部排序的效率。 24 七月 2022 在第一階段要按照初始有序表確定的長度在原文件上依次建立好每個有序表，在第二個階段再調(diào)用對文件的歸并排序算法完成排序。 【例8-8】 對一個含有10 000個記錄的文件進行外部排序。 解：首先通過10次內(nèi)部排序得到10個初始歸并段R1R10，其中每一段都含有1 000個記錄。然后對它們進行如下圖所示的兩兩歸并，直至得到一個有序文件。24 七月 2022 由上圖可見，由10個初始歸并段到一個有序文件，共進行了4趟歸并，每一趟從m個歸并段得到 個歸并段，這種歸并方法稱為二路平衡歸并。 外部排序?qū)崿F(xiàn)兩兩歸并

52、不僅要調(diào)用前面所學(xué)的merge歸并過程，還要進行外存的讀/寫，這是因為不能將兩個有序段及歸并結(jié)果同時放在內(nèi)存中。 24 七月 2022 一般情況下，外部排序所需的總時間由下式計算： 外部排序所需的總時間=內(nèi)部排序（產(chǎn)生初始歸并段）所需的時間(mtIS)+外存信息讀寫的時間(dtIO)+內(nèi)部歸并所需的時間(sutmg)其中，tIS是為得到一個初始歸并段進行內(nèi)部排序所需時間的均值，tIO是進行一次外存讀/寫時間的均值，utmg是對u個記錄進行內(nèi)部歸并所需時間，m為經(jīng)過內(nèi)部排序之后得到的初始歸并段的個數(shù)，s為歸并的趟數(shù)，d為總的讀/寫次數(shù)。 24 七月 2022 【例8-8】中的記錄利用二路歸并進行外部排序所需的總時間=10tIS+500tIO +410 000tmg，其中tIO取決于所用的外存設(shè)備，顯然tIO要比tmg大得多。因此，提高外部排序的效率應(yīng)主要放在減少外存信息讀寫的次數(shù)d上。 分析d和“歸并過程”的關(guān)系。 對【例8-8】中所得的10個初始歸并段進行5-路平衡歸并