第10章 內部排序.ppt

1、第10章 內部排序,在信息處理過程中，最基本的操作是查找。從查找來說，效率最高的是折半查找，折半查找的前提是所有的數(shù)據(jù)元素(記錄)是按關鍵字有序的。需要將一個無序的數(shù)據(jù)文件轉變?yōu)橐粋€有序的數(shù)據(jù)文件。 將任一文件中的記錄通過某種方法整理成為按(記錄)關鍵字有序排列的處理過程稱為排序。 排序是數(shù)據(jù)處理中一種最常用的操作。,10.1 排序的基本概念, 排序(Sorting) 排序是將一批(組)任意次序的記錄重新排列成按關鍵字有序的記錄序列的過程，其定義為： 給定一組記錄序列：R1 , R2 , Rn，其相應的關鍵字序列是K1 , K2 , Kn 。確定1, 2, n的一個排列p1 , p2 , pn

2、，使其相應的關鍵字滿足如下非遞減(或非遞增)關系： Kp1Kp2 Kpn的序列Kp1 ,Kp2 , ,Kpn ，這種操作稱為排序。 關鍵字Ki可以是記錄Ri的主關鍵字，也可以是次關鍵字或若干數(shù)據(jù)項的組合。, Ki是主關鍵字：排序后得到的結果是唯一的； Ki是次關鍵字：排序后得到的結果是不唯一的。 排序的穩(wěn)定性 若記錄序列中有兩個或兩個以上關鍵字相等的記錄： Ki =Kj(ij，i, j=1, 2, n)，且在排序前Ri先于Rj(ij)，排序后的記錄序列仍然是Ri先于Rj，稱排序方法是穩(wěn)定的，否則是不穩(wěn)定的。 排序算法有許多，但就全面性能而言，還沒有一種公認為最好的。每種算法都有其優(yōu)點和缺點，分

3、別適合不同的數(shù)據(jù)量和硬件配置。 評價排序算法的標準有：執(zhí)行時間和所需的輔助空間，其次是算法的穩(wěn)定性。,若排序算法所需的輔助空間不依賴問題的規(guī)模n，即空間復雜度是O(1) ，則稱排序方法是就地排序，否則是非就地排序。 排序的分類 待排序的記錄數(shù)量不同，排序過程中涉及的存儲器的不同，有不同的排序分類。 待排序的記錄數(shù)不太多：所有的記錄都能存放在內存中進行排序，稱為內部排序； 待排序的記錄數(shù)太多：所有的記錄不可能存放在內存中， 排序過程中必須在內、外存之間進行數(shù)據(jù)交換，這樣的排序稱為外部排序。, 內部排序的基本操作 對內部排序地而言，其基本操作有兩種： 比較兩個關鍵字的大??； 存儲位置的移動：從一個

4、位置移到另一個位置。 第一種操作是必不可少的；而第二種操作卻不是必須的，取決于記錄的存儲方式，具體情況是： 記錄存儲在一組連續(xù)地址的存儲空間：記錄之間的邏輯順序關系是通過其物理存儲位置的相鄰來體現(xiàn)，記錄的移動是必不可少的； 記錄采用鏈式存儲方式：記錄之間的邏輯順序關系是通過結點中的指針來體現(xiàn)，排序過程僅需修改結點的指針，而不需要移動記錄；, 記錄存儲在一組連續(xù)地址的存儲空間：構造另一個輔助表來保存各個記錄的存放地址(指針) ：排序過程不需要移動記錄，而僅需修改輔助表中的指針，排序后視具體情況決定是否調整記錄的存儲位置。 比較適合記錄數(shù)較少的情況；而、則適合記錄數(shù)較少的情況。 為討論方便，假設待

5、排序的記錄是以的情況存儲，且設排序是按升序排列的；關鍵字是一些可直接用比較運算符進行比較的類型。,待排序的記錄類型的定義如下： #define MAX_SIZE 100 Typedef int KeyType ; typedef struct RecType KeyType key ; /* 關鍵字碼 */ infoType otherinfo ; /* 其他域 */ RecType ; typedef struct Sqlist RecType RMAX_SIZE ; int length ; Sqlist ;,10.2 插入排序,采用的是以 “玩橋牌者”的方法為基礎的。即在考察記錄Ri之前

6、，設以前的所有記錄R1, R2 ,., Ri-1已排好序，然后將Ri插入到已排好序的諸記錄的適當位置。 最基本的插入排序是直接插入排序(Straight Insertion Sort) 。,10.2.1 直接插入排序,1 排序思想 將待排序的記錄Ri，插入到已排好序的記錄表R1, R2 ,., Ri-1中，得到一個新的、記錄數(shù)增加1的有序表。 直到所有的記錄都插入完為止。 設待排序的記錄順序存放在數(shù)組R1n中，在排序的某一時刻，將記錄序列分成兩部分： R1i-1：已排好序的有序部分； Rin：未排好序的無序部分。 顯然，在剛開始排序時，R1是已經(jīng)排好序的。,例：設有關鍵字序列為：7, 4, -

7、2, 19, 13, 6，直接插入排序的過程如下圖10-1所示：,2 算法實現(xiàn) void straight_insert_sort(Sqlist *L) int i, j ; for (i=2; ilength; i+) L-R0=L-Ri; j=i-1; /* 設置哨兵 */ while( LT(L-R0.key, L-Rj.key) ) L-Rj+1=L-Rj; j-; /* 查找插入位置 */ L-Rj+1=L-R0; /* 插入到相應位置 */ ,3 算法說明 算法中的R0開始時并不存放任何待排序的記錄，引入的作用主要有兩個： 不需要增加輔助空間： 保存當前待插入的記錄Ri，Ri會因為

8、記錄的后移而被占用； 保證查找插入位置的內循環(huán)總可以在超出循環(huán)邊界之前找到一個等于當前記錄的記錄，起“哨兵監(jiān)視”作用，避免在內循環(huán)中每次都要判斷j是否越界。,4 算法分析 最好情況：若待排序記錄按關鍵字從小到大排列(正序)，算法中的內循環(huán)無須執(zhí)行，則一趟排序時：關鍵字比較次數(shù)1次，記錄移動次數(shù)2次(RiR0, R0Rj+1)。 則整個排序的關鍵字比較次數(shù)和記錄移動次數(shù)分別是：, 最壞情況：若待排序記錄按關鍵字從大到小排列(逆序)，則一趟排序時：算法中的內循環(huán)體執(zhí)行i-1，關鍵字比較次數(shù)i次，記錄移動次數(shù)i+1。 則就整個排序而言：,一般地，認為待排序的記錄可能出現(xiàn)的各種排列的概率相同，則取以上

9、兩種情況的平均值，作為排序的關鍵字比較次數(shù)和記錄移動次數(shù)，約為n2/4，則復雜度為O(n2) 。,10.2.2 其它插入排序,1 折半插入排序 當將待排序的記錄Ri 插入到已排好序的記錄子表R1i-1中時，由于R1, R2 , Ri-1已排好序，則查找插入位置可以用“折半查找”實現(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; /* 設置哨兵 */,low=1 ; high=i-1 ; while (l

10、owR0.key, L-Rmid.key) ) high=mid-1 ; else low=mid+1 ; /* 查找插入位置 */ for (j=i-1; j=high+1; j-) L-Rj+1=L-Rj; L-Rhigh+1=L-R0; /* 插入到相應位置 */ ,從時間上比較，折半插入排序僅僅減少了關鍵字的比較次數(shù)，卻沒有減少記錄的移動次數(shù)，故時間復雜度仍然為O(n2) 。 排序示例 設有一組關鍵字30, 13, 70, 85, 39, 42, 6, 20，采用折半插入排序方法排序的過程如圖10-2所示：,2 2-路插入排序 是對折半插入排序的改進，以減少排序過程中移動記錄的次數(shù)。附

11、加n個記錄的輔助空間，方法是： 另設一個和L-R同類型的數(shù)組d，L-R1賦給d1，將d1看成是排好序的序列中中間位置的記錄； 分別將L-R 中的第i個記錄依次插入到d1之前或之后的有序序列中，具體方法： L-Ri.keyRi插入到d1之前的有序表中； L-Ri.keyd1.key： L-Ri插入到d1之后的有序表中；,關鍵點：實現(xiàn)時將向量d看成是循環(huán)向量，并設兩個指針first和final分別指示排序過程中得到的有序序列中的第一個和最后一個記錄。 排序示例 設有初始關鍵字集合49, 38, 65, 13, 97, 27, 76 ，采用2-路插入排序的過程如右圖10-3所示。 在2-路插入排序中

12、，移動記錄的次數(shù)約為n2/8 。但當L-R1是待排序記錄中關鍵字最大或最小的記錄時，2-路插入排序就完全失去了優(yōu)越性。,3 表插入排序 前面的插入排序不可避免地要移動記錄，若不移動記錄就需要改變數(shù)據(jù)結構。附加n個記錄的輔助空間，記錄類型修改為：,typedef struct RecNode KeyType key ; infotype otherinfo ; int *next; RecNode ; 初始化：下標值為0的分量作為表頭結點，關鍵字取為最大值，各分量的指針值為空； 將靜態(tài)鏈表中數(shù)組下標值為1的分量(結點)與表頭結點構成一個循環(huán)鏈表； i=2 ，將分量Ri按關鍵字遞減插入到循環(huán)鏈表；

13、 增加i ，重復，直到全部分量插入到循環(huán)鏈表。,例：設有關鍵字集合49, 38, 65, 97, 76, 13, 27, 49 ，采用表插入排序的過程如下圖10-4所示。,和直接插入排序相比，不同的是修改2n次指針值以代替移動記錄，而關鍵字的比較次數(shù)相同，故時間復雜度為O(n2)。 表插入排序得到一個有序鏈表，對其可以方便地進行順序查找，但不能實現(xiàn)隨即查找。根據(jù)需要，可以對記錄進行重排，記錄重排詳見P268。,10.2.3 希爾排序,希爾排序(Shell Sort，又稱縮小增量法)是一種分組插入排序方法。 1 排序思想 先取一個正整數(shù)d1(d1n)作為第一個增量，將全部n個記錄分成d1組，把所

14、有相隔d1的記錄放在一組中，即對于每個k(k=1, 2, d1)，Rk, Rd1+k, R2d1+k , 分在同一組中，在各組內進行直接插入排序。這樣一次分組和排序過程稱為一趟希爾排序； 取新的增量d2d1，重復的分組和排序操作；直至所取的增量di=1為止，即所有記錄放進一個組中排序為止。,2 排序示例 設有10個待排序的記錄，關鍵字分別為9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希爾排序的過程如圖10-5所示。,3 算法實現(xiàn) 先給出一趟希爾排序的算法，類似直接插入排序。 void shell_pass(Sqlist *L, int d) /*

15、 對順序表L進行一趟希爾排序, 增量為d */ int j, k ; for (j=d+1; jlength; j+) L-R0=L-Rj ; /* 設置監(jiān)視哨兵 */ k=j-d ; while (k0 ,然后在根據(jù)增量數(shù)組dk進行希爾排序。 void shell_sort(Sqlist *L, int dk, int t) /* 按增量序列dk0 t-1,對順序表L進行希爾排序 */ int m ; for (m=0; m=t; m+) shll_pass(L, dkm) ; 希爾排序的分析比較復雜，涉及一些數(shù)學上的問題，其時間是所取的“增量”序列的函數(shù)。 希爾排序特點 子序列的構成不是簡

16、單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列。,希爾排序可提高排序速度，原因是： 分組后n值減小，n更小，而T(n)=O(n),所以T(n)從總體上看是減小了； 關鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序。 增量序列取法 無除1以外的公因子； 最后一個增量值必須為1。,10.3 快速排序,是一類基于交換的排序，系統(tǒng)地交換反序的記錄的偶對，直到不再有這樣一來的偶對為止。其中最基本的是冒泡排序(Bubble Sort)。,10.3.1 冒泡排序,1 排序思想 依次比較相鄰的兩個記錄的關鍵字，若兩個記錄是反序的(即前一個記錄的關鍵字大于后前一個記錄的關

17、鍵字)，則進行交換，直到?jīng)]有反序的記錄為止。 首先將L-R1與L-R2的關鍵字進行比較，若為反序(L-R1的關鍵字大于L-R2的關鍵字)，則交換兩個記錄；然后比較L-R2與L-R3的關鍵字，依此類推，直到L-Rn-1與L-Rn的關鍵字比較后為止，稱為一趟冒泡排序，L-Rn為關鍵字最大的記錄。, 然后進行第二趟冒泡排序，對前n-1個記錄進行同樣的操作。 一般地，第i趟冒泡排序是對L-R1 n-i+1中的記錄進行的，因此，若待排序的記錄有n個，則要經(jīng)過n-1趟冒泡排序才能使所有的記錄有序。 2 排序示例 設有9個待排序的記錄，關鍵字分別為23, 38, 22, 45, 23, 67, 31, 15

18、, 41，冒泡排序的過程如圖10-6所示。 3 算法實現(xiàn) #define FALSE 0 #define TRUE 1,void Bubble_Sort(Sqlist *L) int j ,k , flag ; 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 ;

19、,故時間復雜度：T(n)=O(n) 空間復雜度：S(n)=O(1),4 算法分析 時間復雜度 最好情況(正序)：比較次數(shù)：n-1；移動次數(shù)：0； 最壞情況(逆序)：,10.3.2 快速排序,1 排序思想 通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，再分別對這兩部分記錄進行下一趟排序，以達到整個序列有序。 2 排序過程 設待排序的記錄序列是Rst ，在記錄序列中任取一個記錄(一般取Rs)作為參照(又稱為基準或樞軸)，以Rs.key為基準重新排列其余的所有記錄，方法是：, 所有關鍵字比基準小的放Rs之前； 所有關鍵字比基準大的放Rs之后。 以Rs

20、.key最后所在位置i作為分界，將序列Rst分割成兩個子序列，稱為一趟快速排序。 3 一趟快速排序方法 從序列的兩端交替掃描各個記錄，將關鍵字小于基準關鍵字的記錄依次放置到序列的前邊；而將關鍵字大于基準關鍵字的記錄從序列的最后端起，依次放置到序列的后邊，直到掃描完所有的記錄。 設置指針low，high，初值為第1個和最后一個記錄的位置。,設兩個變量i，j，初始時令i=low，j=high，以Rlow.key作為基準(將Rlow保存在R0中) 。 從j所指位置向前搜索：將R0.key與Rj.key進行比較： 若R0.keyRj.key ：令j=j-1，然后繼續(xù)進行比較， 直到i=j或R0.key

21、Rj.key為止； 若R0.keyRj.key ：RjRi，騰空Rj的位置， 且令i=i+1； 從i所指位置起向后搜索：將R0.key與Ri.key進行比較： 若R0.keyRi.key ：令i=i+1，然后繼續(xù)進行比較， 直到i=j或R0.keyRi.key為止；, 若R0.keyRi.key ：RiRj，騰空Ri的位置， 且令j=j-1； 重復、，直至i=j為止，i就是R0(基準)所應放置的位置。 4 一趟排序示例 設有6個待排序的記錄，關鍵字分別為29, 38, 22, 45, 23, 67，一趟快速排序的過程如圖10-7所示。 5 算法實現(xiàn) 一趟快速排序算法的實現(xiàn) int quick_

22、one_pass(Sqlist *L , int low, int high) int i=low, j=high ;,L-R0=L-Ri ; /* R0作為臨時單元和哨兵 */ do while (LQ(L-R0.key, L-Rj.key) , 快速排序算法實現(xiàn) 當進行一趟快速排序后，采用同樣方法分別對兩個子序列快速排序，直到子序列記錄個為1為止。 遞歸算法 void quick_Sort(Sqlist *L , int low, int high) int k ; if (lowhigh) k=quick_one_pass(L, low, high); quick_Sort(L, low

23、, k-1); quick_Sort(L, k+1, high); /* 序列分為兩部分后分別對每個子序列排序 */ , 非遞歸算法 # define MAX_STACK 100 void quick_Sort(Sqlist *L , int low, int high) int k , stackMAX_STACK , top=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=

24、stacktop- ; high=stacktop- ; ,while (top!=0 6 算法分析 快速排序的主要時間是花費在劃分上，對長度為k的記錄序列進行劃分時關鍵字的比較次數(shù)是k-1 。設長度為n的記錄序列進行排序的比較次數(shù)為C(n)，則C(n)=n-1+C(k)+C(n-k-1) 。 最好情況：每次劃分得到的子序列大致相等，則 C(n)n+2C(n/2)+C(n-k-1) n+2n/2+ 2C(n/2)/2) 2n+4C(n/4) hn+2hC(n/2h) ，當n/2h=1時排序結束。,即C(n)n2n+nC(1) ，C(1)看成常數(shù)因子， 即C(n)O(n2n) ； 最壞情況：每次

25、劃分得到的子序列中有一個為空，另一個子序列的長度為n-1。即每次劃分所選擇的基準是當前待排序序列中的最小(或最大)關鍵字。, 一般情況： 對n個記錄進行快速排序所需的時間T(n)組成是： 對n個記錄進行一趟劃分所需的時間是：nC ，C是常數(shù)； 對所得到的兩個子序列進行快速排序的時間： Tavg(n)=C(n)+Tavg(k-1)+Tavg(n-k) ,若記錄是隨機排列的，k取值在1n之間的概率相同，則：,當n1時，用n-1代替中的n，得到：, nTavg(n)-(n-1)Tavg(n-1)=(2n-1)C+2Tavg(n-1) ，即 Tavg(n)=(n+1)/nTavg(n-1)+(2n-1

26、)/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 ,只有1個記錄的排序時間是一個常數(shù)， 快速排序的平均時間復雜度是：T(n)=O(n2n) 從所需要的附加空間來看，快速排序算法是遞歸調用，系統(tǒng)內用堆棧保存遞歸參數(shù)，當每次劃分比較均勻時，棧的最大深度為2n+1 。 快速排序的空間復雜度是：S(n)=O(2n) 從排序的穩(wěn)定性來看，快速排序是不穩(wěn)定的。,10. 4 選擇排序,選擇排序(Selection Sort)的基本思想是：每次從當前待排序的記錄中選取關

27、鍵字最小的記錄表，然后與待排序的記錄序列中的第一個記錄進行交換，直到整個記錄序列有序為止。,10.4.1 簡單選擇排序,簡單選擇排序(Simple Selection Sort ，又稱為直接選擇排序)的基本操作是：通過n-i次關鍵字間的比較，從n-i+1個記錄中選取關鍵字最小的記錄，然后和第i個記錄進行交換，i=1, 2, n-1 。 1 排序示例 例：設有關鍵字序列為：7, 4, -2, 19, 13, 6，直接選擇排序的過程如下圖10-8所示。,2 算法實現(xiàn) void simple_selection_sort(Sqlist *L) int m, n , k; for (m=1; mlen

28、gth; m+) k=m ; for (n=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ù)，對n個記錄進行排序的趟數(shù)為n-1趟；內循環(huán)控制每一趟的排序。 進行第i趟排序時，關鍵字的比較次數(shù)為n-i，則：, 時間復雜度是：T(n)=O(n2) 空間復雜度是：S(n)=O(1) 從排序的穩(wěn)定性來看，直接選擇排序是不穩(wěn)定的。,10.4.2 樹形選擇排序,借助“淘汰賽”中的對壘就

29、很容易理解樹形選擇排序的思想。 首先對n個記錄的關鍵字兩兩進行比較，選取n/2個較小者；然后這n/2個較小者兩兩進行比較，選取n/4個較小者 如此重復，直到只剩1個關鍵字為止。 該過程可用一棵有n個葉子結點的完全二叉樹表示，如圖10-9所示。 每個枝結點的關鍵字都等于其左、右孩子結點中較小的關鍵字，根結點的關鍵字就是最小的關鍵字。,輸出最小關鍵字后，根據(jù)關系的可傳遞性，欲選取次小關鍵字，只需將葉子結點中的最小關鍵字改為“最大值” ，然后重復上述步驟即可。 含有n個葉子結點的完全二叉樹的深度為2n+1，則總的時間復雜度為O(n2n) 。,10.4.3 堆排序,1 堆的定義 是n個元素的序列H=k

30、1, k2 , kn ，滿足：,由堆的定義知，堆是一棵以k1為根的完全二叉樹。若對該二叉樹的結點進行編號(從上到下，從左到右)，得到的序列就是將二叉樹的結點以順序結構存放，堆的結構正好和該序列結構完全一致。,2 堆的性質 堆是一棵采用順序存儲結構的完全二叉樹， k1是根結點； 堆的根結點是關鍵字序列中的最小(或最大)值，分別稱為小(或大)根堆； 從根結點到每一葉子結點路徑上的元素組成的序列都是按元素值(或關鍵字值)非遞減(或非遞增)的； 堆中的任一子樹也是堆。 利用堆頂記錄的關鍵字值最小(或最大)的性質，從當前待排序的記錄中依次選取關鍵字最小(或最大)的記錄，就可以實現(xiàn)對數(shù)據(jù)記錄的排序，這種排

31、序方法稱為堆排序。,3 堆排序思想 對一組待排序的記錄，按堆的定義建立堆； 將堆頂記錄和最后一個記錄交換位置，則前n-1個記錄是無序的，而最后一個記錄是有序的； 堆頂記錄被交換后，前n-1個記錄不再是堆，需將前n-1個待排序記錄重新組織成為一個堆，然后將堆頂記錄和倒數(shù)第二個記錄交換位置，即將整個序列中次小關鍵字值的記錄調整(排除)出無序區(qū)； 重復上述步驟，直到全部記錄排好序為止。 結論：排序過程中，若采用小根堆，排序后得到的是非遞減序列；若采用大根堆，排序后得到的是非遞增序列。,堆排序的關鍵 如何由一個無序序列建成一個堆？ 如何在輸出堆頂元素之后，調整剩余元素，使之成為一個新的堆？ 4 堆的調

32、整篩選 堆的調整思想 輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換；重復上述操作，直到是葉子結點或其關鍵字值小于等于左、右子樹的關鍵字的值，將得到新的堆。稱這個從堆頂至葉子的調整過程為“篩選”，如圖10-10所示。,注意：篩選過程中，根結點的左、右子樹都是堆，因此，篩選是從根結點到某個葉子結點的一次調整過程。, 堆調整算法實現(xiàn) void Heap_adjust(Sqlist *H, int s, int m) /* H-Rsm中記錄關鍵字除H-Rs.key均滿足堆定義 */ /* 調整H-Rs的位置使之成為小根堆 */ int

33、j=s, k=2*j ; /* 計算H-Rj的左孩子的位置 */ H-R0=H-Rj ; /* 臨時保存H-Rj */ for (k=2*j; kRk+1.key, H-Rk.key) k+ ; /* 選擇左、右孩子中關鍵字的最小者 */ if ( LT(H-Rk.key, H-R0.key) ) H-Rj=H-Rk ; j=k ; k=2*j else break ; ,H-Rj=H-R0 ; 5 堆的建立 利用篩選算法，可以將任意無序的記錄序列建成一個堆，設R1,R2, ,Rn是待排序的記錄序列。 將二叉樹的每棵子樹都篩選成為堆。只有根結點的樹是堆。第n/2個結點之后的所有結點都沒有子樹，

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

35、-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 ; /* 堆頂與最后一個交換 */ Heap_adjust(H, 1, j-1) ; 7 算法分析 主要過程：初始建堆和重新調整成堆。設記錄數(shù)為n，所對應的完全二叉樹深度為h 。 初始建堆：每個非葉子結點都要從上到下做“篩選” 。第i層結點數(shù)2i-1，結點下移的最大深度是h-i，而每下移一層要比較2次，則比較次數(shù)C1(n)為：, h=2n+1， C1(

36、n)4(n-2n-1) 篩選調整：每次篩選要將根結點“下沉”到一個合適位置。第i次篩選時：堆中元素個數(shù)為n-i+1；堆的深度是2(n-i+1)+1，則進行n-1次“篩選”的比較次數(shù)C2(n)為：, C2(n)2n2n 堆排序的比較次數(shù)的數(shù)量級為： T(n)=O(n2n)；而附加空間就是交換時所用的臨時空間，故空間復雜度為： S(n)=O(1) 。,10. 5 歸并排序,歸并(Merging) ：是指將兩個或兩個以上的有序序列合并成一個有序序列。若采用線性表(無論是那種存儲結構)易于實現(xiàn)，其時間復雜度為O(m+n) 。 歸并思想實例：兩堆撲克牌，都已從小到大排好序，要將兩堆合并為一堆且要求從小到

37、大排序。 將兩堆最上面的抽出(設為C1，C2)比較大小，將小者置于一邊作為新的一堆(不妨設C1C2)；再從第一堆中抽出一張繼續(xù)與C2進行比較，將較小的放置在新堆的最下面； 重復上述過程，直到某一堆已抽完，然后將剩下一堆中的所有牌轉移到新堆中。,1 排序思想 初始時，將每個記錄看成一個單獨的有序序列，則n個待排序記錄就是n個長度為1的有序子序列； 對所有有序子序列進行兩兩歸并，得到n/2個長度為2或1的有序子序列一趟歸并； 重復 ，直到得到長度為n的有序序列為止。 上述排序過程中，子序列總是兩兩歸并，稱為2-路歸并排序。其核心是如何將相鄰的兩個子序列歸并成一個子序列。設相鄰的兩個子序列分別為：

38、Rk, Rk+1, , Rm和Rm+1, Rm+2, Rh，將它們歸并為一個有序的子序列： DRl, DRl+1, , DRm, DRm+1, , DRh ,例：設有9個待排序的記錄，關鍵字分別為23, 38, 22, 45, 23, 67, 31, 15, 41，歸并排序的過程如圖10-11所示。,歸并的算法 void Merge(RecType R, RecType DR, int k, int m, int h) int p, q, n ; p=n=k, q=m+1 ; while (p=m) ,2 一趟歸并排序 一趟歸并排序都是從前到后，依次將相鄰的兩個有序子序列歸并為一個，且除最后一

39、個子序列外，其余每個子序列的長度都相同。設這些子序列的長度為d，則一趟歸并排序的過程是： 從j=1開始，依次將相鄰的兩個有序子序列Rjj+d-1和Rj+dj+2d-1進行歸并；每次歸并兩個子序列后，j后移動2d個位置，即j=j+2d；若剩下的元素不足兩個子序列時，分以下兩種情況處理： 剩下的元素個數(shù)d：再調用一次上述過程，將一個長度為d的子序列和不足d的子序列進行歸并； 剩下的元素個數(shù)d：將剩下的元素依次復制到歸并后的序列中。, 一趟歸并排序算法 void Merge_pass(RecType R, RecType DR, int d, int n) int j=1 ; while (j+2*

40、d-1)=n) Merge(R, DR, j, j+d-1, j+2*d-1) ; j=j+2*d ; /* 子序列兩兩歸并 */ if (j+d-1n) /* 剩余元素個數(shù)超過一個子序列長度d */ Merge(R, DR, j, j+d-1, n) ; else Merge(R, DR, j, n, n) ;/* 剩余子序列復制 */ , 歸并排序的算法 開始歸并時，每個記錄是長度為1的有序子序列，對這些有序子序列逐趟歸并，每一趟歸并后有序子序列的長度均擴大一倍；當有序子序列的長度與整個記錄序列長度相等時，整個記錄序列就成為有序序列。算法是： void Merge_sort(Sqlist

41、*L, RecType DR) int d=1 ; while(dlength) Merge_pass(L-R, DR, d, L-length) ; Merge_pass(DR, L-R, 2*d, L-length) ; d=4*d ; ,3 算法分析 具有n個待排序記錄的歸并次數(shù)是2n，而一趟歸并的時間復雜度為O(n)，則整個歸并排序的時間復雜度無論是最好還是最壞情況均為O(n2n)。在排序過程中，使用了輔助向量DR，大小與待排序記錄空間相同，則空間復雜度為O(n)。歸并排序是穩(wěn)定的。,10. 6 基數(shù)排序,基數(shù)排序(Radix Sorting) 又稱為桶排序或數(shù)字排序：按待排序記錄的關

42、鍵字的組成成分(或“位”)進行排序。 基數(shù)排序和前面的各種內部排序方法完全不同，不需要進行關鍵字的比較和記錄的移動。借助于多關鍵字排序思想實現(xiàn)單邏輯關鍵字的排序。,10.6.1 多關鍵字排序,設有n個記錄R1, R2, ,Rn， 每個記錄Ri的關鍵字是由若干項(數(shù)據(jù)項)組成，即記錄Ri的關鍵字Key是若干項的集合： Ki1, Ki2, ,Kid(d1) 。 記錄R1, R2, ,Rn有序的，指的是i, j1,n，ij ，若記錄的關鍵字滿足： Ki1, Ki2, KidKj1, Kj2, Kjd， 即Kip Kjp (p=1, 2, d),多關鍵字排序思想 先按第一個關鍵字K1進行排序，將記錄序

43、列分成若干個子序列，每個子序列有相同的K1值；然后分別對每個子序列按第二個關鍵字K2進行排序，每個子序列又被分成若干個更小的子序列；如此重復，直到按最后一個關鍵字Kd進行排序。 最后，將所有的子序列依次聯(lián)接成一個有序的記錄序列，該方法稱為最高位優(yōu)先(Most Significant Digit first)。 另一種方法正好相反，排序的順序是從最低位開始，稱為最低位優(yōu)先(Least Significant Digit first)。,10.6.2 鏈式基數(shù)排序,若記錄的關鍵字由若干確定的部分(又稱為 “位”)組成，每一位(部分)都有確定數(shù)目的取值。對這樣的記錄序列排序的有效方法是基數(shù)排序。 設

44、有n個待排序記錄R1, R2, ,Rn， (單)關鍵字是由d位(部分)組成，每位有r種取值，則關鍵字Ri.key可以看成一個d元組： Ri.key=Ki1, Ki2, ,Kid 。 基數(shù)排序可以采用前面介紹的MSD或LSD方法。以下以LSD方法討論鏈式基數(shù)排序。,1 排序思想 首先以靜態(tài)鏈表存儲n個待排序記錄，頭結點指針指向第一個記錄結點； 一趟排序的過程是： 分配： 按Kd值的升序順序，改變記錄指針，將鏈表中的記錄結點分配到r個鏈表(桶)中，每個鏈表中所有記錄的關鍵字的最低位(Kd)的值都相等，用fi、ei作為第i個鏈表的頭結點和尾結點； 收集：改變所有非空鏈表的尾結點指針，使其指向下一個非

45、空連表的第一個結點，從而將r個鏈表中的記錄重新鏈接成一個鏈表； 如此依次按Kd-1, Kd-2, K1分別進行，共進行d趟排序后排序完成。,2 排序示例 設有關鍵字序列為1039, 2121, 3355, 4382, 66, 118的一組記錄，采用鏈式基數(shù)排序的過程如下圖10-12所示。,3 鏈式基數(shù)排序算法 為實現(xiàn)基數(shù)排序，用兩個指針數(shù)組來分別管理所有的緩存(桶)，同時對待排序記錄的數(shù)據(jù)類型進行改造，相應的數(shù)據(jù)類型定義如下： #define BIT_key 8 /* 指定關鍵字的位數(shù)d */ #define RADIX 10 /* 指定關鍵字基數(shù)r */ typedef struct Rec

46、Type char keyBIT_key ; /* 關鍵字域 */ infoType otheritems ; struct RecType *next ; SRecord, *fRADIX ,*eRADIX ; /* 桶的頭尾指針數(shù)組 */,void Radix_sort(SRecord *head ) int j, k, m ; SRecord *p, *q, *fRADIX, *eRADIX ; for (j=BIT_key-1; j=0; j-) /* 關鍵字的每位一趟排序 */ for (k=0; kkeyj) ; /* 取關鍵字的第j位kj */ if (fm=NULL) fm=p

47、 ; else em-next=p ; p=p-next ;, head=NULL ; /* 以head作為頭指針進行收集 */ q=head ; /* q作為收集后的尾指針 */ for (k=0; knext=fk ; else head=fk ; q=ek ; /* 完成一趟排序的收集 */ q-next=NULL ; /* 修改收集鏈尾指針 */ ,4 算法分析 設有n個待排序記錄，關鍵字位數(shù)為d，每位有r種取值。則排序的趟數(shù)是d；在每一趟中： 鏈表初始化的時間復雜度：O(r) ； 分配的時間復雜度：O(n) ； 分配后收集的時間復雜度：O(r) ； 則鏈式基數(shù)排序的時間復雜度為： O(d(n+r) 在排序過程中使用的輔助空間是：2r個鏈表指針， n個指針域空間，則空間復雜度為：O(n+r) 基數(shù)排序是穩(wěn)定的。