《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第8章 排序C語言描述（第2版）張乃孝編著

《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第8章 排序C語言描述（第2版）張乃孝編著》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第8章 排序C語言描述（第2版）張乃孝編著（73頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、8.1 基本概念8.2 插入排序8.3 選擇排序8.4 交換排序8.5 分配排序8.6 歸并排序（1）排序的確切定義： 假設(shè)R0, R1, , Rn-1是由n個記錄組成的文件， K0, K1, , Kn-1是排序碼集合，所謂排序是將記錄 按排序碼不增（或不減）的次序排列。 排序碼可以是主關(guān)鍵碼，也可以是次關(guān)鍵碼。 （2）穩(wěn)定排序和不穩(wěn)定排序 假設(shè)Ki=Kj(0=i,j=n-1,ij)，且在排序前的序列 中Ri領(lǐng)先于Rj(即ij)，若在排序后的序列中Ri仍領(lǐng) 先于Rj，則稱所用的排序方法是穩(wěn)定的，否則是不 穩(wěn)定的。 （3）排序中的基本操作： 比較關(guān)鍵碼大小 移動記錄（4）待排序的記錄在排序過程中

2、全部存放在內(nèi)存的稱為內(nèi)排序，如果排序過程中需要使用外存的稱為外排序。本章討論的都是內(nèi)排序的方法，但有些方法(特別是歸并排序的思想)也可以用于外排序。排序方法：一、插入排序二、選擇排序三、交換排序四、分配排序五、歸并排序六、外部排序* 評價排序算法好壞的標(biāo)準(zhǔn)主要有兩條第一是執(zhí)行算法所需的時間；第二是執(zhí)行算法所需要的附加空間；另外算法本身的復(fù)雜程度也是考慮的一個因素。由于排序是經(jīng)常使用的一種運算，因此，排序的時間開銷是算法好壞的最重要的標(biāo)志。而排序的時間開銷又可以用算法執(zhí)行中的比較和移動次數(shù)來衡量。 8.2.1 8.2.1 直接插入排序直接插入排序 8.2.2 8.2.2 二分法插入排序二分法插入

3、排序 8.2.3 8.2.3 表插入排序表插入排序 8.2.4 8.2.4 ShellShell排序排序8.2.1 8.2.1 直接插入排序直接插入排序 初始： 49 38 65 97 76 13 27 49 i=1: 38 49 65 97 76 13 27 49 i=2: 38 49 65 97 76 13 27 49 i=3: 38 49 65 97 76 13 27 49 i=4: 38 49 65 76 97 13 27 49 i=5: 13 38 49 65 76 97 27 49 i=6: 13 27 38 49 65 76 97 49 i=7: 13 27 38 49 49 6

4、5 76 97 穩(wěn)定排序 typedef int KeyTypetypedef int KeyType; ;typedef int DataTypetypedef int DataType; ;typedef atructtypedef atruct KeyType KeyType key; key; DataType DataType info; info;RecordNodeRecordNode; ;typedef structtypedef struct int int n; n; RecordNode RecordNode * *record;record;SortObjectSort

5、Object; ;算法算法8.1 直接插入排序直接插入排序void insertSort(SortObject * pvector)/ 按增序進行直接插入排序按增序進行直接插入排序 int i, j; RecordNode temp; for( i = 1; i n; i+ ) /* 依次插入記錄依次插入記錄R1, R2Rn-1 */ temp = pvector-recordi; j = i-1; while (temp.key recordj.key)&(j=0) ) /* 由后向前找插入位置由后向前找插入位置 */ pvector-recordj+1 = pvector-recordj;

6、 /* 將排序碼大于將排序碼大于ki的記錄后移的記錄后移 */ j-; if( j!=(i-1) ) pvector-recordj+1 = temp; 算法分析： 空間效率：只需要一個記錄的輔助空間。 時間效率：比較記錄的次數(shù): 最小: n-1次;最大: n(n-1)/2次移動記錄的次數(shù): 最小: n-1 最大: (n+4)(n-1)/2 i-1 i-1 pjcj =(1/i)(j+1) =(i+1)/2 j=0 j=0 n-1 (i+1)/2 = O(n2) i=1平均情況：比較O(n2)，移動O(n2) 由于插入排序的基本操作是在有序表中進行查找,而查找的過程是可以用折半查找來實現(xiàn)的。由

7、此實現(xiàn)的排序稱為二分法插入排序。8.2.2 8.2.2 二分法插入排序二分法插入排序 二分法插入排序必須采用順序存儲方式。 二分法插入排序的比較次數(shù)與待排序記錄的初始狀態(tài)無關(guān)，僅依賴于記錄的個數(shù) 二分法插入排序(1) 1327384965769749 left=0 mid=3right=6(2) 1327384965769749left=4 mid=5 right=6(3) 1327384965769749left=4 mid=4 right=4 49right 已找到插入位置left=4(4) 1327384949657697圖8.2 二分法插入排序示例 算法分析： 空間效率：同直接插入排序

8、 時間效率：僅減少了比較次數(shù)，移動記錄次數(shù)不變。 n log2i nlog2n i=1最壞的情況為n2/2，最好的情況為2n，平均移動次數(shù)為O(n2) 4938659776132749 prenow3849659776132749 prenow3849659776132749 prenow3849659776132749 prenow類型聲明如下：struct Node;typedef struct Node ListNode;struct Node KeyType key; DataType info; ListNode *next; ;typedef ListNode * LinkList

9、;算法 8.3 表插入排序算法分析： 空間效率：每個記錄中增加了一個next字段，所以，輔助空間為S(n)=O(n)。 時間效率： 用鏈表方式減少記錄移動的次數(shù)，時間復(fù)雜度仍為O(n2)。算法由條件p.key=now.key保證表插入排序是穩(wěn)定的。 shell排序又稱縮小增量排序(Diminishing Increment Sort)。 先將整個待排記錄序列分割成若干個子序列分別進行直接插入排序，待整個序列中的記錄“基本有序“時，再對全體記錄進行一次直接插入排序，就可以完成整個的排序工作。 shell排序的一個特點是：子序列的構(gòu)成不是簡單“逐段分割”，而是將相隔某個增量的記錄組成一個子序列。

10、8.2.4 shell.2.4 shell排序排序非形式算法如下所示： increment=d; /* d0) 相距 increment的記錄為一組 對每組進行插入排序； increment=increment/2; ;Shell排序的平均比較次數(shù)和平均移動次數(shù)都為O(n1.3)左右。Shell排序算法中增加了一個輔助空間temp，因此算法的輔助空間為S(n)=O(1)。Shell排序是不穩(wěn)定的。 算法 8.4 shell 排序例題 待排序序列為49,38,65,97,13,76,27,49，請用 Shell排序法排序。 原始序列 49 38 65 97 13 76 27 491. d=4 2

11、. d=2 13 38 27 49 49 76 65 97 3. d=1 13 38 27 49 49 76 65 97 排序結(jié)果 13 27 38 49 49 65 76 97 基本思想是：每一趟在n-i+1個記錄中選取關(guān)鍵碼最小的記錄作為有序序列中第i個記錄。 8.3.1 8.3.1 直接選擇排序直接選擇排序 8.3.2 8.3.2 堆排序堆排序直接選擇排序的時間復(fù)雜度： 移動：最好時：0最壞時：3（n-1) 比較：n(n-1)/2 總的時間復(fù)雜度：O(n2)穩(wěn)定性：不穩(wěn)定 首先在所有記錄中選出排序碼最小的記錄，與第一個記錄交換，然后在其余的記錄中再選出排序碼最小的記錄與第二個記錄交換，以

12、此類推，直到所有記錄排好序。 直接選擇排序的比較次數(shù)與文件初始狀態(tài)無關(guān)。 8.3.1 直接選擇排序直接選擇排序49 38 65 97 49 13 27 76 13 38 65 97 49 49 27 76 13 27 65 97 49 49 38 76 13 27 38 97 49 49 65 7613 27 38 49 97 49 65 7613 27 38 49 49 97 65 7613 27 38 49 49 65 97 7613 27 38 49 49 65 76 9713 27 38 49 49 65 76 97 算法8.5 直接選擇排序void selectSort(SortOb

13、ject * pvector)/ 按遞增序進行選擇排序 int i, j, k; RecordNode temp; for( i = 0; i n-1; i+ )/* 做n-1趟選擇排序 */ k=i; for(j=i+1; jn; j+) /* 在無序區(qū)內(nèi)找出排序碼最小的記錄Rk*/ if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) /* 記錄Rk與Ri互換 */ temp=pvector-recordi; pvector-record i= pvector-record k; pvector-record k=temp; 選擇排序選擇排序的主

14、要操作是比較比較，要提高它的速度必須減少比較的次數(shù)。而實際上如果能利用以前的比較結(jié)果則可以提高排序速度。 樹形選擇排序樹形選擇排序(Tree Selection Sort)，又稱錦標(biāo)錦標(biāo)賽排序賽排序(Tournament Sort)。其方法是：首先對n個記錄的關(guān)鍵字進行兩兩比較，然后在n/2個較小者之間再進行兩兩比較，如此重復(fù)直到選出最小關(guān)鍵字的記錄為止。然后對剩下的記錄作同樣的操作，選出具有次小關(guān)鍵字的記錄。這個過程可以用一個完全二叉樹來表示。如下圖。8.3.2 8.3.2 堆排序堆排序(Heap Sort)(Heap Sort)133813386513274938659776132788樹

15、形選擇排序示例樹形選擇排序示例 該方法的時間復(fù)雜度為O(nlog2n)。缺點是使用了較多的輔助空間，并且和“最大值”進行了多余的比較。1964年Willioms提出了堆排序堆排序。 堆的定義：n個元素的序列k1,k2,kn當(dāng)且僅當(dāng)滿足如下關(guān)系時，稱之為堆。 ki k2iki k2i ki k2i+1 ki k2i+1( i = 1, 2, , n/2 ) 或 若將和此序列對應(yīng)的一維數(shù)組看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不大于（或不小于）其左右孩子結(jié)點的值。由此，若序列 k1,k2,kn 是堆，則堆頂元素必為序列中n個元素的最小值（或最大值）。如果在輸出堆頂?shù)?/p>

16、最小值后，使得剩余n-1個元素的序列重又建成一個堆，則得到次小值。反復(fù)執(zhí)行便能得到所有記錄的有序序列，這個過程稱為堆排序。 現(xiàn)在剩下兩個問題： （1）如何由一個無序序列建成一個堆； （2）如何在輸出堆頂元素后，調(diào)整剩余元素為 一個新的堆。 在輸出堆頂元素后，用堆中最后一個元素替代，此時根結(jié)點的左右子樹均為堆，則僅需自上而下進行調(diào)整即可。首先堆頂元素和其左右孩子的值比較，把最小的值（假設(shè)為左孩子結(jié)點）調(diào)到根結(jié)點的位置，由于左子樹的根結(jié)點發(fā)生了改變，因此需要對左子樹進行上述一樣的調(diào)整，直至葉子結(jié)點。這個自堆頂至葉子的調(diào)整過程稱為篩選。 從一個無序序列建堆的過程就是一個反復(fù)篩選的過程。若將此無序序列

17、看成是一個完全二叉樹，則最后一個非終端結(jié)點就是第n/2 個元素，因此篩選只需從第n/2 個元素起，篩選到第1個元素（即堆頂元素）。如下頁圖。例：初始序列為 26，5，77，1，61，11，59，15，48，1926057701611159154819（1）初始完全二叉樹26057701611159154819(2)調(diào)整序號為4的結(jié)點 26057748611159150119(3)調(diào)整序號為3的結(jié)點 26057748611159150119(4)調(diào)整序號為2的結(jié)點 26617748191159150105(5)調(diào)整序號為1的結(jié)點 77615948191126150105(6)調(diào)整序號為0的結(jié)點

18、05615948191126150177(7)結(jié)點77與結(jié)點5互換615915191126050177(8)重建堆48(9)結(jié)點61與結(jié)點1互換592615191101056177(10)重建堆4801591519112605617748(11)結(jié)點59與結(jié)點05互換052615191101596177(12)重建堆4848261505110159617719(12)結(jié)點48與結(jié)點1互換(13)重建堆0126150511485961771926111505014859617719(15)結(jié)點26與結(jié)點1互換(16)重建堆0111150526485961771919110105264859617

19、715(17)結(jié)點19與結(jié)點5互換(18)重建堆0511011926485961771515110119264859617705(19)結(jié)點15與結(jié)點1互換(20)重建堆0111151926485961770511011519264859617705 堆排序適用于n值較大的情況。其比較次數(shù)為： 2n(log2n)。在最壞的情況下，時間復(fù)雜度也是O(nlogn)。且僅需一個記錄大小的輔助空間。 兩兩比較待排序記錄的排序碼，交換不滿足順序要求的偶對，直到全部為止。 8.4.1 8.4.1 起泡排序起泡排序 8.4.2 8.4.2 快速排序快速排序 設(shè)待排序記錄順序存放在R0,R1,R2,Rn-1中

20、，依次比較（R0,R1），（ R1,R2）, (Rn-2,Rn-1),不滿足順序則交換，結(jié)果，最大者在Rn-1中。這叫一次起泡。此后，再對存放在R0,R1,R2,Rn-2中n-1個記錄作同樣處理,結(jié)果，最大者在Rn-2中。 。 n-1次起泡能完成排序。設(shè)置標(biāo)志noswap表示本次起泡是否有交換，若無交換，表示排序完成。8.4.1 8.4.1 起泡排序起泡排序38 49 65 76 13 27 49 97 49 38 65 97 76 13 27 49 38 49 65 13 27 49 76 97 38 49 13 27 49 65 76 97 38 13 27 49 49 65 76 97

21、13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 初始 1 2 3 4 5 6 算法8.7 起泡排序算法void bubbleSort(SortObject * pvector) int i, j, noswap; RecordNode temp; for(i=0; in-1; i+)/* 做n-1次起泡 */ noswap=TRUE; for(j=0; jn-i-1; j+) /* 置交換標(biāo)志 */ if(pvector-recordj+1.keyrecordj.key) temp=pvector-recordj; /* 交換記錄 */ pvec

22、tor-recordj=pvector-recordj+1; pvector-recordj+1=temp; noswap=FALSE; if(noswap) break; /本趟起泡未發(fā)生記錄交換，算法結(jié)束 起泡排序的最壞時間復(fù)雜度為O(n2)，平均 時間復(fù)雜度為O(n2)。 起泡排序算法中增加一個輔助空間temp，輔助空間為S(n)=O(1)。 起泡排序是穩(wěn)定的。 快速排序是對冒泡排序的改進，其基本思想是：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。 首先任意選取一個記錄作為樞軸（或支點

23、）(Pivot)，然后按下述原則重新排列其一記錄：將所有關(guān)鍵字小于它的記錄都安置在它之前，將所有關(guān)鍵字大于它的記錄安置在它之后。于是以該樞軸記錄所在的位置i作分界線，將整個序列分成兩個子序列。這個過程稱為一趟快速排序。然后分別對于兩個子序列作同樣的操作，重復(fù)這個過程，直到子序列不可再分就完成了記錄的排序工作。一趟快速排序的具體做法是：附設(shè)兩個指針low和high,它們的初值分別是一個序列的第一個和最后一個記錄的位置，設(shè)樞軸記錄的關(guān)鍵字為pivotKey，在首先從high所指位置起向前搜索直到第一個關(guān)鍵字小于pivotKey的記錄和樞軸記錄交換，然后從low所指位置起向后搜索，找到第一個關(guān)鍵字大

24、于pivotKey的記錄和樞軸記錄互相交換，重復(fù)交替這兩步直到low=high為止。算法算法8.8 8.8 快速排序算法快速排序算法491386597761327492樞軸一般取第樞軸一般取第一個記錄，并把一個記錄，并把樞軸關(guān)鍵字放入樞軸關(guān)鍵字放入臨時變量中，空臨時變量中，空置樞軸所在位置置樞軸所在位置從高端找一個比從高端找一個比樞軸關(guān)鍵字小的樞軸關(guān)鍵字小的記錄放入當(dāng)前空記錄放入當(dāng)前空的低端位置的低端位置從低端找一個比樞軸關(guān)鍵字大的從低端找一個比樞軸關(guān)鍵字大的記錄放入當(dāng)前空的高端位置記錄放入當(dāng)前空的高端位置樞軸樞軸lowhigh臨時變量：臨時變量： pivotkey=491Low與與high標(biāo)

25、識標(biāo)識記錄調(diào)整的低記錄調(diào)整的低端與高端位置端與高端位置highlow65high1397491Low =high樞軸應(yīng)樞軸應(yīng)到達的最終位置到達的最終位置27high交替進行上述兩步交替進行上述兩步記錄重新排列的記錄重新排列的策略：從表的兩策略：從表的兩側(cè)向中間夾側(cè)向中間夾lowhigh49 38 65 97 76 13 27 4927 38 13 49 76 97 65 4913 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 各趟排序結(jié)果算法算法8.8 快速排序算法快速排序算法void quickSort(SortObject * pvector,

26、int l, int r) int i, j; RecordNode temp; if(l=r) return; /* 只有一個記錄或無記錄，則無須排序只有一個記錄或無記錄，則無須排序 */ i=l; j=r; temp=pvector-recordi; while(i!=j)/* 尋找尋找Rl的最終位置的最終位置 */ while( (pvector-recordj.key=temp.key) & (ji) ) j - -; /從右向左掃描，查找第從右向左掃描，查找第1個排序碼小于個排序碼小于temp.key的記錄的記錄 if(irecordi+= pvector-record j; whi

27、le( (pvector-recordi.keyi) ) i+; /從左向右掃描，查找第從左向右掃描，查找第1個排序碼大于個排序碼大于temp.key的記錄的記錄 if(irecordj-= pvector-recordi; pvector-recordi=temp;/* 找到找到Rl的最終位置的最終位置 */ quickSort(pvector,l,i-1); /* 遞歸處理左區(qū)間遞歸處理左區(qū)間 */ quickSort(pvector,i+1,r);/* 遞歸處理右區(qū)間遞歸處理右區(qū)間 */算法分析： 快速排序的記錄移動次數(shù)不大于比較次數(shù)，所以，快速排序的最壞時間復(fù)雜度應(yīng)為O(n2)，最好時

28、間復(fù)雜度為O(nlog2n)。為了改善最壞情況下的時間性能，可采用“三者取中”的規(guī)則，即在每一趟劃分前，首先比較Rl.key、Rr.key和R.key的大小，取中間的記錄與Rl交換。快速排序的平均時間復(fù)雜度是T(n)=O(nlog2n)。 算法需要一個?？臻g實現(xiàn)遞歸。棧的大小取決于遞歸調(diào)用的深度，最多不超過n，若每次都選較大的部分進棧，處理較短的部分，則遞歸深度最多不超過log2n，所以快速排序的輔助空間為S(n)=O(log2n)。 快速排序是不穩(wěn)定的。 分配排序的思想是把排序碼分解成若干部分，然后通過對各個部分排序碼的分別排序，最終達到整個排序碼的排序。 8.5.1 8.5.1 概述概述

29、8.5.2 8.5.2 基數(shù)排序基數(shù)排序 多關(guān)鍵字的排序l假定撲克牌的次序為: 23A23A 23A23Al要將撲克牌排成上面的次序，通常采用的方法是先按花色分成4堆，并按花色的次序?qū)?堆排好，然后分別對每一堆按面值從小到大整理有序。這種方法稱為最高位優(yōu)先法MSD（most significant digit first）8.5.1 8.5.1 概述概述l也可以先按面值分成13堆，并按面值大小將13堆排好，然后再將這13堆按花色分成4堆，4堆牌按花色從小到大合在一起，同樣完成排序。這種方法稱為最低位優(yōu)先法LSD（lease significant digit first）。 一般情況下，假設(shè)文

30、件F有n個記錄F=(R0，R1，Rn-1) 且每個記錄Ri的排序碼中含有d個部分(ki0, ki1, kid-1)，則文件F對排序碼(k0,k1,kd-1)有序是指 文件中任意兩個記錄Ri和Rj(0ijn-1)滿足詞典次序有序關(guān)系(ki0, ki1, kid-1) (kj0, kj1, kjd-1) 其中k0稱為最高位排序碼，kd-1稱為最低位排序碼。實現(xiàn)分配排序，有兩種方法 第一種是先對最高位排序碼k0排序，稱為高位優(yōu)先法。第二種是先對最低位排序碼kd-1排序，稱為低位優(yōu)先法。 低位優(yōu)先法比高位優(yōu)先法簡單，高位優(yōu)先排序必須將文件逐層分割成若干子文件，然后各子文件獨立排序；低位優(yōu)先排序不必分成

31、子堆，對每個排序碼都是整個文件參加排序，且可通過若干次“分配”和“收集”實現(xiàn)排序。但對Ki(0 = i = d-2)進行排序時，只能用穩(wěn)定的排序方法。 下面將介紹的基數(shù)排序就是用排序碼低位優(yōu)先法的思想對排序碼進行分解后排序的一種方法。 采用基數(shù)排序首先把每個排序碼看成是一個d元組Ki=(Ki0, Ki1, Kid-1) 其中每個Ki都是集合C0，C1，Cr-1 (C0C1Cr-1)中的值，即C0KijCr-1(0in-1, 0jd-1)，其中r稱為基數(shù)基數(shù)。排序時先按Kid-1從小到大將記錄分配到r個堆中，然后依次收集，再按Kid-2分配到r個堆中，如此反復(fù)，直到對Ki0分配、收集，得到的便是

32、排好序的序列。 8.5.2 8.5.2 基數(shù)排序基數(shù)排序109278063930589184505269008083e0 e1 e2 e3 e4 e5 e6 e7 e8 e9f0 f1 f2 f3 f4 f5 f6 f7 f8 f9930063083184505008278109589269063930083184505278008109589269e0 e1 e2 e3 e4 e5 e6 e7 e8 e9505008109930063269278083184589f0 f1 f2 f3 f4 f5 f6 f7 f8 f9008505109930063269278083184259e0 e1

33、e2 e3 e4 e5 e6 e7 e8 e9008063083109184269278505589930f0 f1 f2 f3 f4 f5 f6 f7 f8 f9063008083109184269278505589930時間復(fù)雜度O(d*n)其中d為關(guān)鍵字的位數(shù)，n為關(guān)鍵字的個數(shù)。穩(wěn)定的排序方法。l基數(shù)排序算法中，時間耗費主要在修改指針上。一趟排序的時間為O(r+n)。總共要進行d趟排序，基數(shù)排序的時間復(fù)雜度是T(n)=O(d*(r+n)。當(dāng)n較大、d較小，特別是記錄的信息量較大時，基數(shù)排序非常有效。l基數(shù)排序中，每個記錄中增加了一個next字段，還增加了一個queue數(shù)組，故輔助空間為S

34、(n)=O(n+r)。l基數(shù)排序是穩(wěn)定的。算法分析：算法算法8.9 8.9 基數(shù)排序算法基數(shù)排序算法 歸并的含義是將兩個或兩個以上的有序表合并成一個有序表。利用歸并的思想就可以實現(xiàn)排序。假設(shè)初始的序列含有n個記錄，可以看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復(fù)直到得到一個長度為n的有序序列為止。這種排序方法稱為二路歸并排序。例題初始序列為25, 57, 48, 37, 12, 82, 75, 29, 16，請用二路歸并排序法排序。初始排序碼25 57 48 37 12 82 75 29 16 / / / /第一趟歸并后2

35、5 57 37 48 12 82 29 75 16 / /第二趟歸并后25 37 48 57 12 29 75 82 16 /第三趟歸并后12 25 29 37 48 57 75 82 16 /第四趟歸并后12 16 25 29 37 48 57 75 82排序后的結(jié)果為 12, 16, 25, 29, 37, 48, 57, 75, 82算法分析: 時間復(fù)雜度: O(nlog2n) 空間復(fù)雜度: 和待排記錄等量的空間. 二路歸并算法是穩(wěn)定的. 一般情況下很少用于內(nèi)部排序.算法算法8.10 8.10 兩組歸并算法兩組歸并算法算法算法8.11 8.11 一趟歸并算法一趟歸并算法算法算法8.12

36、8.12 二路歸并算法二路歸并算法算法算法7.11 7.11 兩組歸并算法兩組歸并算法void merge(RecordNode r,RecordNode r1,int low,int m,int high)void merge(RecordNode r,RecordNode r1,int low,int m,int high) / /* *rlowrlow到到rmrm和和rm+1rm+1到到rhightrhight是兩個有序文件是兩個有序文件 * */ / int i,j,k; int i,j,k; i=low; j=m+1; k=low; i=low; j=m+1; k=low; whil

37、e( (i=m) & (j=high) ) while( (i=m) & (j=high) ) if(ri.key=rj.key) if(ri.key=rj.key) / /從兩個有序文件中的第一個記錄中選出小的記錄從兩個有序文件中的第一個記錄中選出小的記錄 r1k+=ri+;r1k+=ri+; else else r1k+=rj+; r1k+=rj+; while (i=m) r1k+=ri+; while (i=m) r1k+=ri+; / /* * 復(fù)制第一個文件的剩余記錄復(fù)制第一個文件的剩余記錄 * */ / while (j=high) r1k+=rj+; while (j=high

38、) r1k+=rj+; / /* * 復(fù)制第二個文件的剩余記錄復(fù)制第二個文件的剩余記錄 * */ / 算法算法7.12 7.12 一趟歸并算法一趟歸并算法/ /* * 對對r r做一趟歸并，結(jié)果放在做一趟歸并，結(jié)果放在r1r1中中 * */ /void mergePass(RecordNode r,RecordNode r1,int n,int length)void mergePass(RecordNode r,RecordNode r1,int n,int length) / /* * length length為本趟歸并的有序子文件的長度為本趟歸并的有序子文件的長度 * */ / int

39、 i, j; int i, j; i=0; i=0; while(i+2 while(i+2* *length-1n)length-1n) merge(r,r1,i,i+length-1,i+2 merge(r,r1,i,i+length-1,i+2* *length-1);length-1); / /* * 歸并長度為歸并長度為lengthlength的兩個子文件的兩個子文件* */ / i+=2 i+=2* *length;length; if(i+length-1n-1) if(i+length-1n-1) / /* * 剩下兩個子文件，其中一個長度小于剩下兩個子文件，其中一個長度小于

40、length length * */ / merge(r,r1,i,i+length-1,n-1); merge(r,r1,i,i+length-1,n-1); else else for(j=i; jn; j+) for(j=i; jn; j+) / /* * 將最后一個子文件復(fù)制到數(shù)組將最后一個子文件復(fù)制到數(shù)組r1r1中中 * */ / r1j=rj; r1j=rj; 算法算法7.13 7.13 二路歸并算法二路歸并算法void mergeSort(SortObject void mergeSort(SortObject * * pvector) pvector) RecordNode r

41、ecordMAXNUM; RecordNode recordMAXNUM; int length; int length; length=1; length=1; while(lengthn) while(lengthn) mergePass(pvector-record,record,pvector-n,length); mergePass(pvector-record,record,pvector-n,length); / /* * 一趟歸并，結(jié)果存放在數(shù)組一趟歸并，結(jié)果存放在數(shù)組r1r1中中* */ / length length* *=2;=2; mergePass(record,pv

42、ector-record,pvector-n,length); mergePass(record,pvector-record,pvector-n,length); / /* * 一趟歸并，結(jié)果存放在數(shù)組一趟歸并，結(jié)果存放在數(shù)組r r中中 * */ / length length* *=2;=2; l8.6.2 外排序（略） 排序方法最壞時間復(fù)雜度平均時間復(fù)雜度 輔助空間 穩(wěn)定性直接插入排序O(n2) O(n2) O(1) 穩(wěn)定的二分法插入排序O(n2) O(n2) O(1) 穩(wěn)定的表插入排序O(n2) O(n2) O(n) 穩(wěn)定的Shell排序O(n1.3) O(n1.3) O(1) 不定的

43、直接選擇排序O(n2) O(n2) O(1)不穩(wěn)定的堆排序O(nlog2n) O(nlog2n) O(1)不穩(wěn)定的起泡排序O(n2) O(n2) O(1) 穩(wěn)定的快速排序O(n2) O(nlog2n) O(log2n)不穩(wěn)定的基數(shù)排序O(d(n+r) O(d(n+r) O(r+n) 穩(wěn)定的歸并排序O(nlog2n) O(nlog2n) O(n) 穩(wěn)定的結(jié)論： （1）平均時間性能：以快速排序法最佳，但最壞情況下不如堆排序和歸并排序；在n較大時，歸并排序比堆排序快，但所需輔助空間最多。 （2）簡單排序以直接插入排序最簡單，當(dāng)下列中記錄“基本有序“或n值較小時，是最佳的排序方法。因此常和其他排序方法

44、結(jié)合使用。 （3）基數(shù)排序最適用于n值很大而關(guān)鍵字較小的序列。若關(guān)鍵字也很大，而序列中大多數(shù)記錄的”最高位關(guān)鍵字”均不同，則也可以先按“最高位關(guān)鍵字”不同將序列分成若干個子序列，而后用直接插入排序。 （4）從穩(wěn)定性來看，基數(shù)排序是穩(wěn)定的排序方法，大部分時間復(fù)雜度為O(n2)的簡單排序法都是穩(wěn)定的。然而，快速排序、堆排序和希爾排序等時間性能較好的排序都是不穩(wěn)定的。一般來說，排序過程中的比較是在相鄰的兩個記錄關(guān)鍵字之間進行的排序方法是穩(wěn)定的。大多數(shù)情況下排序是按記錄的主關(guān)鍵字進行的，則所有的排序方法是否穩(wěn)定無關(guān)緊要。當(dāng)排序是按記錄的次關(guān)鍵字進行時，則應(yīng)根據(jù)問題所需慎重選擇。 本章討論的大多數(shù)算法是在順序存儲結(jié)構(gòu)上進行的，因此在排序過程中要進行大量的記錄的移動。當(dāng)記錄很大（即每個記錄所占的空間很大）時，記錄移動所耗費的時間也很多，此時可采用靜態(tài)鏈表作存儲結(jié)構(gòu)，如表插入排序，鏈?zhǔn)交鶖?shù)排序，以修改指針代替移動記錄。但有些方法如快速排序法是無法實現(xiàn)表排序的，在這種情況下，可以進行“地址排序”，即另設(shè)一個向量指示需要記錄，同時在排序過程中不移動記錄而移動地址向量中相應(yīng)分量的內(nèi)容。lP278 復(fù)習(xí)題 1，2，3l 算法題2，3，4