第10章內(nèi)部排序

1、第第10章章 內(nèi)部排序內(nèi)部排序 在信息處理過程中，最基本的操作是查找。從查找在信息處理過程中，最基本的操作是查找。從查找來說，效率最高的是折半查找，折半查找的前提是所來說，效率最高的是折半查找，折半查找的前提是所有的數(shù)據(jù)元素有的數(shù)據(jù)元素(記錄記錄)是按關(guān)鍵字有序的。需要將一個無是按關(guān)鍵字有序的。需要將一個無序的數(shù)據(jù)文件轉(zhuǎn)變?yōu)橐粋€有序的數(shù)據(jù)文件。序的數(shù)據(jù)文件轉(zhuǎn)變?yōu)橐粋€有序的數(shù)據(jù)文件。 將任一文件中的記錄通過某種方法整理成為按將任一文件中的記錄通過某種方法整理成為按(記記錄錄)關(guān)鍵字有序排列的處理過程稱為關(guān)鍵字有序排列的處理過程稱為排序排序。 排序是排序是數(shù)據(jù)處理數(shù)據(jù)處理中一種中一種最常用的操作最

2、常用的操作。10.1 排序的基本概念排序的基本概念 排序排序(Sorting) 排序排序是將一批是將一批(組組)任意次序的記錄重新排列成任意次序的記錄重新排列成按關(guān)按關(guān)鍵字有序鍵字有序的記錄序列的過程，其定義為：的記錄序列的過程，其定義為： 給定一組記錄序列：給定一組記錄序列：R1 , R2 , Rn，其相應(yīng)的關(guān)鍵，其相應(yīng)的關(guān)鍵字序列是字序列是K1 , K2 , Kn 。確定。確定1, 2, n的一個排列的一個排列p1 , p2 , pn，使其相應(yīng)的關(guān)鍵字滿足如下非遞減，使其相應(yīng)的關(guān)鍵字滿足如下非遞減(或非遞增或非遞增)關(guān)系：關(guān)系： Kp1Kp2 Kpn的序列的序列Kp1 ,Kp2 , ,Kp

3、n ，這種操作，這種操作稱為排序。稱為排序。 關(guān)鍵字關(guān)鍵字Ki可以是記錄可以是記錄Ri的主關(guān)鍵字，也可以是次關(guān)的主關(guān)鍵字，也可以是次關(guān)鍵字或若干數(shù)據(jù)項的組合。鍵字或若干數(shù)據(jù)項的組合。 Ki是主關(guān)鍵字：排序后得到的結(jié)果是唯一的；是主關(guān)鍵字：排序后得到的結(jié)果是唯一的； Ki是次關(guān)鍵字：排序后得到的結(jié)果是不唯一的。是次關(guān)鍵字：排序后得到的結(jié)果是不唯一的。 排序的穩(wěn)定性排序的穩(wěn)定性 若記錄序列中有若記錄序列中有兩個或兩個以上關(guān)鍵字相等兩個或兩個以上關(guān)鍵字相等的記錄：的記錄： Ki =Kj(ij，i, j=1, 2, n)，且在排序前，且在排序前Ri先于先于Rj(ij)，排序，排序后的記錄序列仍然是后的

4、記錄序列仍然是Ri先于先于Rj，稱排序方法是穩(wěn)定的，稱排序方法是穩(wěn)定的，否則是不穩(wěn)定的。否則是不穩(wěn)定的。 排序算法有許多，但就全面性能而言，還沒有一種排序算法有許多，但就全面性能而言，還沒有一種公認(rèn)為最好的。每種算法都有其優(yōu)點和缺點，分別適合公認(rèn)為最好的。每種算法都有其優(yōu)點和缺點，分別適合不同的數(shù)據(jù)量和硬件配置。不同的數(shù)據(jù)量和硬件配置。 評價排序算法的標(biāo)準(zhǔn)有：評價排序算法的標(biāo)準(zhǔn)有：執(zhí)行時間執(zhí)行時間和和所需的輔助空所需的輔助空間間，其次是，其次是算法的穩(wěn)定性算法的穩(wěn)定性。 若排序算法所需的輔助空間不依賴問題的規(guī)模若排序算法所需的輔助空間不依賴問題的規(guī)模n，即，即空間復(fù)雜度是空間復(fù)雜度是O(1)

5、，則稱排序方法是，則稱排序方法是就地排序就地排序，否則是，否則是非就地排序非就地排序。 排序的分類排序的分類 待排序的記錄數(shù)量不同，排序過程中涉及的存儲器待排序的記錄數(shù)量不同，排序過程中涉及的存儲器的不同，有不同的排序分類。的不同，有不同的排序分類。 待排序的記錄數(shù)不太多待排序的記錄數(shù)不太多：所有的記錄都能存放在內(nèi)存中進：所有的記錄都能存放在內(nèi)存中進行排序，稱為行排序，稱為內(nèi)部排序內(nèi)部排序； 待排序的記錄數(shù)太多待排序的記錄數(shù)太多：所有的記錄不可能存放在內(nèi)存中，：所有的記錄不可能存放在內(nèi)存中， 排序過程中必須在內(nèi)、外存之間進行數(shù)據(jù)交換，這樣的排序排序過程中必須在內(nèi)、外存之間進行數(shù)據(jù)交換，這樣的排

6、序稱為稱為外部排序外部排序。 內(nèi)部排序的基本操作內(nèi)部排序的基本操作 對內(nèi)部排序地而言，其基本操作有兩種：對內(nèi)部排序地而言，其基本操作有兩種： 比較兩個關(guān)鍵字的大?。槐容^兩個關(guān)鍵字的大?。?存儲位置的移動：從一個位置移到另一個位置。存儲位置的移動：從一個位置移到另一個位置。 第一種操作是必不可少的；而第二種操作卻不是必第一種操作是必不可少的；而第二種操作卻不是必須的，取決于記錄的存儲方式，具體情況是：須的，取決于記錄的存儲方式，具體情況是： 記錄存儲在一組連續(xù)地址的存儲空間記錄存儲在一組連續(xù)地址的存儲空間：記錄之間的邏輯順：記錄之間的邏輯順序關(guān)系是通過其物理存儲位置的相鄰來體現(xiàn)，序關(guān)系是通過其物

7、理存儲位置的相鄰來體現(xiàn)，記錄的移動是記錄的移動是必不可少的必不可少的； 記錄采用鏈?zhǔn)酱鎯Ψ绞接涗洸捎面準(zhǔn)酱鎯Ψ绞剑河涗浿g的邏輯順序關(guān)系是通過：記錄之間的邏輯順序關(guān)系是通過結(jié)點中的指針來體現(xiàn)，排序過程結(jié)點中的指針來體現(xiàn)，排序過程僅需修改結(jié)點的指針僅需修改結(jié)點的指針，而，而不不需要移動記錄需要移動記錄； 記錄存儲在一組連續(xù)地址的存儲空間記錄存儲在一組連續(xù)地址的存儲空間：構(gòu)造另一個輔助表：構(gòu)造另一個輔助表來保存各個記錄的存放地址來保存各個記錄的存放地址(指針指針) ：排序過程：排序過程不需要移動記不需要移動記錄錄，而，而僅需修改僅需修改輔助表中的輔助表中的指針指針，排序后視具體情況決定是，排序后視

8、具體情況決定是否調(diào)整記錄的存儲位置。否調(diào)整記錄的存儲位置。 比較適合記錄數(shù)較少的情況；而比較適合記錄數(shù)較少的情況；而、則適合記則適合記錄數(shù)較少的情況。錄數(shù)較少的情況。 為討論方便，假設(shè)待排序的記錄是以為討論方便，假設(shè)待排序的記錄是以的情況存儲，的情況存儲，且設(shè)排序是按升序排列的；關(guān)鍵字是一些可直接用比較且設(shè)排序是按升序排列的；關(guān)鍵字是一些可直接用比較運算符進行比較的類型。運算符進行比較的類型。待排序的記錄類型的定義如下：待排序的記錄類型的定義如下：#define MAX_SIZE 100Typedef int KeyType ;typedef struct RecType KeyType ke

9、y ; /* 關(guān)鍵字碼關(guān)鍵字碼 */infoType otherinfo ; /* 其他域其他域 */RecType ;typedef struct Sqlist RecType RMAX_SIZE ;int length ;Sqlist ;10.2 插入排序插入排序 采用的是以采用的是以 “玩橋牌者玩橋牌者”的方法為基礎(chǔ)的。即在考的方法為基礎(chǔ)的。即在考察記錄察記錄Ri之前，設(shè)以前的所有記錄之前，設(shè)以前的所有記錄R1, R2 ,., Ri-1已排已排好序，然后將好序，然后將Ri插入到已排好序的諸記錄的適當(dāng)位置。插入到已排好序的諸記錄的適當(dāng)位置。 最基本的插入排序是最基本的插入排序是直接插入排序

10、直接插入排序(Straight Insertion Sort) 。10.2.1 直接插入排序直接插入排序1 排序思想排序思想 將待排序的記錄將待排序的記錄Ri，插入到已排好序的記錄表，插入到已排好序的記錄表R1, R2 ,., Ri-1中，得到一個新的、記錄數(shù)增加中，得到一個新的、記錄數(shù)增加1的有序表。的有序表。 直到所有的記錄都插入完為止。直到所有的記錄都插入完為止。 設(shè)待排序的記錄順序存放在數(shù)組設(shè)待排序的記錄順序存放在數(shù)組R1n中，在排中，在排序的某一時刻，將記錄序列分成兩部分：序的某一時刻，將記錄序列分成兩部分： R1i-1：已排好序的有序部分；：已排好序的有序部分； Rin：未排好序的

11、無序部分。：未排好序的無序部分。 顯然，在剛開始排序時，顯然，在剛開始排序時，R1是已經(jīng)排好序的。是已經(jīng)排好序的。 例：例：設(shè)有關(guān)鍵字序列為：設(shè)有關(guān)鍵字序列為：7, 4, -2, 19, 13, 6，直接插，直接插入排序的過程如下圖入排序的過程如下圖10-1所示：所示：初始記錄的關(guān)鍵字：初始記錄的關(guān)鍵字： 7 4 -2 19 13 6第一趟排序：第一趟排序： 4 7 -2 19 13 6第二趟排序：第二趟排序： -2 4 7 19 13 6第三趟排序：第三趟排序： -2 4 7 19 13 6第四趟排序：第四趟排序： -2 4 7 13 19 6第五趟排序：第五趟排序： -2 4 6 7 13

12、 19圖圖10-1 直接插入排序的過程直接插入排序的過程2 算法實現(xiàn)算法實現(xiàn)void straight_insert_sort(Sqlist *L) int i, j ;for (i=2; ilength; i+) L-R0=L-Ri; j=i-1; /* 設(shè)置哨兵設(shè)置哨兵 */while( LT(L-R0.key, L-Rj.key) ) L-Rj+1=L-Rj; j-; /* 查找插入位置查找插入位置 */L-Rj+1=L-R0; /* 插入到相應(yīng)位置插入到相應(yīng)位置 */3 算法說明算法說明 算法中的算法中的R0開始時并不存放任何待排序的記錄，引開始時并不存放任何待排序的記錄，引入的作用主

13、要有兩個：入的作用主要有兩個： 不需要增加輔助空間：不需要增加輔助空間： 保存當(dāng)前待插入的記錄保存當(dāng)前待插入的記錄Ri，Ri會因為記錄的后移而被占用；會因為記錄的后移而被占用； 保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊界之前找到一個等于當(dāng)前記錄的記錄，起界之前找到一個等于當(dāng)前記錄的記錄，起“哨兵監(jiān)視哨兵監(jiān)視”作用，避免在內(nèi)循環(huán)中每次都要判斷作用，避免在內(nèi)循環(huán)中每次都要判斷j是否越界。是否越界。4 算法分析算法分析 最好情況最好情況：若待排序記錄按關(guān)鍵字從小到大排若待排序記錄按關(guān)鍵字從小到大排列列(正序正序)，算法中的內(nèi)循環(huán)無須執(zhí)行，則一趟排序時：，算

14、法中的內(nèi)循環(huán)無須執(zhí)行，則一趟排序時：關(guān)鍵字比較次數(shù)關(guān)鍵字比較次數(shù)1次，記錄移動次數(shù)次，記錄移動次數(shù)2次次(RiR0, R0Rj+1)。 則整個排序的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)分則整個排序的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)分別是：別是：比較次數(shù)：比較次數(shù)：1=n-1ni=2移動次數(shù)：移動次數(shù)： 2=2(n-1)ni=2 最壞情況最壞情況：若待排序記錄按關(guān)鍵字從大到小排若待排序記錄按關(guān)鍵字從大到小排列列(逆序逆序)，則一趟排序時：算法中的內(nèi)循環(huán)體執(zhí)行，則一趟排序時：算法中的內(nèi)循環(huán)體執(zhí)行i-1，關(guān)鍵字比較次數(shù)，關(guān)鍵字比較次數(shù)i次，記錄移動次數(shù)次，記錄移動次數(shù)i+1。則就整個排序而言：則就整個排序而言：

15、比較次數(shù)：比較次數(shù)： i=ni=2(n-1)(n+1)2移動次數(shù)：移動次數(shù)：(i+1)=ni=2(n-1)(n+4)2 一般地，認(rèn)為待排序的記錄可能出現(xiàn)的各種排列的概一般地，認(rèn)為待排序的記錄可能出現(xiàn)的各種排列的概率相同，則取以上兩種情況的平均值，作為排序的關(guān)鍵率相同，則取以上兩種情況的平均值，作為排序的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)，約為字比較次數(shù)和記錄移動次數(shù)，約為n2/4，則復(fù)雜度為，則復(fù)雜度為O(n2) 。10.2.2 其它插入排序其它插入排序1 折半插入排序折半插入排序 當(dāng)將待排序的記錄當(dāng)將待排序的記錄Ri 插入到已排好序的記錄子表插入到已排好序的記錄子表R1i-1中時，由于中時，由于R

16、1, R2 , Ri-1已排好序，則查找插入已排好序，則查找插入位置可以用位置可以用“折半查找折半查找”實現(xiàn)，則直接插入排序就變成實現(xiàn)，則直接插入排序就變成為折半插入排序。為折半插入排序。 算法實現(xiàn)算法實現(xiàn)void Binary_insert_sort(Sqlist *L) int i, j, low, high, mid ;for (i=2; ilength; i+) L-R0=L-Ri; /* 設(shè)置哨兵設(shè)置哨兵 */low=1 ; high=i-1 ; while (lowR0.key, L-Rmid.key) ) high=mid-1 ; else low=mid+1 ; /* 查找插入

17、位置查找插入位置 */for (j=i-1; j=high+1; j-)L-Rj+1=L-Rj; L-Rhigh+1=L-R0; /* 插入到相應(yīng)位置插入到相應(yīng)位置 */ 從時間上比較，折半插入排序僅僅減少了關(guān)鍵字的比從時間上比較，折半插入排序僅僅減少了關(guān)鍵字的比較次數(shù)，卻沒有減少記錄的移動次數(shù)，故時間復(fù)雜度仍較次數(shù)，卻沒有減少記錄的移動次數(shù)，故時間復(fù)雜度仍然為然為O(n2) 。 排序示例排序示例 設(shè)有一組關(guān)鍵字設(shè)有一組關(guān)鍵字30, 13, 70, 85, 39, 42, 6, 20，采用，采用折半插入排序方法排序的過程如圖折半插入排序方法排序的過程如圖10-2所示：所示：i=1 (30) 1

18、3 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85) 20i=8 20 (6 13 30 39 42 70 85) 20lowhighmidi=8 20 (6 13 30 39 42 70 85) 20lowhighmidi=8 20 (6 13 30 39 42 70 85) 20mid highlowi=8 20 (6 13 20 30 39 42 70 85)圖圖10-2 折半插入排序過程折半插入排序過程2 2-路插入排序路插入排序 是對折半插入排序的改進是對折半插入排序的改進，以減少排序

19、過程中移動記以減少排序過程中移動記錄的次數(shù)。附加錄的次數(shù)。附加n個記錄的輔助空間個記錄的輔助空間，方法是，方法是： 另設(shè)一個和另設(shè)一個和L-R同類型的數(shù)組同類型的數(shù)組d，L-R1賦給賦給d1，將，將d1看成是排好序的序列中中間位置的記錄；看成是排好序的序列中中間位置的記錄； 分別將分別將L-R 中的第中的第i個記錄依次插入到個記錄依次插入到d1之前或之后之前或之后的的有序序列中，具體方法有序序列中，具體方法： L-Ri.keyRi插入到插入到d1之前之前的有序表中；的有序表中； L-Ri.keyd1.key： L-Ri插入到插入到d1之后之后的的有序表中；有序表中；關(guān)鍵點關(guān)鍵點：實現(xiàn)時將實現(xiàn)時

20、將向量向量d看成是循環(huán)向量，并設(shè)兩個指看成是循環(huán)向量，并設(shè)兩個指針針first和和final分別指示排序過程中得到的有序序列中的分別指示排序過程中得到的有序序列中的第一個和最后一個記錄第一個和最后一個記錄。排序示例排序示例設(shè)有初始關(guān)鍵字集合設(shè)有初始關(guān)鍵字集合49, 38, 65, 13, 97, 27, 76 ，采用，采用2-路插入排序的過程如右圖路插入排序的過程如右圖10-3所示。所示。 在在2-路插入排序中，移動記錄的次數(shù)約為路插入排序中，移動記錄的次數(shù)約為n2/8 。但。但當(dāng)當(dāng)L-R1是待排序記錄中關(guān)鍵字最大或最小的記錄時，是待排序記錄中關(guān)鍵字最大或最小的記錄時，2-路插入排序就完全失去

21、了優(yōu)越性。路插入排序就完全失去了優(yōu)越性。2776d49firstfirstfirstfirstfinalfinalfinalfinal653897971313圖圖10-3 2-路插入排序過程路插入排序過程3 表插入排序表插入排序前面的插入排序不可避免地要移動記錄，若不移動記錄前面的插入排序不可避免地要移動記錄，若不移動記錄就需要改變數(shù)據(jù)結(jié)構(gòu)。附加就需要改變數(shù)據(jù)結(jié)構(gòu)。附加n個記錄的輔助空間，記錄個記錄的輔助空間，記錄類型修改為：類型修改為：typedef struct RecNode KeyType key ;infotype otherinfo ;int *next;RecNode ;初始化初

22、始化：下標(biāo)值為：下標(biāo)值為0的分量作為表頭結(jié)點的分量作為表頭結(jié)點，關(guān)鍵字取為最大值，關(guān)鍵字取為最大值，各分量的指針值為空；各分量的指針值為空； 將靜態(tài)鏈表中將靜態(tài)鏈表中數(shù)組下標(biāo)值為數(shù)組下標(biāo)值為1的分量的分量(結(jié)點結(jié)點)與表頭結(jié)點構(gòu)成與表頭結(jié)點構(gòu)成一個循環(huán)鏈表；一個循環(huán)鏈表； i=2 ，將分量，將分量Ri按關(guān)鍵字遞減插入到循環(huán)鏈表；按關(guān)鍵字遞減插入到循環(huán)鏈表； 增加增加i ，重復(fù)，直到全部分量插入到循環(huán)鏈表。，重復(fù)，直到全部分量插入到循環(huán)鏈表。例：例：設(shè)有關(guān)鍵字集合設(shè)有關(guān)鍵字集合49, 38, 65, 97, 76, 13, 27, 49 ，采用表插入排序的過程如下圖采用表插入排序的過程如下圖10

23、-4所示。所示。 0 1 2 3 4 5 6 7 8key域域next域域MAXINT 49 38 65 13 97 27 76 49 1 0 - - - - - - -i=2MAXINT 49 38 65 13 97 27 76 49 2 0 1 - - - - - -i=3MAXINT 49 38 65 13 97 27 76 49 2 3 1 0 - - - - -i=4MAXINT 49 38 65 13 97 27 76 49 4 3 1 0 2 - - - -i=5MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 2 0 - - - 和直接插入排序相比，

24、不同的是修改和直接插入排序相比，不同的是修改2n次指針值次指針值以代替移動記錄，而關(guān)鍵字的比較次數(shù)相同，故時間復(fù)以代替移動記錄，而關(guān)鍵字的比較次數(shù)相同，故時間復(fù)雜度為雜度為O(n2)。 表插入排序得到一個有序鏈表，對其可以方便地進行表插入排序得到一個有序鏈表，對其可以方便地進行順序查找，但不能實現(xiàn)隨即查找。根據(jù)需要，可以對記順序查找，但不能實現(xiàn)隨即查找。根據(jù)需要，可以對記錄進行重排，記錄重排詳見錄進行重排，記錄重排詳見P268。i=6MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 6 0 2 - -i=7MAXINT 49 38 65 13 97 27 76 49

25、 4 3 1 7 6 0 2 5 -i=8MAXINT 49 38 65 13 97 27 76 49 4 8 1 7 6 0 2 5 3圖圖10-4 表插入排序過程表插入排序過程10.2.3 希爾排序希爾排序 希爾排序希爾排序(Shell Sort，又稱，又稱縮小增量法縮小增量法)是一種分組插是一種分組插入排序方法入排序方法。1 排序思想排序思想 先取一個正整數(shù)先取一個正整數(shù)d1(d1n)作為第一個增量，將全部作為第一個增量，將全部n個記錄個記錄分成分成d1組，把所有相隔組，把所有相隔d1的記錄放在一組中，即對于每個的記錄放在一組中，即對于每個k(k=1, 2, d1)，Rk, Rd1+k,

26、 R2d1+k , 分在同一組中，在各組內(nèi)進分在同一組中，在各組內(nèi)進行直接插入排序行直接插入排序。這樣一次分組和排序過程稱為一趟這樣一次分組和排序過程稱為一趟希爾排序希爾排序； 取新的增量取新的增量d2d1，重復(fù)，重復(fù)的分組和排序操作；直至所取的的分組和排序操作；直至所取的增量增量di=1為止，即所有記錄放進一個組中排序為止為止，即所有記錄放進一個組中排序為止。2 排序示排序示例例 設(shè)有設(shè)有10個待排序的記錄，關(guān)鍵字分別為個待排序的記錄，關(guān)鍵字分別為9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是，增量序列是5, 3, 1，希爾排序的過程如，希爾排序的過程如圖圖10

27、-5所示所示。9 7 1 2 5 13 13 8 15 11第一趟排序后第一趟排序后:2 5 1 9 7 13 11 8 15 13第二趟排序后第二趟排序后:1 2 5 7 8 9 11 13 13 15第三趟排序后第三趟排序后:圖圖10-5 希爾排序過程希爾排序過程9 13 8 2 5 13 7 1 15 1171318初始關(guān)鍵字序列初始關(guān)鍵字序列:第一趟排序過程第一趟排序過程:3 算法實現(xiàn)算法實現(xiàn) 先給出一趟希爾排序的算法，類似直接插入排序。先給出一趟希爾排序的算法，類似直接插入排序。void shell_pass(Sqlist *L, int d) /* 對順序表對順序表L進行一趟希爾排

28、序進行一趟希爾排序, 增量為增量為d */ int j, k ;for (j=d+1; jlength; j+) L-R0=L-Rj ; /* 設(shè)置監(jiān)視哨兵設(shè)置監(jiān)視哨兵 */k=j-d ;while (k0&LT(L-R0.key, L-Rk.key) ) L-Rk+d=L-Rk ; k=k-d ; L-Rk+j=L-R0 ; 然后在根據(jù)增量數(shù)組然后在根據(jù)增量數(shù)組dk進行希爾排序。進行希爾排序。void shell_sort(Sqlist *L, int dk, int t) /* 按增量序列按增量序列dk0 t-1,對順序表對順序表L進行希爾排序進行希爾排序 */ int m ;fo

29、r (m=0; mR1與與L-R2的關(guān)鍵字進行比較的關(guān)鍵字進行比較，若為反序，若為反序(L-R1的關(guān)鍵字大于的關(guān)鍵字大于L-R2的關(guān)鍵字的關(guān)鍵字)，則交換兩個記錄，則交換兩個記錄；然后然后比較比較L-R2與與L-R3的關(guān)鍵字的關(guān)鍵字，依此類推，直到，依此類推，直到L-Rn-1與與L-Rn的關(guān)鍵字比較后為止的關(guān)鍵字比較后為止，稱為一趟，稱為一趟冒泡排序冒泡排序，L-Rn為關(guān)為關(guān)鍵字最大的記錄鍵字最大的記錄。 然后進行第二趟然后進行第二趟冒泡排序冒泡排序，對前，對前n-1個記錄進行同樣的操個記錄進行同樣的操作作。 一般地，第一般地，第i趟冒泡排序是對趟冒泡排序是對L-R1 n-i+1中的記錄中的記

30、錄進行的進行的，因此，若待排序的記錄有，因此，若待排序的記錄有n個個，則要經(jīng)過，則要經(jīng)過n-1趟趟冒泡排序才能使所有的記錄有序冒泡排序才能使所有的記錄有序。2 排序示排序示例例 設(shè)有設(shè)有9個待排序的記錄，關(guān)鍵字分別為個待排序的記錄，關(guān)鍵字分別為23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的過程如圖，冒泡排序的過程如圖10-6所示所示。3 算法實現(xiàn)算法實現(xiàn)#define FALSE 0#define TRUE 1圖圖10-6 冒泡排序過程冒泡排序過程23 38 22 45 23 67 31 15 41初始關(guān)鍵字序列初始關(guān)鍵字序列:第一趟排序后第一趟排序后:23

31、22 38 23 45 31 15 41 67第二趟排序后第二趟排序后:22 23 23 38 31 15 41 45 67第三趟排序后第三趟排序后:22 23 23 31 15 38 41 45 67第四趟排序后第四趟排序后:22 23 23 15 31 38 41 45 67第五趟排序后第五趟排序后:22 23 15 23 31 38 41 45 67第六趟排序后第六趟排序后:22 15 23 23 31 38 41 45 67第七趟排序后第七趟排序后:15 22 23 23 31 38 41 45 67void Bubble_Sort(Sqlist *L) int j ,k , flag

32、 ;for (j=0; jlength; j+) /* 共有共有n-1趟排序趟排序 */ flag=TRUE ;for (k=1; klength-j; k+) /* 一趟排序一趟排序 */ if (LT(L-Rk+1.key, L-Rk.key ) ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if (flag=TRUE) break ;故時間復(fù)雜度故時間復(fù)雜度：T(n)=O(n)空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)4 算法分析算法分析時間復(fù)雜度時間復(fù)雜度 最好情況最好情況(正序正序)：比較次數(shù)：比較次數(shù)：n-1；移動次數(shù)

33、：；移動次數(shù)：0； 最壞情況最壞情況(逆序逆序)：比較次數(shù)：比較次數(shù)：(n-i)=n-1i=1n(n-1)2移動次數(shù)：移動次數(shù)： 3(n-i)=n-1i=13n(n-1)210.3.2 快速排序快速排序1 排序思想排序思想 通過一趟排序，將待排序記錄分割成獨立的兩部分，通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再分別對這兩部分記錄進行下一趟排序，以達到整個序再分別對這兩部分記錄進行下一趟排序，以達到整個序列有序列有序。2 排序過程排序過程 設(shè)待排序的記錄序列是設(shè)待排序的記錄序列是Rst ，在

34、記錄序列中任取，在記錄序列中任取一個記錄一個記錄(一般取一般取Rs)作為作為參照參照(又稱為又稱為基準(zhǔn)基準(zhǔn)或或樞軸樞軸)，以，以Rs.key為基準(zhǔn)重新排列其余的所有記錄，方法是：為基準(zhǔn)重新排列其余的所有記錄，方法是： 所有關(guān)鍵字比基準(zhǔn)小的放所有關(guān)鍵字比基準(zhǔn)小的放Rs之前；之前； 所有關(guān)鍵字比基準(zhǔn)大的放所有關(guān)鍵字比基準(zhǔn)大的放Rs之后之后。 以以Rs.key最后所在位置最后所在位置i作為分界，將序列作為分界，將序列Rst分分割成兩個子序列，稱為一趟快速排序割成兩個子序列，稱為一趟快速排序。3 一趟快速排序方法一趟快速排序方法 從序列的兩端交替掃描各個記錄，將從序列的兩端交替掃描各個記錄，將關(guān)鍵字小

35、于關(guān)鍵字小于基準(zhǔn)關(guān)鍵字的記錄基準(zhǔn)關(guān)鍵字的記錄依次依次放置到序列的前邊放置到序列的前邊；而將；而將關(guān)鍵字關(guān)鍵字大于基準(zhǔn)關(guān)鍵字的記錄大于基準(zhǔn)關(guān)鍵字的記錄從序列的最后端起，依次從序列的最后端起，依次放置到放置到序列的后邊序列的后邊，直到掃描完所有的記錄，直到掃描完所有的記錄。 設(shè)置指針設(shè)置指針low，high，初值為第，初值為第1個和最后一個記錄個和最后一個記錄的位置。的位置。 設(shè)兩個變量設(shè)兩個變量i，j，初始時令，初始時令i=low，j=high，以以Rlow.key作為基準(zhǔn)作為基準(zhǔn)(將將Rlow保存在保存在R0中中) 。 從從j所指位置向前搜索：將所指位置向前搜索：將R0.key與與Rj.key

36、進行比較：進行比較： 若若R0.keyRj.key ：令：令j=j-1，然后繼續(xù)進行比，然后繼續(xù)進行比較，較， 直到直到i=j或或R0.keyRj.key為止；為止； 若若R0.keyRj.key ：RjRi，騰空騰空Rj的位的位置置， 且令且令i=i+1； 從從i所指位置起向后搜索：將所指位置起向后搜索：將R0.key與與Ri.key進行比較：進行比較： 若若R0.keyRi.key ：令：令i=i+1，然后繼續(xù)進行比，然后繼續(xù)進行比較，較， 直到直到i=j或或R0.keyRi.key為止；為止； 若若R0.keyR0=L-Ri ; /* R0作為臨時單元和哨兵作為臨時單元和哨兵 */do

37、while (LQ(L-R0.key, L-Rj.key)&(ji) j- ;if (ji) L-Ri=L-Rj ; i+; while (LQ(L-Ri.key, L-R0.key)&(ji) i+ ;if (ji) L-Rj=L-Ri ; j-; while(i!=j) ; /* i=j時退出掃描時退出掃描 */L-Ri=L-R0 ; return(i) ; 快速排序算法實現(xiàn)快速排序算法實現(xiàn) 當(dāng)進行一趟快速排序后，采用同樣方法分別對兩個當(dāng)進行一趟快速排序后，采用同樣方法分別對兩個子序列快速排序，直到子序列記錄個為子序列快速排序，直到子序列記錄個為1為止為止。 遞歸算法遞歸算

38、法 void quick_Sort(Sqlist *L , int low, int high) int k ;if (lowhigh) k=quick_one_pass(L, low, high);quick_Sort(L, low, k-1);quick_Sort(L, k+1, high); /* 序列分為兩部分后分別對每個子序列排序序列分為兩部分后分別對每個子序列排序 */ 非遞歸算法非遞歸算法# define MAX_STACK 100void quick_Sort(Sqlist *L , int low, int high) int k , stackMAX_STACK , top

39、=0; do while (lowhigh) k=quick_one_pass(L,low,high); stack+top=high ; stack+top=k+1 ; /* 第二個子序列的上第二個子序列的上,下界分別入棧下界分別入棧 */ high=k-1 ; if (top!=0) low=stacktop- ; high=stacktop- ; while (top!=0&low1時，用時，用n-1代替中的代替中的n，得到：，得到：Tavg(n)=(n-1)C+ Tavg(k) n-2k=02n nTavg(n)-(n-1)Tavg(n-1)=(2n-1)C+2Tavg(n-1

40、) ，即即Tavg(n)=(n+1)/nTavg(n-1)+(2n-1)/nC(n+1)/nTavg(n-1)+2C(n+1)/nn/(n-1)Tavg(n-2)+2C+2C=(n+1)/(n-1)Tavg(n-2)+2(n+1)1/n+1/(n+1)C Tavg(1)+2(n+1)C2n+13141+1n+1n1+ Tavg(n)只有只有1個記錄的排序時間是一個常數(shù)，個記錄的排序時間是一個常數(shù)， 快速排序的平均時間復(fù)雜度是快速排序的平均時間復(fù)雜度是：T(n)=O(n2n) 從所需要的附加空間來看，快速排序算法是遞歸調(diào)從所需要的附加空間來看，快速排序算法是遞歸調(diào)用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)

41、每次劃分比較均勻用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)每次劃分比較均勻時，棧的最大深度為時，棧的最大深度為2n+1 。 快速排序的空間復(fù)雜度是：快速排序的空間復(fù)雜度是：S(n)=O(2n) 從排序的穩(wěn)定性來看，快速排序是從排序的穩(wěn)定性來看，快速排序是不穩(wěn)定不穩(wěn)定的。的。10. 4 選擇排序選擇排序 選擇排序選擇排序(Selection Sort)的基本思想是：每的基本思想是：每次從當(dāng)前待排序的記錄中選取關(guān)鍵字最小的記錄表，然次從當(dāng)前待排序的記錄中選取關(guān)鍵字最小的記錄表，然后與待排序的記錄序列中的第一個記錄進行交換，直到后與待排序的記錄序列中的第一個記錄進行交換，直到整個記錄序列有序為止。整個記錄序列

42、有序為止。 10.4.1 簡單選擇排序簡單選擇排序 簡單選擇排序簡單選擇排序(Simple Selection Sort ，又稱為，又稱為直接選擇排序直接選擇排序)的基本操作是：通過的基本操作是：通過n-i次關(guān)鍵字間的比次關(guān)鍵字間的比較，從較，從n-i+1個記錄中選取關(guān)鍵字最小的記錄，然后和第個記錄中選取關(guān)鍵字最小的記錄，然后和第i個記錄進行交換，個記錄進行交換，i=1, 2, n-1 。1 排序示例排序示例 例：例：設(shè)有關(guān)鍵字序列為：設(shè)有關(guān)鍵字序列為：7, 4, -2, 19, 13, 6，直接，直接選擇排序的過程如下圖選擇排序的過程如下圖10-8所示。所示。圖圖10-8 直接選擇排序的過程

43、直接選擇排序的過程初始記錄的關(guān)鍵字：初始記錄的關(guān)鍵字： 7 4 -2 19 13 6第一趟排序：第一趟排序：-2 4 7 19 13 6第二趟排序：第二趟排序： -2 4 7 19 13 6第三趟排序：第三趟排序： -2 4 6 19 13 7第四趟排序：第四趟排序： -2 4 6 7 13 19第五趟排序：第五趟排序： -2 4 6 7 13 19第六趟排序：第六趟排序： -2 4 6 7 13 192 算法實現(xiàn)算法實現(xiàn)void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1; mlength; m+) k=m ; for (n=

44、m+1; nlength; n+) if ( LT(L-Rn.key, L-Rk.key) ) k=n ;if (k!=m) /* 記錄交換記錄交換 */ L-R0=L-Rm; L-Rm=L-Rk; L-Rk=L-R0; 3 算法分析算法分析 整個算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對整個算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對n個記錄進行排序的趟數(shù)為個記錄進行排序的趟數(shù)為n-1趟；內(nèi)循環(huán)控制每一趟的趟；內(nèi)循環(huán)控制每一趟的排序。排序。 進行第進行第i趟排序時，關(guān)鍵字的比較次數(shù)為趟排序時，關(guān)鍵字的比較次數(shù)為n-i，則：，則：比較次數(shù)：比較次數(shù)： (n-i)=n-1i=1n(n-1)2 時間復(fù)雜

45、度是：時間復(fù)雜度是：T(n)=O(n2) 空間復(fù)雜度是：空間復(fù)雜度是：S(n)=O(1) 從排序的穩(wěn)定性來看，直接選擇排序是從排序的穩(wěn)定性來看，直接選擇排序是不穩(wěn)定不穩(wěn)定的。的。10.4.2 樹形選擇排序樹形選擇排序 借助借助“淘汰賽淘汰賽”中的對壘就很容易理解樹形選擇排序中的對壘就很容易理解樹形選擇排序的思想。的思想。 首先對首先對n個記錄的關(guān)鍵字兩兩進行比較個記錄的關(guān)鍵字兩兩進行比較，選取，選取n/2個較小者；然后這個較小者；然后這n/2個較小者個較小者兩兩進行比較兩兩進行比較，選，選取取n/4個較小者個較小者 如此重復(fù)，直到只剩如此重復(fù)，直到只剩1個關(guān)鍵字為個關(guān)鍵字為止止。該過程可用一棵

46、有該過程可用一棵有n個葉子結(jié)點的完全二叉樹表示，如個葉子結(jié)點的完全二叉樹表示，如圖圖10-9所示。所示。 每個枝結(jié)點的關(guān)鍵字都等于其左、右孩子結(jié)點中較每個枝結(jié)點的關(guān)鍵字都等于其左、右孩子結(jié)點中較小的關(guān)鍵字，小的關(guān)鍵字，根結(jié)點的關(guān)鍵字就是最小的關(guān)鍵字根結(jié)點的關(guān)鍵字就是最小的關(guān)鍵字。 輸出最小關(guān)鍵字后，根據(jù)輸出最小關(guān)鍵字后，根據(jù)關(guān)系的可傳遞性關(guān)系的可傳遞性，欲選取次，欲選取次小關(guān)鍵字，只需將葉子結(jié)點中的最小關(guān)鍵字改為小關(guān)鍵字，只需將葉子結(jié)點中的最小關(guān)鍵字改為“最大最大值值” ，然后重復(fù)上述步驟即可。，然后重復(fù)上述步驟即可。 含有含有n個葉子結(jié)點的完全二叉樹的深度為個葉子結(jié)點的完全二叉樹的深度為2n

47、+1，則總的時間復(fù)雜度為則總的時間復(fù)雜度為O(n2n) 。492525372828196519153415251515圖圖10- “淘汰賽淘汰賽”過程示意圖過程示意圖10.4.3 堆排序堆排序1 堆的定義堆的定義 是是n個元素的序列個元素的序列H=k1, k2 , kn ，滿足，滿足：kik2i 當(dāng)當(dāng)2in時時kik2i+1 當(dāng)當(dāng)2i+1n時時或或kik2i 當(dāng)當(dāng)2in時時ki k2i+1 當(dāng)當(dāng)2i+1n時時其中：其中： i=1,2 , , n/2 由堆的定義知，堆是一棵以由堆的定義知，堆是一棵以k1為根的完全二叉樹。為根的完全二叉樹。若對該二叉樹的結(jié)點進行編號若對該二叉樹的結(jié)點進行編號(從上

48、到下，從左到右從上到下，從左到右)，得到的序列就是將二叉樹的結(jié)點以得到的序列就是將二叉樹的結(jié)點以順序結(jié)構(gòu)存放順序結(jié)構(gòu)存放，堆的，堆的結(jié)構(gòu)正好和該序列結(jié)構(gòu)完全一致。結(jié)構(gòu)正好和該序列結(jié)構(gòu)完全一致。2 堆的性質(zhì)堆的性質(zhì) 堆是一棵采用順序存儲結(jié)構(gòu)的完全二叉樹，堆是一棵采用順序存儲結(jié)構(gòu)的完全二叉樹， k1是根結(jié)點；是根結(jié)點； 堆的根結(jié)點是關(guān)鍵字序列中的最小堆的根結(jié)點是關(guān)鍵字序列中的最小(或最大或最大)值，分別稱為值，分別稱為小小(或大或大)根堆；根堆； 從根結(jié)點到每一葉子結(jié)點路徑上的元素組成的序列都是從根結(jié)點到每一葉子結(jié)點路徑上的元素組成的序列都是按元素值按元素值(或關(guān)鍵字值或關(guān)鍵字值)非遞減非遞減(或

49、非遞增或非遞增)的；的；堆中的任一子樹也是堆堆中的任一子樹也是堆。 利用堆頂記錄的關(guān)鍵字值最小利用堆頂記錄的關(guān)鍵字值最小(或最大或最大)的性質(zhì)，從的性質(zhì)，從當(dāng)前待排序的記錄中當(dāng)前待排序的記錄中依次選取關(guān)鍵字最小依次選取關(guān)鍵字最小(或最大或最大)的記的記錄，就可以實現(xiàn)對數(shù)據(jù)記錄的排序，這種排序方法稱為錄，就可以實現(xiàn)對數(shù)據(jù)記錄的排序，這種排序方法稱為堆排序堆排序。3 堆排序思想堆排序思想 對一組待排序的記錄，按堆的定義對一組待排序的記錄，按堆的定義建立堆建立堆； 將將堆頂記錄和最后一個記錄交換堆頂記錄和最后一個記錄交換位置，則前位置，則前n-1個記錄是無序的，而最后一個記錄是有序的；個記錄是無序的

50、，而最后一個記錄是有序的； 堆頂記錄堆頂記錄被交換后，前被交換后，前n-1個記錄不再是堆，需個記錄不再是堆，需將前將前n-1個待排序記錄重新組織成為一個堆，然后個待排序記錄重新組織成為一個堆，然后將將堆頂記錄和倒數(shù)第二個記錄交換堆頂記錄和倒數(shù)第二個記錄交換位置，即將整個位置，即將整個序列中次小關(guān)鍵字值的記錄調(diào)整序列中次小關(guān)鍵字值的記錄調(diào)整(排除排除)出無序區(qū)；出無序區(qū)； 重復(fù)上述步驟，直到全部記錄排好序為止。重復(fù)上述步驟，直到全部記錄排好序為止。 結(jié)論結(jié)論：排序過程中，若采用排序過程中，若采用小根堆小根堆，排序后得到的是，排序后得到的是非遞減序列非遞減序列；若采用；若采用大根堆大根堆，排序后得

51、到的是，排序后得到的是非遞增非遞增序列序列。堆排序的關(guān)鍵堆排序的關(guān)鍵 如何由一個無序序列建成一個堆？如何由一個無序序列建成一個堆？ 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？成為一個新的堆？ 4 堆的調(diào)整堆的調(diào)整篩選篩選 堆的調(diào)整思想堆的調(diào)整思想 輸出堆頂元素之后，以堆中最后一個元素替代之；然輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與與其中小者進行交換其中小者進行交換；重復(fù)上述操作，直到是葉子結(jié)點或；重復(fù)上述操作，直到是葉子結(jié)點或其關(guān)鍵字值

52、小于等于左、右子樹的關(guān)鍵字的值，將得到其關(guān)鍵字值小于等于左、右子樹的關(guān)鍵字的值，將得到新的堆。稱這個從堆頂至葉子的調(diào)整過程為新的堆。稱這個從堆頂至葉子的調(diào)整過程為“篩選篩選”，如，如圖圖10-10所示。所示。注意注意：篩選過程中，根結(jié)點的左、右子樹都是堆，因篩選過程中，根結(jié)點的左、右子樹都是堆，因此，篩選是從根結(jié)點到某個葉子結(jié)點的一次調(diào)整過程。此，篩選是從根結(jié)點到某個葉子結(jié)點的一次調(diào)整過程。圖圖10-10 堆的篩選過程堆的篩選過程49253728196534182715492537281965342718154927372819653425181549253728196534181527 堆調(diào)

53、整算法實現(xiàn)堆調(diào)整算法實現(xiàn)void Heap_adjust(Sqlist *H, int s, int m)/* H-Rsm中記錄關(guān)鍵字除中記錄關(guān)鍵字除H-Rs.key均滿足堆定義均滿足堆定義 */* 調(diào)整調(diào)整H-Rs的位置使之成為的位置使之成為小根堆小根堆 */ int j=s, k=2*j ; /* 計算計算H-Rj的左孩子的位置的左孩子的位置 */H-R0=H-Rj ; /* 臨時保存臨時保存H-Rj */ for (k=2*j; k=m; k=2*k) if (kRk+1.key, H-Rk.key) k+ ; /* 選擇左、右孩子中關(guān)鍵字的最小者選擇左、右孩子中關(guān)鍵字的最小者 */if

54、 ( LT(H-Rk.key, H-R0.key) ) H-Rj=H-Rk ; j=k ; k=2*j else break ;H-Rj=H-R0 ; 5 堆的建立堆的建立 利用篩選算法，可以將任意無序的記錄序列建成一利用篩選算法，可以將任意無序的記錄序列建成一個堆，設(shè)個堆，設(shè)R1,R2, ,Rn是待排序的記錄序列。是待排序的記錄序列。 將二叉樹的將二叉樹的每棵子樹都篩選成為堆每棵子樹都篩選成為堆。只有根結(jié)點的。只有根結(jié)點的樹是堆。第樹是堆。第 n/2 個結(jié)點之后的所有結(jié)點都沒有子樹，個結(jié)點之后的所有結(jié)點都沒有子樹，即以第即以第n/2個結(jié)點之后的結(jié)點為根的子樹都是堆。個結(jié)點之后的結(jié)點為根的子樹

55、都是堆。因此，以這些結(jié)點為左、右孩子的結(jié)點，其左、右子樹因此，以這些結(jié)點為左、右孩子的結(jié)點，其左、右子樹都是堆，則都是堆，則進行一次篩選進行一次篩選就可以成為堆。同理，只要將就可以成為堆。同理，只要將這些結(jié)點的直接父結(jié)點這些結(jié)點的直接父結(jié)點進行一次篩選進行一次篩選就可以成為堆就可以成為堆。 只需從第只需從第n/2個記錄到第個記錄到第1個記錄依次進行篩選個記錄依次進行篩選就可以建立堆。就可以建立堆。可用下列語句實現(xiàn)：可用下列語句實現(xiàn)：for (j=n/2; j=1; j-)Heap_adjust(R, j , n) ;6 堆排序算法實現(xiàn)堆排序算法實現(xiàn) 堆的根結(jié)點是關(guān)鍵字最小的記錄，輸出根結(jié)點后，

56、堆的根結(jié)點是關(guān)鍵字最小的記錄，輸出根結(jié)點后，是以序列的最后一個記錄作為根結(jié)點，而原來堆的左、是以序列的最后一個記錄作為根結(jié)點，而原來堆的左、右子樹都是堆，則右子樹都是堆，則進行一次篩選進行一次篩選就可以成為堆。就可以成為堆。void Heap_Sort(Sqlist *H) int j ;for (j=H-length/2; j0; j-)Heap_adjust(H, j , H-length) ; /* 初始建堆初始建堆 */for (j=H-length/2; j=1; j-) H-R0=H-R1 ; H-R1=H-Rj ;H-Rj=H-R0 ; /* 堆頂與最后一個交換堆頂與最后一個交換

57、 */Heap_adjust(H, 1, j-1) ; 7 算法分析算法分析 主要過程：初始建堆和重新調(diào)整成堆。設(shè)記錄數(shù)為主要過程：初始建堆和重新調(diào)整成堆。設(shè)記錄數(shù)為n，所對應(yīng)的完全二叉樹深度為所對應(yīng)的完全二叉樹深度為h 。 初始建堆初始建堆：每個非葉子結(jié)點都要從上到下做：每個非葉子結(jié)點都要從上到下做“篩篩選選” 。第。第i層結(jié)點數(shù)層結(jié)點數(shù)2i-1，結(jié)點下移的最大深度是，結(jié)點下移的最大深度是h-i，而每下移一層要比較而每下移一層要比較2次，則比較次數(shù)次，則比較次數(shù)C1(n)為：為：C1(n) 2 (2i-1(h-i)4(2h-h-1)h-1i=1 h=2n+1， C1(n)4(n-2n-1)

58、篩選調(diào)整篩選調(diào)整：每次篩選要將根結(jié)點：每次篩選要將根結(jié)點“下沉下沉”到一個合到一個合適位置。第適位置。第i次篩選時：堆中元素個數(shù)為次篩選時：堆中元素個數(shù)為n-i+1；堆的；堆的深度是深度是2(n-i+1)+1，則進行，則進行n-1次次“篩選篩選”的比較的比較次數(shù)次數(shù)C2(n)為：為：C2(n) (22(n-i+1)n-1i=1 C2(n)2n2n 堆排序的比較次數(shù)的數(shù)量級為：堆排序的比較次數(shù)的數(shù)量級為： T(n)=O(n2n)；而附加空間就是交換時所用的臨時空間，故空間復(fù)雜而附加空間就是交換時所用的臨時空間，故空間復(fù)雜度為：度為： S(n)=O(1) 。10. 5 歸并排序歸并排序 歸并歸并(

59、Merging) ：是指將兩個或兩個以上的有序：是指將兩個或兩個以上的有序序列合并成一個有序序列。若采用線性表序列合并成一個有序序列。若采用線性表(無論是那種無論是那種存儲結(jié)構(gòu)存儲結(jié)構(gòu))易于實現(xiàn)，其時間復(fù)雜度為易于實現(xiàn)，其時間復(fù)雜度為O(m+n) 。 歸并思想實例歸并思想實例：兩堆撲克牌，都兩堆撲克牌，都已從小到大排好已從小到大排好序序，要將兩堆合并為一堆且要求，要將兩堆合并為一堆且要求從小到大排序從小到大排序。 將兩堆最上面的抽出將兩堆最上面的抽出(設(shè)為設(shè)為C1，C2)比較大小，將比較大小，將小者置于一邊作為新的一堆小者置于一邊作為新的一堆(不妨設(shè)不妨設(shè)C1C2)；再從第；再從第一堆中抽出一

60、張繼續(xù)與一堆中抽出一張繼續(xù)與C2進行比較，將較小的放置進行比較，將較小的放置在新堆的最下面；在新堆的最下面； 重復(fù)上述過程，直到某一堆已抽完，然后將剩下重復(fù)上述過程，直到某一堆已抽完，然后將剩下一堆中的所有牌轉(zhuǎn)移到新堆中。一堆中的所有牌轉(zhuǎn)移到新堆中。1 排序思想排序思想 初始時，將每個記錄看成一個單獨的有序序列，則初始時，將每個記錄看成一個單獨的有序序列，則n個待個待排序記錄就是排序記錄就是n個長度為個長度為1的有序子序列；的有序子序列； 對所有有序子序列進行兩兩歸并，得到對所有有序子序列進行兩兩歸并，得到n/2個長度為個長度為2或或1的有序子序列的有序子序列一趟歸并一趟歸并； 重復(fù)重復(fù) ，直到得到長度為，直到得到長度為n的有序