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

1、第第10章章 內(nèi)部排序內(nèi)部排序 在信息處理過程中，最基本的操作是查找。從查找在信息處理過程中，最基本的操作是查找。從查找來說，效率最高的是折半查找，折半查找的前提是所來說，效率最高的是折半查找，折半查找的前提是所有的數(shù)據(jù)元素有的數(shù)據(jù)元素(記錄記錄)是按關(guān)鍵字有序的。需要將一個(gè)無是按關(guān)鍵字有序的。需要將一個(gè)無序的數(shù)據(jù)文件轉(zhuǎn)變?yōu)橐粋€(gè)有序的數(shù)據(jù)文件。序的數(shù)據(jù)文件轉(zhuǎn)變?yōu)橐粋€(gè)有序的數(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的一個(gè)排列的一個(gè)排列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ù)項(xiàng)的組合。鍵字或若干數(shù)據(jù)項(xiàng)的組合。 Ki是主關(guān)鍵字：排序后得到的結(jié)果是唯一的；是主關(guān)鍵字：排序后得到的結(jié)果是唯一的； Ki是次關(guān)鍵字：排序后得到的結(jié)果是不唯一的。是次關(guān)鍵字：排序后得到的結(jié)果是不唯一的。 排序的穩(wěn)定性排序的穩(wěn)定性 若記錄序列中有若記錄序列中有兩個(gè)或兩個(gè)以上關(guān)鍵字相等兩個(gè)或兩個(gè)以上關(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)點(diǎn)和缺點(diǎn)，分別適合公認(rèn)為最好的。每種算法都有其優(yōu)點(diǎn)和缺點(diǎn)，分別適合不同的數(shù)據(jù)量和硬件配置。不同的數(shù)據(jù)量和硬件配置。 評價(jià)排序算法的標(biāo)準(zhǔn)有：評價(jià)排序算法的標(biāo)準(zhǔn)有：執(zhí)行時(shí)間執(zhí)行時(shí)間和和所需的輔助空所需的輔助空間間，其次是，其次是算法的穩(wěn)定性算法的穩(wěn)定性。 若排序算法所需的輔助空間不依賴問題的規(guī)模若排序算法所需的輔助空間不依賴問題的規(guī)模n，即，即空間復(fù)雜度是空間復(fù)雜度是O(1)

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

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

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

8、具體情況決定是否調(diào)整記錄的存儲(chǔ)位置。否調(diào)整記錄的存儲(chǔ)位置。 比較適合記錄數(shù)較少的情況；而比較適合記錄數(shù)較少的情況；而、則適合記則適合記錄數(shù)較少的情況。錄數(shù)較少的情況。 為討論方便，假設(shè)待排序的記錄是以為討論方便，假設(shè)待排序的記錄是以的情況存儲(chǔ)，的情況存儲(chǔ)，且設(shè)排序是按升序排列的；關(guān)鍵字是一些可直接用比較且設(shè)排序是按升序排列的；關(guān)鍵字是一些可直接用比較運(yùn)算符進(jìn)行比較的類型。運(yùn)算符進(jì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中，得到一個(gè)新的、記錄數(shù)增加中，得到一個(gè)新的、記錄數(shù)增加1的有序表。的有序表。 直到所有的記錄都插入完為止。直到所有的記錄都插入完為止。 設(shè)待排序的記錄順序存放在數(shù)組設(shè)待排序的記錄順序存放在數(shù)組R1n中，在排中，在排序的某一時(shí)刻，將記錄序列分成兩部分：序的某一時(shí)刻，將記錄序列分成兩部分： R1i-1：已排好序的有序部分；：已排好序的有序部分； Rin：未排好序的

11、無序部分。：未排好序的無序部分。 顯然，在剛開始排序時(shí)，顯然，在剛開始排序時(shí)，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 算法實(shí)現(xiàn)算法實(shí)現(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開始時(shí)并不存放任何待排序的記錄，引開始時(shí)并不存放任何待排序的記錄，引入的作用主

13、要有兩個(gè)：入的作用主要有兩個(gè)： 不需要增加輔助空間：不需要增加輔助空間： 保存當(dāng)前待插入的記錄保存當(dāng)前待插入的記錄Ri，Ri會(huì)因?yàn)橛涗浀暮笠贫徽加?；?huì)因?yàn)橛涗浀暮笠贫徽加茫?保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊保證查找插入位置的內(nèi)循環(huán)總可以在超出循環(huán)邊界之前找到一個(gè)等于當(dāng)前記錄的記錄，起界之前找到一個(gè)等于當(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í)行，則一趟排序時(shí)：，算

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

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

16、1, R2 , Ri-1已排好序，則查找插入已排好序，則查找插入位置可以用位置可以用“折半查找折半查找”實(shí)現(xiàn)，則直接插入排序就變成實(shí)現(xiàn)，則直接插入排序就變成為折半插入排序。為折半插入排序。 算法實(shí)現(xiàn)算法實(shí)現(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)位置 */ 從時(shí)間上比較，折半插入排序僅僅減少了關(guān)鍵字的比從時(shí)間上比較，折半插入排序僅僅減少了關(guān)鍵字的比較次數(shù)，卻沒有減少記錄的移動(dòng)次數(shù)，故時(shí)間復(fù)雜度仍較次數(shù)，卻沒有減少記錄的移動(dòng)次數(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-路插入排序路插入排序 是對折半插入排序的改進(jìn)是對折半插入排序的改進(jìn)，以減少排序

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

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

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

22、始化：下標(biāo)值為：下標(biāo)值為0的分量作為表頭結(jié)點(diǎn)的分量作為表頭結(jié)點(diǎn)，關(guān)鍵字取為最大值，關(guān)鍵字取為最大值，各分量的指針值為空；各分量的指針值為空； 將靜態(tài)鏈表中將靜態(tài)鏈表中數(shù)組下標(biāo)值為數(shù)組下標(biāo)值為1的分量的分量(結(jié)點(diǎn)結(jié)點(diǎn))與表頭結(jié)點(diǎn)構(gòu)成與表頭結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)鏈表；一個(gè)循環(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次指針值次指針值以代替移動(dòng)記錄，而關(guān)鍵字的比較次數(shù)相同，故時(shí)間復(fù)以代替移動(dòng)記錄，而關(guān)鍵字的比較次數(shù)相同，故時(shí)間復(fù)雜度為雜度為O(n2)。 表插入排序得到一個(gè)有序鏈表，對其可以方便地進(jìn)行表插入排序得到一個(gè)有序鏈表，對其可以方便地進(jìn)行順序查找，但不能實(shí)現(xiàn)隨即查找。根據(jù)需要，可以對記順序查找，但不能實(shí)現(xiàn)隨即查找。根據(jù)需要，可以對記錄進(jìn)行重排，記錄重排詳見錄進(jìn)行重排，記錄重排詳見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 排序思想排序思想 先取一個(gè)正整數(shù)先取一個(gè)正整數(shù)d1(d1n)作為第一個(gè)增量，將全部作為第一個(gè)增量，將全部n個(gè)記錄個(gè)記錄分成分成d1組，把所有相隔組，把所有相隔d1的記錄放在一組中，即對于每個(gè)的記錄放在一組中，即對于每個(gè)k(k=1, 2, d1)，Rk, Rd1+k,

26、 R2d1+k , 分在同一組中，在各組內(nèi)進(jìn)分在同一組中，在各組內(nèi)進(jìn)行直接插入排序行直接插入排序。這樣一次分組和排序過程稱為一趟這樣一次分組和排序過程稱為一趟希爾排序希爾排序； 取新的增量取新的增量d2d1，重復(fù)，重復(fù)的分組和排序操作；直至所取的的分組和排序操作；直至所取的增量增量di=1為止，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹篂橹梗此杏涗浄胚M(jìn)一個(gè)組中排序?yàn)橹埂? 排序示排序示例例 設(shè)有設(shè)有10個(gè)待排序的記錄，關(guān)鍵字分別為個(gè)待排序的記錄，關(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 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 先給出一趟希爾排序的算法，類似直接插入排序。先給出一趟希爾排序的算法，類似直接插入排序。void shell_pass(Sqlist *L, int d) /* 對順序表對順序表L進(jìn)行一趟希爾排

28、序進(jìn)行一趟希爾排序, 增量為增量為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進(jìn)行希爾排序。進(jìn)行希爾排序。void shell_sort(Sqlist *L, int dk, int t) /* 按增量序列按增量序列dk0 t-1,對順序表對順序表L進(jìn)行希爾排序進(jìn)行希爾排序 */ int m ;fo

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

30、錄進(jìn)行的進(jìn)行的，因此，若待排序的記錄有，因此，若待排序的記錄有n個(gè)個(gè)，則要經(jīng)過，則要經(jīng)過n-1趟趟冒泡排序才能使所有的記錄有序冒泡排序才能使所有的記錄有序。2 排序示排序示例例 設(shè)有設(shè)有9個(gè)待排序的記錄，關(guān)鍵字分別為個(gè)待排序的記錄，關(guān)鍵字分別為23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的過程如圖，冒泡排序的過程如圖10-6所示所示。3 算法實(shí)現(xiàn)算法實(shí)現(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 ;故時(shí)間復(fù)雜度故時(shí)間復(fù)雜度：T(n)=O(n)空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)4 算法分析算法分析時(shí)間復(fù)雜度時(shí)間復(fù)雜度 最好情況最好情況(正序正序)：比較次數(shù)：比較次數(shù)：n-1；移動(dòng)次數(shù)

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

34、記錄序列中任取，在記錄序列中任取一個(gè)記錄一個(gè)記錄(一般取一般取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分分割成兩個(gè)子序列，稱為一趟快速排序割成兩個(gè)子序列，稱為一趟快速排序。3 一趟快速排序方法一趟快速排序方法 從序列的兩端交替掃描各個(gè)記錄，將從序列的兩端交替掃描各個(gè)記錄，將關(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個(gè)和最后一個(gè)記錄個(gè)和最后一個(gè)記錄的位置。的位置。 設(shè)兩個(gè)變量設(shè)兩個(gè)變量i，j，初始時(shí)令，初始時(shí)令i=low，j=high，以以Rlow.key作為基準(zhǔn)作為基準(zhǔn)(將將Rlow保存在保存在R0中中) 。 從從j所指位置向前搜索：將所指位置向前搜索：將R0.key與與Rj.key

36、進(jìn)行比較：進(jìn)行比較： 若若R0.keyRj.key ：令：令j=j-1，然后繼續(xù)進(jìn)行比，然后繼續(xù)進(jìn)行比較，較， 直到直到i=j或或R0.keyRj.key為止；為止； 若若R0.keyRj.key ：RjRi，騰空騰空Rj的位的位置置， 且令且令i=i+1； 從從i所指位置起向后搜索：將所指位置起向后搜索：將R0.key與與Ri.key進(jìn)行比較：進(jìn)行比較： 若若R0.keyRi.key ：令：令i=i+1，然后繼續(xù)進(jìn)行比，然后繼續(xù)進(jìn)行比較，較， 直到直到i=j或或R0.keyRi.key為止；為止； 若若R0.keyR0=L-Ri ; /* R0作為臨時(shí)單元和哨兵作為臨時(shí)單元和哨兵 */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時(shí)退出掃描時(shí)退出掃描 */L-Ri=L-R0 ; return(i) ; 快速排序算法實(shí)現(xiàn)快速排序算法實(shí)現(xiàn) 當(dāng)進(jìn)行一趟快速排序后，采用同樣方法分別對兩個(gè)當(dāng)進(jìn)行一趟快速排序后，采用同樣方法分別對兩個(gè)子序列快速排序，直到子序列記錄個(gè)為子序列快速排序，直到子序列記錄個(gè)為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); /* 序列分為兩部分后分別對每個(gè)子序列排序序列分為兩部分后分別對每個(gè)子序列排序 */ 非遞歸算法非遞歸算法# 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 ; /* 第二個(gè)子序列的上第二個(gè)子序列的上,下界分別入棧下界分別入棧 */ high=k-1 ; if (top!=0) low=stacktop- ; high=stacktop- ; while (top!=0&low1時(shí)，用時(shí)，用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個(gè)記錄的排序時(shí)間是一個(gè)常數(shù)，個(gè)記錄的排序時(shí)間是一個(gè)常數(shù)， 快速排序的平均時(shí)間復(fù)雜度是快速排序的平均時(shí)間復(fù)雜度是：T(n)=O(n2n) 從所需要的附加空間來看，快速排序算法是遞歸調(diào)從所需要的附加空間來看，快速排序算法是遞歸調(diào)用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)

41、每次劃分比較均勻用，系統(tǒng)內(nèi)用堆棧保存遞歸參數(shù)，當(dāng)每次劃分比較均勻時(shí)，棧的最大深度為時(shí)，棧的最大深度為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)鍵字最小的記錄表，然后與待排序的記錄序列中的第一個(gè)記錄進(jìn)行交換，直到后與待排序的記錄序列中的第一個(gè)記錄進(jìn)行交換，直到整個(gè)記錄序列有序?yàn)橹?。整個(gè)記錄序列

42、有序?yàn)橹埂?10.4.1 簡單選擇排序簡單選擇排序 簡單選擇排序簡單選擇排序(Simple Selection Sort ，又稱為，又稱為直接選擇排序直接選擇排序)的基本操作是：通過的基本操作是：通過n-i次關(guān)鍵字間的比次關(guān)鍵字間的比較，從較，從n-i+1個(gè)記錄中選取關(guān)鍵字最小的記錄，然后和第個(gè)記錄中選取關(guān)鍵字最小的記錄，然后和第i個(gè)記錄進(jìn)行交換，個(gè)記錄進(jìn)行交換，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 算法實(shí)現(xiàn)算法實(shí)現(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 算法分析算法分析 整個(gè)算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對整個(gè)算法是二重循環(huán)：外循環(huán)控制排序的趟數(shù)，對n個(gè)記錄進(jìn)行排序的趟數(shù)為個(gè)記錄進(jìn)行排序的趟數(shù)為n-1趟；內(nèi)循環(huán)控制每一趟的趟；內(nèi)循環(huán)控制每一趟的排序。排序。 進(jìn)行第進(jìn)行第i趟排序時(shí)，關(guān)鍵字的比較次數(shù)為趟排序時(shí)，關(guān)鍵字的比較次數(shù)為n-i，則：，則：比較次數(shù)：比較次數(shù)： (n-i)=n-1i=1n(n-1)2 時(shí)間復(fù)雜

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

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

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

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

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

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

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

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

53、整算法實(shí)現(xiàn)堆調(diào)整算法實(shí)現(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 ; /* 計(jì)算計(jì)算H-Rj的左孩子的位置的左孩子的位置 */H-R0=H-Rj ; /* 臨時(shí)保存臨時(shí)保存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 堆的建立堆的建立 利用篩選算法，可以將任意無序的記錄序列建成一利用篩選算法，可以將任意無序的記錄序列建成一個(gè)堆，設(shè)個(gè)堆，設(shè)R1,R2, ,Rn是待排序的記錄序列。是待排序的記錄序列。 將二叉樹的將二叉樹的每棵子樹都篩選成為堆每棵子樹都篩選成為堆。只有根結(jié)點(diǎn)的。只有根結(jié)點(diǎn)的樹是堆。第樹是堆。第 n/2 個(gè)結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都沒有子樹，個(gè)結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都沒有子樹，即以第即以第n/2個(gè)結(jié)點(diǎn)之后的結(jié)點(diǎn)為根的子樹都是堆。個(gè)結(jié)點(diǎn)之后的結(jié)點(diǎn)為根的子樹

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

56、堆的根結(jié)點(diǎn)是關(guān)鍵字最小的記錄，輸出根結(jié)點(diǎn)后，是以序列的最后一個(gè)記錄作為根結(jié)點(diǎn)，而原來堆的左、是以序列的最后一個(gè)記錄作為根結(jié)點(diǎn)，而原來堆的左、右子樹都是堆，則右子樹都是堆，則進(jìn)行一次篩選進(jìn)行一次篩選就可以成為堆。就可以成為堆。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 ; /* 堆頂與最后一個(gè)交換堆頂與最后一個(gè)交換

57、 */Heap_adjust(H, 1, j-1) ; 7 算法分析算法分析 主要過程：初始建堆和重新調(diào)整成堆。設(shè)記錄數(shù)為主要過程：初始建堆和重新調(diào)整成堆。設(shè)記錄數(shù)為n，所對應(yīng)的完全二叉樹深度為所對應(yīng)的完全二叉樹深度為h 。 初始建堆初始建堆：每個(gè)非葉子結(jié)點(diǎn)都要從上到下做：每個(gè)非葉子結(jié)點(diǎn)都要從上到下做“篩篩選選” 。第。第i層結(jié)點(diǎn)數(shù)層結(jié)點(diǎn)數(shù)2i-1，結(jié)點(diǎn)下移的最大深度是，結(jié)點(diǎn)下移的最大深度是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é)點(diǎn)：每次篩選要將根結(jié)點(diǎn)“下沉下沉”到一個(gè)合到一個(gè)合適位置。第適位置。第i次篩選時(shí)：堆中元素個(gè)數(shù)為次篩選時(shí)：堆中元素個(gè)數(shù)為n-i+1；堆的；堆的深度是深度是2(n-i+1)+1，則進(jìn)行，則進(jìn)行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)；而附加空間就是交換時(shí)所用的臨時(shí)空間，故空間復(fù)雜而附加空間就是交換時(shí)所用的臨時(shí)空間，故空間復(fù)雜度為：度為： S(n)=O(1) 。10. 5 歸并排序歸并排序 歸并歸并(

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

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