數(shù)據(jù)結構課件：第7章 排序

1、第七章 排 序,第七章 排序,7.1 基本概念 7.2 插入排序 7.3 交換排序 7.4 選擇排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序,從數(shù)學和計算機角度而言，簡單地說排序算法就是把元素按照一定的序關系列表，最常見的序關系是數(shù)字序和字典序。 高效的排序算法有助于提高其他算法的效率，如查找算法。此外，在很多情況下，排序有助于規(guī)范化數(shù)據(jù)和便于人類閱讀、理解。 盡管排序問題本身相對于其他計算理論問題而言并不復雜，但要設計高效的、有針對性的排序算法也并非易事，因此針對它的研究一直在持續(xù)開展。,排序，也叫分類，是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律排列起來的過程。 文

2、件，是待排序數(shù)據(jù)對象的集合；一個數(shù)據(jù)對象也叫作一個記錄，記為R1，R2，Rn 關鍵詞域(key): 通常數(shù)據(jù)對象由多個屬性域(多個數(shù)據(jù)成員)組成，其中可將一個屬性域作為排序依據(jù)，該域即為關鍵詞域。 關鍵詞記為：K1，K2，Kn； 排序：將記錄按關鍵詞域遞增或遞減的順序排列,7.1 基本概念,每個文件用哪個屬性域作為關鍵詞，要視具體的應用需要而定；即使是同一個文件表，在解決不同問題的場合也可能取不同的關鍵詞域。 主關鍵詞: 如果在數(shù)據(jù)表中各個對象的關鍵詞互不相同，這種關鍵詞即主關鍵詞。按照主關鍵詞排序，排序的結果是唯一的。 次關鍵詞: 數(shù)據(jù)表中有些對象的關鍵詞可能相同，這種關鍵詞稱為次關鍵詞。按

3、照次關鍵詞排序，排序的結果可能不唯一。,排序算法的度量指標: 排序的時間開銷(排序算法的時間復雜性):是衡量算法好壞的最重要標志?？捎盟惴▓?zhí)行中關鍵詞的比較次數(shù)與數(shù)據(jù)的移動次數(shù)來衡量。 各算法的時間復雜性一般都按平均情況進行估算。對那些受對象初始排列及對象個數(shù)影響較大的，需要按最好和最壞情況進行估算。 算法的空間復雜性:主要考察排序過程所需輔助存儲空間的大小。 排序算法的穩(wěn)定性: 如果在對象序列中有兩個對象ri和rj，它們的關鍵詞ki=kj，且在排序之前對象ri排在rj前面，如果在排序之后，對象ri仍在對象rj的前面，則稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。,排序算法有多種分類

4、方法: 從元素的存儲設備角度可分為內(nèi)排序（在內(nèi)存中進行）和外排序（在外存儲器上進行）。 按對關鍵詞的操作可分為基于關鍵詞比較的排序算法和分布排序算法。 按時間代價分類：平方階排序算法，它們一般都比較簡單，特點是容易實現(xiàn)，但時間復雜度相對較高，最壞情況下時間復雜度一般為O(n2)；線性對數(shù)階算法，以分治策略算法為主，最壞情況下時間復雜度一般為O(nlog(n).,第七章 排序,7.1 基本概念 7.2 插入排序 直接插入排序 希爾排序 7.3 交換排序 7.4 選擇排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序,7.2 插入排序,例： 原有序表：(9 15 23

5、28 37) 20 找插入位置 : (9 15 23 28 37) 20 新有序表: (9 15 20 23 28 37),插入排序思想 基于插入操作所完成的排序。 插入:將一個記錄插入到已排好序的有序表中，從而得到一個新的記錄數(shù)增一的有序表。,7.2.1 直接插入排序算法 1. 基本思想 待排序記錄 R1，R2， ，Rn1, Rn 第一步：R1 第二步：(R1 ), R2 第三步：(R1 , R2), R3 第 j 步：(R1，R2， ，Rj1), Rj 第 n 步: (R1，R2， ，Rn1), Rn,例：j=5,9,15,28,23,08,1 2 3 4 5 6,16,16,28,16,

6、23,16,16,一次插入過程,16,16,原有序表中關鍵詞比Rj大的記錄數(shù)：dj 比較次數(shù)：dj+1 移動次數(shù)： dj+2,28,16,23,2. 算法描述 算法 InsertSort (R,n) FOR j2 TO n DO ( /每次將Rj插入到有序表R1，Rj1中 KKj. RRj. ij-1. WHILE (i0) AND (KiK) DO (Ri+1Ri. ii-1.) Ri+1R. ),算法InsertSortA( R, s, e ) /引入虛擬記錄,Ks-1minKi| sie ISA1 逐一排序 FOR js+1 TO e DO ( ij-1KKj. RRj . WHILE

7、KKi DO ( Ri+1Ri ii-1 ) Ri+1R ) ,ISA1 逐一排序 FOR js+1 TO e DO ( ij-1KKj . RRj . WHILE KKi DO ( Ri+1Ri ii-l ) Ri+1R ) ,3. 算法分析 設dj是Rj左邊關鍵詞大于Kj的記錄個數(shù)，則算法InsertSortA中關鍵詞的比較次數(shù)為： 記錄的移動次數(shù)為,最好情況下，排序前記錄已經(jīng)按關鍵詞從小到大有序排列，即dj=0。每趟只需與前面的有序部分的最后一個記錄的關鍵詞比較 1 次，記錄移動 2 次，總的關鍵詞比較次數(shù)為 n-1，記錄移動次數(shù)為 2(n-1)。,最壞情況下：第i趟時，第i個記錄前面所

8、有記錄的關鍵詞都比第i個記錄的關鍵詞大，即dj=j-1 總的關鍵詞比較次數(shù)： 記錄移動次數(shù)：,平均情況下，若待排序文件中記錄所有可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關鍵詞比較次數(shù)和記錄移動次數(shù)分別為 因此，直接插入排序的時間復雜度為 O(n2)。,平均情況下，考察分析 的期望值。 對于序列K1，K2，Kn ，如果1ijn，且KiKj，則稱(Ki , Kj)為上述序列的一個反序對。實際上， 正好是序列K1，K2，Kn的反序對個數(shù)。 例 待排序記錄：8，7，2，4，6中反序對的個數(shù) 是7個。,則有,反序對的平均個數(shù) = 0+ (0+1)/2+ (0+1+2)/

9、3+ (0123)/4(01234)/5 (012345)/6 (012n1)/n 01/22/2 3/24/25/2( n1)/2 n(n1)/4 即 的期望值為n(n1)/4 .,4.直接插入排序算法總結 優(yōu)點:是算法的執(zhí)行過程相當清晰，并且書寫容易. 缺點:期望復雜性為O(n2) . 穩(wěn)定性：直接插入排序是穩(wěn)定的排序方法。 最好情況是：當被排序文件初態(tài)為正序時，算法的時間復雜度為O(n) . 輔助空間： O(1),5. 直接插入排序算法是否可以進一步改進呢？ 直接插入排序算法中包含了一個查找過程，對前部已經(jīng)排序完的記錄執(zhí)行順序查找。這顯然是其效率低下的原因之一，是否可以通過改進順序查找來

10、提高排序效率呢?,通過將順序查找改為二分查找，可以構造二分插入排序算法。即在插入第j個元素時，不是像直接插入排序那樣順序尋找插入的位置，而是采用對半（或二分）的方法插入。 如果文件（R1，R2，Rn）采用順序存儲，則對半插入排序算法可以減少關鍵詞的比較次數(shù)，但是記錄的移動次數(shù)仍不能減少。 如果文件（R1，R2，Rn）采用鏈接存儲，不能使用對半的方法尋找插入位置。,第七章 排序,7.1 基本概念 7.2 插入排序 直接插入排序 希爾排序 7.3 交換排序 7.4 選擇排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序 7.8 外排序,7.2.2 希爾(shell)排序

11、 1、希爾排序（漸減增量排序法）思想： 1959年Donald L. Shell提出Shell排序法 ，源自對直接插入算法的改進. 把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。,例 將十個數(shù)進行希爾排序的示例。,0 1 2 3 4 5 6 7 8 9,下標,例 將十個數(shù)進行希爾排序的示例。, 希爾排序增量的取法：,2、算法分析,Shell算法的性能與所選取的分組長度序列有很大關系。 只對特定的待排序記錄序列，可以準確地估算關鍵詞的比較次數(shù)和對象移動次數(shù)。 想要弄清關鍵詞比較次數(shù)和記錄移

12、動次數(shù)與增量選擇之間的關系，并給出完整的數(shù)學分析，至今仍然是數(shù)學難題。,Shell算法的性能與所選取的分組長度序列有很大關系。 前面介紹的實例是最簡單的分組長度序列，即n/2i，最壞情況下時間復雜度為O(n2). 一般實際應用中選擇2.2作為遞減因子效果更好，而不是2 . 如果選擇2k-1為分組長度序列，最壞情況下能達到 .,第七章 排序,7.1 基本概念 7.2 插入排序 7.3 交換排序 冒泡排序 快速排序 7.4 選擇排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序 7.8 外排序,7.3 交換排序 反序對：對于序列K1, K2, , Kn, 若1iKj ,

13、 則稱(Ki,Kj)為上述序列的一個反序對。 交換排序的思想：交換文件中存在的反序對，直到不存在反序對為止。 交換排序包括：冒泡排序、分劃交換排序（快速排序）。,7.3.1 冒泡排序 1、冒泡排序思想： 通過比較相鄰記錄的關鍵詞，交換存在逆序的記錄；使關鍵詞較大的記錄如氣泡一般逐漸往上“飄移”直至浮出“水面”。,i = 1,2、冒泡排序算法 算法BSort ( R，n ) BS1 冒泡過程 FOR i=n TO 2 STEP 1 DO FOR j=1 TO i1 DO IF Kj Kj+1 THEN ( RjRj+1 ). 關鍵詞的比較次數(shù): (n-1)+(n-2)+1= (n-1)n/2,經(jīng)

14、過一趟冒泡，可以把具有最大關鍵詞的記錄移至最后（第n個位置）。 第i趟冒泡，把第i大記錄放在第i個位置上。 做n-1趟冒泡，就可以對所有記錄排序。 發(fā)生一次記錄交換，反序對的個數(shù)減少一個。 排序中可能出現(xiàn)如下情況：每趟比較中，在某位置后，沒有記錄交換；最后幾趟沒有交換。,i = 1,3、冒泡排序算法的改進,算法Bubble ( R，n ) Bubble1 終止位置初始化 BOUNDn /每趟冒泡關鍵詞比較的終止位置 Bubble2 冒泡過程 WHILE BOUND0 DO ( t0 /每趟冒泡記錄交換的最后位置 FOR j1 TO BOUND1 DO IF Kj Kj+1 THEN ( RjR

15、j+1 . tj .) BOUNDt ) . ,4、算法分析 最好情形：記錄的初始排列按關鍵詞從小到大排好序時，此算法只執(zhí)行一趟起泡，做 n-1 次關鍵詞比較，不發(fā)生記錄交換； 最壞情形：算法執(zhí)行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次關鍵詞比較，執(zhí)行了n-i 次記錄交換,此時，總的關鍵詞比較次數(shù)和記錄交換次數(shù)為(n-1)n/2,一般情形 假定記錄序列R1，R2，Rn所對應的關鍵詞序列為A = K1，K2，Kn 令bj（1 j n）表示A中關鍵詞第 j 小的記錄左邊大于它的關鍵詞的個數(shù)，則文件 b1，b2，bn 稱為A的反序表. A=07, 09, 02, 16, 08,

16、 05, 12, 14, 13 B=2, 4, 0, 2, 0, 1, 2, 1 , 0,經(jīng)過一趟冒泡后，記錄的位置發(fā)生變化，反序表也發(fā)生變化。 定理7.1 設K1，K2，Kn是序列1，2，n的一個排列，b1，b2，bn是對應的反序表. 如果算法Bubble的一趟冒泡把K1, K2, Kn改變?yōu)镵1, K2, Kn, 那么從b1, b2, bn中把每個非零元素減1, 就得到了相應的反序表b1,b2,bn .,A=07, 09, 02, 16, 08, 05, 12, 14, 13 B=2, 4, 0, 2, 0, 1, 2, 1 , 0 A=07, 02, 09, 08, 05, 12, 14

17、, 13 , 16 B=1, 3, 0, 1, 0, 0, 1, 0 , 0,證明：如果Kj（1 j n）的左邊有大于Kj的元素，設Km = max Kt | 1 t Kj ，則由算法Bubble知，Rm一定會與Rj交換，且Rj左邊的其它元素不能與Rj交換。所以 如果Kj（1 j n）的左邊沒有大于Kj的元素，即，則說明Rj左邊的所有元素都小于Kj，從而一趟冒泡之后，Rj左邊的任何元素都不與Rj交換（因為它們都小于Kj），所以仍然有 . 證畢。,改進的冒泡排序算法的復雜性：,5、冒泡排序算法總結 時間復雜度：O(n2)（包括最壞和平均） . 最好情況：當被排序文件初態(tài)為正序時，算法的時間復雜度

18、為O(n) . 穩(wěn)定性：冒泡排序是穩(wěn)定的排序方法。 輔助存儲空間：O(1) .,為了進一步提高效率，可采用氣泡上浮和下沉交替的方法。,第七章 排序,7.1 基本概念 7.2 插入排序 7.3 交換排序 冒泡排序 快速排序 7.4 選擇排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序 7.8 外排序,7.3.2 分劃交換排序 1962年，Hoare提出了分劃交換排序，也叫快速排序 (Quick Sort)。 算法的出發(fā)點： 1、通過交換反序對排序，一次記錄交換使得文件中反序對的數(shù)目減少得最多; 2、一趟分劃把一個記錄直接放在其最終的位置上。,1、快速排序的基本思想:

19、 任取待排序文件中的某個記錄 (例如取第一個記錄)作為基準，按照該記錄的關鍵詞大小，將整個文件分劃為左右兩個子文件： 左側子文件中所有記錄的關鍵詞都小于或等于基準記錄的關鍵詞 右側子文件中所有記錄的關鍵詞都大于基準記錄的關鍵詞 基準記錄排在兩個子文件中間。 分別對兩個子文件重復上述方法，直到所有記錄都排在相應位置上為止。,2、快速排序算法描述 QuickSort ( R ) if (R的長度大于1) 將文件R分劃為兩個子文件LeftR 和 RightR; QuickSort ( LeftR ); QuickSort ( RightR ); 將兩個子文件 LeftR 和 RightR合并為一個文

20、件R; ,算法QSort(R, m, n) / 快速排序的遞歸算法 QSort1 遞歸出口 /Rm為基準記錄，Rn+1關鍵詞最大 IF (mK DO jj1 . IF ij THEN Ri Rj ) RmRj . / 對 Rm.n 進行一趟快排，j為基準位置 IF mj-1 QSort ( R，m，j1 ) . / 對低子序列遞歸進行排序 IF j+1n QSort ( R，j+1，n ) ) / 對高子序列遞歸進行排序,18 68 69 23 11 70 93 73 100,WHILE iK DO jj1 . IF ij THEN Ri Rj ) RmRj .,快速排序一次分劃過程示例:,多

21、趟快速排序過程示例,算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) . L1: IF j+1n QSort ( R，j+1，n ). L2: ) ,棧,L m n j,算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) . L1: IF j+1n QSort ( R，j+1，n ). L2: ) ,棧,L m n j,算法QSort(R，m，n)

22、 IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) . L1: IF j+1n QSort ( R，j+1，n ). L2: ) ,棧,L m n j,算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) . L1: IF j+1n QSort ( R，j+1，n ). L2: ) ,棧,L m n j,算法QSort(R，m，n) IF m n THEN ( im . jn+1

23、 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) . L1: IF j+1n QSort ( R，j+1，n ). L2: ) ,棧,L m n j,算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序段 IF mj-1 QSort ( R，m，j1 ) . L1: IF j+1n QSort ( R，j+1，n ). L2: ) ,棧空,L m n j,算法QSort(R，m，n) IF m n THEN ( im . jn+1 . KKm . QSort1；/一次分劃程序

24、段 IF mj-1 QSort ( R，m，j1 ) . L1: IF j+1n QSort ( R，j+1，n ). L2: ) ,3、算法分析 算法Qsort是遞歸的算法，其遞歸樹如圖所示。,一個結點表示一次遞歸調(diào)用。 快速排序的趟數(shù)取決于遞歸樹的深度。 每次分劃后，基準記錄的左右子序列長度相同，是最理想的情況。,一次分劃過程(R,m,n)，有兩個記錄與基準記錄比較兩次，其余的記錄和基準記錄各比較一次。關鍵詞的比較次數(shù)為n-m+2。,18 68 69 23 11 70 93 73 100,4、快速排序算法總結 時間復雜度: O(n2)/最壞 . 時間復雜度: O(nlog2n) /最好和平

25、均 輔助空間： O(log2n) . 穩(wěn)定性：快速排序是不穩(wěn)定的排序方法。 快速排序方法對于 n 較大的平均情況而言，是目前內(nèi)部排序中最好、最快的排序方法。但當 n 很小時，這種排序方法往往比其它簡單排序方法還慢。,第七章 排序,7.1 基本概念 7.2 插入排序 7.3 交換排序 7.4 選擇排序 直接選擇排序 堆排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序 7.8 外排序,7.4 選擇排序 思想：對待排序的文件進行n次選擇操作，其中第i次選擇第i小(或大)的記錄放在第i(或n-i+1)的位置上。 直接選擇排序、堆排序,7.4.1 直接選擇排序 1、直接選擇

26、排序思想： 選擇第 i （i = 1,2, , n-1）大的記錄的具體辦法：在剩余的n-i+1個記錄中進行一趟比較，確定出第i大記錄，放在第n-i+1位置上。 17 78 6 54 34 38 17 38 6 54 34 78 17 38 6 34 54 78,2、直接選擇排序算法 算法 SSort (R, n) /待排序文件(R1,R2,Rn) SS1 排序 FOR j=n TO 2 STEP 1 DO ( /從1到j找最大元素的下標t t1 . FOR i2 TO j DO IF KtKi THEN ti RjRt ) / 將Rt放到第j個位置上,(1) (2) (3) (4) (5) (

27、6),i t,2 算法 SSort（R，n） FOR j=n TO 2 STEP -1 DO ( t1 . FOR i2 TO j DO IF Kt Ki THEN ti Rj Rt) ,21 25 49 25* 16 08 3 2,21 25 49 25* 16 08 4 3,21 25 49 25* 16 08 5 3,21 25 49 25* 16 08 6 3,21 25 08 25* 16 49,21 25 49 25* 16 08,一趟直接選擇排序過程示例,多趟直接選擇排序過程示例,(1) (2) (3) (4) (5) (6),t,1 21 25 08 25* 16 49 2,2

28、 21 16 08 25* 25 49 4,3 21 16 08 25* 25 49 1,5 08 16 21 25* 25 49,4 08 16 21 25* 25 49 2,3、算法分析 直接選擇排序的關鍵詞比較次數(shù)與記錄的初始排列無關。假定整個待排序文件有 n 個記錄，則第 i 趟選擇所需的比較次數(shù)是 n-i 次?？偟年P鍵詞比較次數(shù)為 (n-1)+(n-2)+1= (n-1)n/2 記錄交換次數(shù)是選擇的趟數(shù): n-1.,4、直接選擇排序算法總結 時間復雜度: O(n2)（包括最好、最壞和平均） . 穩(wěn)定性：不穩(wěn)定的排序方法。 輔助空間： O(1) . 優(yōu)點：簡單、書寫容易,第七章 排序,

29、7.1 基本概念 7.2 插入排序 7.3 交換排序 7.4 選擇排序 直接選擇排序 堆排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序 7.8 外排序,7.4.2 堆排序 1、堆排序的原理 選擇排序的關鍵：找最大記錄 堆排序：利用淘汰賽的方式尋找當前序列中的最大記錄 淘汰賽的思想：對n個選手，兩兩比賽，得到 n/2 個優(yōu)勝者，作為第一輪的結果；然后對這n/2個選手，再兩兩比賽，如此重復，直到選出一個冠軍。,滿二叉樹的葉結點，存放待排序記錄的關鍵詞。 如果 n 不是2的 k 次冪，則讓葉結點數(shù)補足到滿足 2k-1 n 2k 的2k個。 非葉結點是關鍵詞兩兩比較的結

30、果，根結點的關鍵詞最大。,比賽樹的概念,每次兩兩比較的結果是把關鍵詞大者作為優(yōu)勝者上升到雙親結點，稱這種樹為比賽樹。 位于最底層的葉結點叫做比賽樹的外結點，非葉結點稱為比賽樹的內(nèi)結點。每個結點除了存放記錄的關鍵詞外，還存放了此對象在滿二叉樹中的序號。 比賽樹最頂層是樹的根，表示最后選擇出來的具有最大關鍵詞的記錄。,形成初始比賽樹（最大關鍵詞上升到根） 得到最大記錄R7,R7,利用比賽樹的排序第1步,將剩余6個記錄，調(diào)整為新的比賽樹 得到第2大記錄R6,49,Winner,49,16,16,-,49,25,21,25,49,25*,16,08,-,tree7 tree8 tree9 tree10

31、 tree11 tree12 tree13 tree14,R6,利用比賽樹的排序第2步,將剩余6個記錄，調(diào)整為新的比賽樹 得到第2大記錄R6,25,Winner,25,16,16,-,25*,25,21,25,25*,16,08,-,tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14,R5,利用比賽樹的排序第3步,-,上述過程重復進行 結果全部輸出時，比賽樹的狀態(tài),08,Winner,08,08,-,-,08,-,tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14,R1,-,-,-,-,

32、-,-,-,2、堆的定義 如果有一個關鍵碼的集合Kk1,k2,kn把它的所有元素按完全二叉樹的順序(數(shù)組)存 儲方式存放在一個一維數(shù)組中。并且滿足 ki k2i且ki k2i+1 / 小根堆 或 ki k2i且ki k2i+1 / 大根堆,例 1 2 3 4 5 6 7 8 9 10 11 12 94 93 75 91 85 44 51 18 48 58 10 34,堆的定義,完全二叉樹的數(shù)組表示 Ki K2i & Ki K2i+1,完全二叉樹的數(shù)組表示 Ki K2i & Ki K2i+1,3、堆排序算法 設數(shù)組R存放堆，則R1是關鍵詞最大的記錄，將R1和Rn互換，使得最大記錄放在Rn的位置。

33、 調(diào)整R1，Rn-1，使之成為新堆，則R1是其中最大者，再交換R1與Rn-1，使Rn-1中放入次最大記錄。 再對R1，R2，Rn-2調(diào)整，使之成為新堆，再進行類似的交換，上述操作反復進行，直到調(diào)整范圍只剩下一個記錄R1為止。此時，R1是n個記錄中最小的，且數(shù)組Rn中的記錄已經(jīng)按從小到大排列了。,堆排序算法的粗略描述： （l）建立包含Kl，K2，Kn的堆； （2）FOR in TO 2 STEP 1 DO （R1Ri 重建包含K1，K2，Ki1的堆 ） 需解決的兩個問題： 如何建堆 如何調(diào)整新堆,問題 初始建堆: 將以序號n/2，n/21 , 1的結點為根的子樹都調(diào)整為堆即可。 例 關鍵詞序列（

34、42,13,91,23,24,16,05,88)。,初始建堆過程圖形說明：,問題重建堆：R1與Ri交換后，只有R1與其左右兒子不滿足堆的性質。,堆排序過程圖形說明：,堆排序過程：,堆排序過程：,堆排序過程：,堆排序過程：,堆排序過程：,堆排序過程：,算法Restore（R，f，e）/ 建堆 R1 初始化 jf R2 建堆 WHILE je/2 DO (IF(2j Kj THEN（RmRj . jm ） ELSE je ）,HS1 初始建堆 FOR in2 TO 1 STEP 1 DO Restore（R，i，n） ,算法HeapSort ( R，n ) / 堆排序算法 HS1 初始建堆 FOR

35、 in2 TO 1 STEP 1 DO Restore（R，i，n） HS2 排序 FOR in TO 2 STEP 1 DO ( R1Ri . Restore ( R，1，i1 ) ) ,重建堆算法的時間復雜 度為 O(log2n),4、堆排序算法總結 時間復雜度: 最好、最壞和平均情況相同 重建堆算法為 O(log2n) 堆排序算法為O(nlog2n) . 穩(wěn)定性：堆排序是不穩(wěn)定的排序方法。 輔助存儲空間： O(1) .,49,25,25*,21,16,08,0,1,2,3,4,5,08,25,25*,16,21,49,0,2,5,4,3,1,49 25 21 25* 16 08,08 2

36、5 21 25* 16 49,交換 0 號與 5 號對象, 5 號對象就位,初始最大堆,25,25*,08,21,16,49,0,1,2,3,4,5,16,25*,08,25,21,49,0,2,5,4,3,1,25 25* 21 08 16 49,16 25* 21 08 25 49,25,25*,08,21,16,49,0,1,2,3,4,5,16,25*,08,25,21,49,0,2,5,4,3,1,25 25* 21 08 16 49,16 25* 21 08 25 49,交換 0 號與 4 號對象, 4 號對象就位,從 0 號到 4 號 重新 調(diào)整為最大堆,25*,16,08,21

37、,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,25* 16 21 08 25 49,08 16 21 25* 25 49,交換 0 號與 3 號對象, 3 號對象就位,從 0 號到 3 號 重新 調(diào)整為最大堆,21,16,25*,08,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,21 16 08 25* 25 49,08 16 21 25* 25 49,交換 0 號與 2 號對象, 2 號對象就位,從 0 號到 2 號 重新 調(diào)整為最大堆,堆存在于順序線性表（數(shù)組）中,16,08,25*

38、,21,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,16 08 21 25* 25 49,08 16 21 25* 25 49,交換 0 號與 1 號對象, 1 號對象就位,從 0 號到 1 號 重新 調(diào)整為最大堆,第七章 排序,7.1 基本概念 7.2 插入排序 7.3 交換排序 7.4 選擇排序 7.5 合并排序 7.6 基于關鍵詞比較的排序算法分析 7.7 分布排序,7.5 合并排序 1、合并 合并(歸并)：把兩個或多個有序文件合并成一個單一的有序文件。 合并的基本思想：設兩個有序表A和B的記錄個數(shù)(表長)分別為 al 和 bl，變量 i 和 j 分別是表A和表B的當前檢測指針。設表C是歸并后的新有序表，變量 k 是它的當前存放指針。,08 21 25 25* 49 62 72 93,16 37 54,l m m+1 n,i j,08