排序(sorting是計算機程序設(shè)計中的一種重要操作

1、排序 排序（sorting）是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。由于待排序的記錄數(shù)量不同，使得排序過程中涉及的存儲器不同，可將排序方法分為兩大類：一類是內(nèi)部排序，指的是待排序記錄存放在計算機存儲器中進行的排序過程；另一類是外部排序，指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中對外存進行訪問的排序過程。 插入排序插入排序 線性插入排序的基本思想是：第1遍，將初始文件中的記錄R1看作有序子文件，將R2插入這個子文件中。若R2的關(guān)鍵字小于R1的關(guān)鍵字，則R2插在R1的前面，否則R2插在R1的后面。

2、第2遍，將R3插入前面的兩個記錄的有序子文件中，得到3個記錄的有序子文件。依此類推，繼續(xù)進行下去，直到將Rn插入到前面的n-1個記錄的有序子文件中，最后得到n個記錄的有序文件。 線性插入排序的基本思想是：第1遍，將初始文件中的記錄R1看作有序子文件，將R2插入這個子文件中。若R2的關(guān)鍵字小于R1的關(guān)鍵字，則R2插在R1的前面，否則R2插在R1的后面。第2遍，將R3插入前面的兩個記錄的有序子文件中，得到3個記錄的有序子文件。依此類推，繼續(xù)進行下去，直到將Rn插入到前面的n-1個記錄的有序子文件中，最后得到n個記錄的有序文件。圖9-1所示為線性插入排序的例子。為了避免檢測是否應(yīng)插在R1的前面，在R

3、1的前面設(shè)立記錄R0，它既是中間變量，又是監(jiān)視哨。設(shè)（R1，R2，Ri-1）是已排序的有序子文件，則插入Ri的步驟是：首先將Ri存放到Ro中，然后將Ko（即原Ri的關(guān)鍵字Ki）依次與Ki-1，Ki-2，比較，若KoKj（j=i-1，i-2，1），則Rj后移一個位置，否則停止比較和移動；最后，將Ro（即原來待插入的記錄Ri）移到j(luò)+1的位置上。由于Ri的前面有監(jiān)視哨Ro，因此不必每次判斷下標j是否出界。算法描述如下： void insertsort(struct node r n+1,int n)/* rn+1為一維數(shù)組，其中r0為監(jiān)視哨，r1到rn為待排序的n個記錄，排序好的記錄仍放在r中*/

4、 for(i=2;ir0.key) rj+1=rj; j-; rj+1=r0; 折半插入排序 在線性插入排序中，我們采用順序查找法來確定記錄的插入位置。由于（R1，R2，Ri-1）是有序子文件，我們可以采用折半查找法來確定R1的插入位置，這種排序稱為折半插入排序。其算法可寫出如下：void binarysort(struct node r n+1,int n)/*按關(guān)鍵字遞增的次序?qū)τ涗況1,r2,rn進行折半插入排序 */ for(i=2;i=n;i+) r0=ri; l=1; h=i-1; while(l=h) mid=(l+h)/2; if(r0.key=l;j-) rj+1=rj; r

5、l=r0; 在上面的算法中，每插入一個R1，平均比較次數(shù)為log2i。 希爾排序希爾排序 希爾排序（Shells Method）又稱“縮小增量排序”（Diminishing Increment Sort），是由D.L.Shell在1959年提出來的。它的作法是：先取定一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組，所有距離為d1的倍數(shù)的記錄放在同一個組中，在各組內(nèi)進行直接插入排序；然后，到第二個增量d2d1重復(fù)上述分組和排序，直至所取的增量dt=1（dtdt-1d2d1），即所有記錄放在同一組中進行直接插入排序為止。先從一個具體的例子來看希爾排序。假設(shè)待排序文件有10個記錄，

6、其關(guān)鍵字分別是：49，38，65，97，76，13，27，49/，55，04。增量序列取值依次為：5，3，1。第一趟排序時，d1=5，整個文件被分成5組：（R1，R6），（R2，R7），（R5，R10）各組中的第1個記錄都自成一個有序區(qū)，我們依次將各組的第2個記錄R6，R7，R10分別插入到各組的有序區(qū)中，使文件的各組均是有序的，其結(jié)果見圖9-2的第七行。第二趟排序時，d2=3，整個文件分成三組：（R1，R4，R7，R10），（R2，R5，R8），（R3，R6，R9），各組的第1個記錄仍自成一個有序區(qū)，然后依次將各組的第2個記錄R4，R5，R6分別插入到該組的當前有序區(qū)中，使得（R1，R4），

7、（R2，R5），（R3，R6）均變?yōu)樾碌挠行騾^(qū)，接著依次將各組的第3個記錄R7，R8，R9分別插入到該組當前的有序區(qū)中，又使得（R1，R4，R7），（R2，R5，R8），（R3，R6，R9）均變?yōu)樾碌挠行騾^(qū)，最后將R10插入到有序區(qū)（R1，R4，R7）中就得到第二趟排序結(jié)果。最后一趟排序時，d3=1，即是對整個文件做直接插入排序，其結(jié)果即為有序文件。 若不設(shè)置監(jiān)視哨，根據(jù)上例的分析不難寫出希爾排序算法，請讀者自行完成之。下面我們先分析如何設(shè)置監(jiān)視哨，然后給出具體算法。設(shè)某一趟希爾排序的增量為h，則整個文件被分成h組：（R1，Rh+1，R2h+1，），（R2，Rh+2，R2h+2，），（Rh，R

8、2h，R3h，），因為各組中記錄之間的距離均為是h，故第1組至第h組的哨兵位置依次為1-h，2-h，0。如果象直接插入排序算法那樣，將待插入記錄Ri（h+1iN） 在查找插入位置之前保存到監(jiān)視哨中，那么必須先計Ri屬于哪一組，才能決定使用哪個監(jiān)視哨來保存Ri。為了避免這種計算，我們可以將Ri保存到另一個輔肋記錄X中，而將所有監(jiān)視哨R1-h，R2-h，R0的關(guān)鍵字，設(shè)置為小于文件中的任何關(guān)鍵字即可。因為增量是變化的，所以，各趟排序中所需的監(jiān)視哨數(shù)目也不相同，但是我們可以按最大增量d1來設(shè)置監(jiān)視哨。 rectype Rn+d1； /* Rd1-1為d1個監(jiān)視哨*/int dt； /* d0到dt-

9、1為增量序列*/SHELLSORT(R,d)Rectype R ；int d ；int i，j，k，h； rectype temp; int maxint=32767； /*機器中最大整數(shù)*/ for (i=0；id0；i+) Ri.key=-maxint； /*設(shè)置哨兵*/ K=0； Do H=dk； /*取本趟增量*/ For(i=h+di；in+d1；i+) /*Rh+d1到Rn+d1-1插入當前有序區(qū)*/ temp=Ri； /*保存待插入記錄Ri*/ j=i-h； while(temp.keyRj.key) /*查找正確的插入位置*/ Rj+h=Rj； /*后移記錄*/ j=j-h；

10、/*得到前一記錄位置*/ Rj+h=temp； /*插入Ri*/ /*本趟排序完成*/ k+； while (h！=1)； /*增量為1排序后終止算法*/ /*SHELLSORT*/讀者可能看出，當增量h=1時，SHELLSORT算法與INSERTSORT基本一致。對希爾排序的分析提出了許多困難的數(shù)學(xué)問題，特別是如何選擇增量序列才能產(chǎn)生最好的排序效果，至今沒有得到解決。希爾本為最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。后來又有人提出其它選擇增量序列的方法，如di+1=(di-1)/3，dt=1，t=log3n-1；以及di+1=(di-1)/2，dt=1，t=log

11、2n-1。為什么希爾排序的時間性能優(yōu)于直接插入排序呢？我們知道直接插入排序在文件初態(tài)為正序時所需要時間最少，實際上，當文件初基本有序時直接插入排序所需的比較和移動次數(shù)均較少。另一面，當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復(fù)雜度O(n)和最壞時間復(fù)雜度O(n2)差別不大。在希爾排序時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較近于有序狀態(tài)，所以新的國趟排序過程也較快。因此，希爾排序在較率上較直接接入排序有較大的改進。希爾排序是不穩(wěn)定的。參見圖9-2的例

12、子，該例中兩個相同關(guān)鍵字49在排序前后的相對次序發(fā)生了變化。 選擇排序選擇排序 選擇排序（selection sort）也是一種簡單排序法。一個記錄最多只需進行一次交換就可以直接到達它的排序位置。設(shè)待排序的文件為（R1，R2，Rn），進行選擇排序的基本步驟如下：（1）置i 為1；（2）當in時，重復(fù)下列步驟；1）當(Ri，Rn)中選出一個關(guān)鍵字最小的記錄Rmin，若Rmin不是Ri，即Rmini則交換Ri和Rmin的位置；否則，不進行交換。2）i的值加1。第1遍掃描時，在n個記錄中為了選出最小關(guān)鍵字的記錄，需要進行n-1次比較，第2掃描時，在余下的n-1記錄中，再選出具有最小關(guān)鍵字的記錄需要比

13、較n-2次，第n-1掃描時，在最后的2個記錄中，比較1次選出最小關(guān)鍵字的記錄。 堆排序堆排序 堆排序(heap sort)是在選擇排序的基礎(chǔ)上發(fā)展起來的。它比選擇排序的效率要高。在堆排序中，把待排序的文件邏輯上看作是一棵順序二叉樹，并用到堆的概念。在介紹堆排序之前，先引入堆的概念。我們回憶一下，一棵有n個結(jié)點的順序二叉樹可以用一個長度為n的向量(一維數(shù)組)來表示；反過來，一個有n個記錄的順序表示的文件，在概念上可以看作是一棵有n個結(jié)點(即記錄)的順序二叉樹。例如，一個順序表示的文件(R1，R2，R9)，可以看作為圖9-4所示的順序二叉樹。 當我們把順序表示的文件(R1，R2，Rn)看作為順序二

14、叉樹時，由順序二叉樹的性質(zhì)可知：記錄Ri(1n，則Ri的左孩子不存在；Ri的右孩子是記錄R2i+1(2i+1n)，但若2i+1n，則Ri的右孩子不存在。什么是堆呢?堆是一個具有這樣性質(zhì)的順序二叉樹，每個非終端結(jié)點(記錄)的關(guān)鍵字大于等于它的孩子結(jié)點的關(guān)鍵字。例如，圖9-5所示的順序二叉樹就是一個堆。顯然，在一個堆中，根結(jié)點具有最大值(指關(guān)鍵字，下同)，而且堆中任何一個結(jié)點的非空左、右子樹都是一個堆，它的根結(jié)點到任一葉子的每條路徑上的結(jié)點都是遞減有序的。堆排序的基本思想是：首先把待排序的順序表示(一維數(shù)組)的文件(R1，R2，Rn)在概念上看作一棵順序二叉樹，并將它轉(zhuǎn)換成一個堆。這時，根結(jié)點具有

15、最大值，刪去根結(jié)點，然后將剩下的結(jié)點重新調(diào)整為一個堆。反復(fù)進行下去，直到只剩下一個結(jié)點為止。堆排序的關(guān)鍵步驟是如何把一棵順序二叉樹調(diào)整為一個堆。初始狀態(tài)時，結(jié)點是隨機排列的，需要經(jīng)過多次調(diào)整才能把它轉(zhuǎn)換成一個堆，這個堆叫做初始堆。建成堆之后，交換根結(jié)點和堆的最后一個結(jié)點的位置，相當于刪去了根結(jié)點。同時，剩下的結(jié)點(除原堆中的根結(jié)點)又構(gòu)成一棵順序二叉樹。這時，根結(jié)點的左、右子樹顯然仍都是一個堆，它們的根結(jié)點具有最大值(除上面刪去的原堆中的根結(jié)點)。把這樣一棵左、右子樹均是堆的順序二叉樹調(diào)整為新堆，是很容易實現(xiàn)的。例如，對于圖7-7所示的堆，交換根結(jié)點63和最后的結(jié)點30之后，便得到圖9-6(a

16、)所示的順序二叉樹(除63之外)。現(xiàn)在，新的根結(jié)點是30，其左、右子樹仍然都是堆。下面討論如何把這棵二叉樹調(diào)整為一個新堆。由于堆的根結(jié)點應(yīng)該是具有最大值的結(jié)點，且已知左、右子樹是堆，因此，新堆的根結(jié)點應(yīng)該是這棵二叉樹的根結(jié)點，根結(jié)點的左孩子，根結(jié)點的右孩子(若存在的話)中最大的那個結(jié)點。于是，先找出根結(jié)點的左、右孩子，比較它們的大小。將其中較大的孩子再與根結(jié)點比較大小。如果這個孩子大于根結(jié)點，則將這個孩子上移到根結(jié)點的位置，而根結(jié)點下沉到這個孩子的位置，即交換它們的位置。在圖9-6(a)中，根結(jié)點30的左、右孩子分別是60、59，由于6059，并且6030，于是應(yīng)交換根結(jié)點30和左孩子60的位

17、置。這時，新的根結(jié)點60的右子樹沒有改變，仍然是一個堆。但是，由于結(jié)點30下沉到左子樹的根上，使得左子樹有可能不再是堆了。按照上面所用的辦法，把這棵子樹調(diào)整為一個堆，顯然，結(jié)點30的左、右子樹原來都是堆，30的左、右子樹分別是40，45。由于4030，于是應(yīng)交換結(jié)點30和右孩子45的位置。 void adjust(struct node rm+1,int m) /* 將文件(r1,r2,rm)解釋為一棵順序二叉樹,將其中以ri為根結(jié)點的二叉樹調(diào)整 為一個堆,設(shè)以ri為根的二叉樹的左,右子樹已是堆,1i1m/2 */ x=ri;j=2*i; /*求出ri的左孩子r2*i，即rj */ while

18、 (j=m) /*有左孩子*/ if (jm) &(rj.keyrj+1.key) /*比較左、右孩子*/ j=j+1; /*左孩子右孩子*/ if (x.key=temp.key) & (ij) j-; /*從右向左掃描，查找第1個關(guān)鍵字小于temp.key的記錄*/ if(ij) Ri+=Rj; /*交換Ri和Rj*/ while(Ri.key=temp.key) & (ij) i+; /*從左向左掃描，查找第1個關(guān)鍵字大于temp.key的記錄*/ if(ij) Rj-=Ri; /*交換Ri和Rj*/ quicksort(R,s1,t1) /*對Rs1到Rt1*/

19、rectype R ;int s1,t1;int i; if (s1t1) /* 只有一個記錄或無記錄須排序*/ i= partition (R,s1,t1); /*對Rs1到Rt1做劃分*/ quicksort (R,s1,i-1); /*遞歸處理左區(qū)間*/ quicksort (R,i+1,t1); /*遞歸處理右區(qū)間*/ 圖9-7展示了一次劃分的過程及整個快速排序的過程。圖中方括號表示無序區(qū)，方框表示基準temp的關(guān)鍵字，它未參加真正的交換，只是在劃分完成時才將它放入正確的位置上。初始關(guān)鍵字 49 38 65 97 76 13 27 49 i jj向左掃描 49 38 65 97 76

20、13 27 49 i j第一次交換后 27 38 65 97 76 13 49 i ji向右掃描 27 38 65 97 76 13 49 i j第二次交換后 27 38 97 76 13 65 49 i jj向左掃描，位置不變 第三次交換后 27 38 13 97 76 65 49 i向左掃描，位置不變， i j第四次交換后 27 38 13 76 97 65 49 i jj 向左掃描 27 38 13 49 76 97 65 49 i j初始關(guān)鍵字： 49 38 65 97 76 13 27 49一趟排序之后： 27 38 13 49 76 97 65 49二趟排序之后： 13 27 38

21、 49 49 65 76 97三趟排序之后： 13 27 38 49 49 65 76 97 最后的排序結(jié)果： 13 27 38 79 79 65 76 97(b) 各趟排序之后的狀態(tài) 最壞情況是第次劃分選取的基準都是當前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，劃分的基準左邊的無序子區(qū)為空（或右邊的無序子區(qū)為空），而劃分所得的另一個非空的無序子區(qū)中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。因此，快速排序必須做n-1趟，每一趟中需進行n-i次比較，故總手工藝比數(shù)次數(shù)達到最大值： Cmax= (n-i)=n(n-1)/2=O(n2)顯然，如果按上面給出的劃分算法，每次取當前無序區(qū)的第1個記錄為

22、基準，那么當文件的記錄已按遞增序（或遞減序）排列時，每次劃分所取的基準就是當前無序區(qū)中關(guān)鍵字最小（或最大）的記錄，則快速排序所需的比較次數(shù)反而最多。在最好情況下，每次劃分所取的基準都是當前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準的左、右兩個無序子區(qū)的長度大致相等地。設(shè)C（n）表示對長度為n的文件進行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對長度為n的無序區(qū)進行劃分所需的比較次數(shù)n-1。加上遞歸地對劃分所得的左、右兩個無序子區(qū)（長度n/2）進行快速排序所需的比較總?cè)藬?shù)。 假設(shè)文件長度n=2k，那么總的比較次數(shù)為：C(n) n+2C(n/2) n+2n/2+2C(n/22)=2n+4C(n/22)

23、2n+4n/4+2C(n/23)=3n+8C(n/23) kn+2kC(n/2k)=nlog2n+nC(1) =O(nlog2n)注意：式中C（1）為一常數(shù)，k=log2n。 ，因為快速排序的記錄移動次數(shù)不大于比較的次數(shù)，所以，快速排序的最壞時間復(fù)雜度應(yīng)為O（n2），最好時間復(fù)雜雅興O(log2n)。為了改善最壞情況下的時間性能，可采用三者取中的規(guī)則，即在每一趟劃分開始前，首先比較R1.key，Rh.key和R(1+h)/2.key，令三者中取中值的記錄和R1交換之。可以證明：快速排序的平均時間復(fù)雜度也是O(nlog2n)，它是目前基于比較的內(nèi)部排序方法 中速度最快的，快速排序亦因此而得名。

24、快速排序需要一個?？臻g來實現(xiàn)遞歸。若每次劃分均能將文件均勻分割為兩部分，則棧的最大深度為log2n+1，所需?？臻g為O（log2n）。最壞情況下，遞歸深度為n，所需?？臻g為O（n)?？焖倥判蚴遣环€(wěn)定的，請讀者自行檢驗。 歸并排序歸并排序 歸并排序(Merge Sort)是利用“歸并”技術(shù)來進行排序，所謂歸并是指將若干個已排序的子文件合并成一個有序的文件。簡單的歸并是將兩個有序的子文件合并成一個有序的文件。假設(shè)R(low)到Rm和Rm+1到Rhigh是存儲在同一個數(shù)組中且相鄰的兩個有序的子文件，要將它們合并為一個有序文件R1low到R1high，只要設(shè)置三個指示器i，j和k，其初值分別是這三個記

25、錄區(qū)的起始位置。合并時依次比較Ri和Rj的關(guān)鍵字，取關(guān)鍵字較小的記錄復(fù)制到R1k中，然后，將指向被復(fù)制記錄的指示器加1和指向復(fù)制位置的指示器K加1，重復(fù)這一過程，直至全部記錄被復(fù)制到R1low到R1high中為止。 基數(shù)排序基數(shù)排序 前介紹的排序方法都是根據(jù)關(guān)鍵字值的大小來進行排序的。本節(jié)介紹的方法是按組成關(guān)鍵字的各個位的值來實現(xiàn)的排序的，這種方法稱為基數(shù)排序（radix sort）。采用基數(shù)排序法需要使用一批桶（或箱子），故這種方法又稱為桶排序列。下面以十進制數(shù)為例來說明基數(shù)排充的過程。假定待排序文件中所有記錄的關(guān)鍵字為不超過d位的非負整數(shù)，從最高位到最低位（個位）的編號依次為1，2，d。設(shè)

26、置10個隊列（即上面所說的桶），它們的編號分別為0，1，2，9。當?shù)谝槐閽呙栉淖謺r，將記錄按關(guān)鍵字的個位（即第d位）數(shù)分別放到相應(yīng)的隊列中：個位數(shù)為0的關(guān)鍵字，其記錄依次放入0號隊列中i個位數(shù)為1的關(guān)鍵字，其記錄放入1號隊列中；個位數(shù)為9的關(guān)鍵字，其記錄放入9號隊列中。這一過程叫做按個位數(shù)分配。現(xiàn)在把這10個隊列中的記錄，按0號，1號，9號隊列的順序收集和排列起來，同一隊列中的記錄按先進先出的次序排列。這是第1遍。第2遍排序使用同樣的辦法，將第1遍排序后的記錄按其關(guān)鍵字的十位數(shù)（第d1位）分配到相應(yīng)的隊列中，再把隊列中的記錄收集和排列起來。繼續(xù)進行下去。第d遍排序時，按第d1遍排序后記錄的關(guān)鍵

27、字的最高位（第1位）進行分配，再收集和排列各隊列中的記錄，醫(yī)得到了原文件的有序文件，這就是以10為基的關(guān)鍵字的基數(shù)排序法。 關(guān)鍵字1022773704545646217558119381021初始狀態(tài)7021,11,210254,6455773870211121025464557738021121,213854,556470,770211212138545564707710個隊列關(guān)鍵字第一遍，按個位數(shù)分配收集后收集后第二遍，按十位數(shù)分配例如，給出關(guān)鍵字序列（02，77，70，54，64，21，55，11，38，21），其中關(guān)鍵字02用1個0在2的前面補足到2位，余關(guān)鍵字均為2位的正整數(shù)。進行基

28、數(shù)排序的過程如圖9-9所示。在這個例子中，文件和所有的隊列都表示成向量（一維數(shù)組）。顯然，關(guān)鍵字的某一位有可能均為同一個數(shù)字（例如，個數(shù)都為0），這時所有的記錄都同時裝入同一個隊列中（例如，同時裝入0號隊列中）。因此，如果每個隊列的大小和文件大小相同，則需要一個10倍于文件大小的附加空間。此外，排序時需要進行反復(fù)的分配和收集記錄。所以，采用順序表示是不方便的。基數(shù)排序所需的計算時間不僅與文件的大小n有關(guān)，而且還與關(guān)鍵字的位數(shù)、關(guān)鍵字的基有關(guān)。設(shè)關(guān)鍵字的基為r（十進制數(shù)的基為10，二進制數(shù)的基為2），為建立r個空隊列所需的時間為O（r）。把n個記錄分放到各個隊列中并重新收集起來所需的時間為O（n

29、），因此一遍排序所需的時間為O（n+r）。若每個關(guān)鍵字有d位，則總共要進行d遍排，所以基數(shù)排序的時間復(fù)雜度為O（d（n+r）。由于關(guān)鍵字的位數(shù)d直接與基數(shù)r以及最大關(guān)鍵字的值有關(guān)，因此不同的r和關(guān)鍵字將需要不同的時間。 在已介紹的上述各種內(nèi)部排序方法中，就所需要的計算時間來看，快速排序、歸并排序、堆排序是很好的方法。但是，歸并排序需要大小為n的輔助空間，快速排序需要一個?？铡３丝焖倥判?、堆排序、選擇排序不穩(wěn)定外，基它排序方法都是穩(wěn)定的。評價一個排序算法性能好壞的主要標準是它所需的計算時間和存儲空間。影響計算時間的兩個景要因素是比較關(guān)鍵字的次數(shù)和記錄的移動次數(shù)。在實際應(yīng)用中，究竟應(yīng)該選用何種排

30、序方法，取決于具體的應(yīng)用和機器條件。 外部排序外部排序 外部排序基本上由兩個相對獨立的階段組成。首先，按可用內(nèi)存大小，將外存上含n個記錄的文件分成若干長度為l的子文件或段（segment），依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對它們進行排序，并將排序后得到的有序子文件重新寫入外存，通常稱這些有序子文件為歸并段或順串（run）；然后，對這些歸并段進行逐趟歸并，使歸并段（有序的子文件）逐漸由小至大，直至得到整個有序文件為止。顯然，第一階段的工作是上一章已經(jīng)討論過的內(nèi)容。本章主要討論第二階段即歸并的過程。先從一個具體例子來看外排中的歸并是如何進行的？假設(shè)有一個含10000個記錄的文件，首先通過10次

31、內(nèi)部排序得到10個初始歸并段R1R10，其中每一段都含1000個記錄。然后對它們作如下圖所示的兩兩歸并，直至得到一個有序文件為止。 將兩個有序段歸并成一個有序段的過程，若在內(nèi)存進行，則很簡單，上一章中的merge過程便可實現(xiàn)此歸并。但是，在外部排序中實現(xiàn)兩兩歸并時，不僅要調(diào)用merge過程，而且要進行外存的讀/寫，這是由于我們不可能將兩個有序段及歸并結(jié)果段同時存放在內(nèi)存中的緣故。在11.1節(jié)中已經(jīng)提到，對外存上信息的讀/寫是以“物理塊”為單位的。假設(shè)在上例中每個物理塊可以容納200個記錄，則每一趟歸并需進行50次“讀”和50次“寫”，四趟歸并加上內(nèi)部排序時所需進行的讀/寫使得在外排中總共需進行

32、500次的讀/寫。一般情況下，外部排序所需總的時間=內(nèi)部排序（產(chǎn)生初始歸并段）所需的時間 m*tIS+外部信息讀寫的時間 d*tIO （11-1）+內(nèi)部歸并所需的時間 s*utmg其中：tIS是為得到一個初始歸并段進行內(nèi)部排序所需時間的均值；tIO是進行一次外存讀/寫時間的均值；utmg是對u個記錄進行內(nèi)部歸并所需時間；m為經(jīng)過內(nèi)部排序之后得到的初始歸并段的個數(shù)；s為歸并的趟數(shù)；d為總的讀/寫次數(shù)。 其中tIO取決于所用的外部設(shè)備，顯然，tIO較tmg要大得多。因此，提高外排的效率應(yīng)主要著眼于減少外存信息讀寫的次數(shù)d。下面來分析d和“歸并過程”的關(guān)系。若對上例中所得的10個初始歸并段進行5-路

33、平衡歸并（即每一趟將5個或5個以下的有序子文件歸并成一個有序子文件），則從下圖可見，僅需進行二趟歸并，外排時總的讀/寫次數(shù)便減至2*100+100=300，比2-路歸并減少了200次的讀/寫。R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2有序文件可見，對同一文件而言，進行外排時所需讀/寫外存的次數(shù)和歸并的趟數(shù)s成正比。而在一般情況下，對m個初始歸并段進行k-路平衡歸并時，歸并的趟數(shù) s = logkm 可見，若增加k或減少m便能減少s。 各種排序方法的比較各種排序方法的比較 迄今為止，已有的排序方法遠遠不止本章討論的這些方法，人們之所以熱衷于研究多種排序方法，不僅是由于排序在計算機中所處的重要地位，而且還因為不同的方法各有其優(yōu)缺點，可適用于不同的場合。選取排序方法時需要考慮的因素有：待排序的記錄數(shù)目n；記錄本身信息量的大小；關(guān)鍵字的結(jié)構(gòu)及分布情況；對排序穩(wěn)定性的要求；語言工具的條件，輔助空間的大小等。依據(jù)這些因素，可得出如下幾點結(jié)論：（1）若n較?。ㄆ┤鏽50)，可采用直接插入排序或直接選。由于直接插入排序所需記錄移動操作較直接選擇排序多，因此若記錄本身信息量較大時，則選用直接選擇排序為宜。（2）若文件的初始狀態(tài)已是按關(guān)鍵字基本有序，則選用直接插入排序泡排序為宜。（3）若N較大，則應(yīng)采用時間復(fù)雜度為的排序方