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

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

2、第2遍，將R3插入前面的兩個(gè)記錄的有序子文件中，得到3個(gè)記錄的有序子文件。依此類推，繼續(xù)進(jìn)行下去，直到將Rn插入到前面的n-1個(gè)記錄的有序子文件中，最后得到n個(gè)記錄的有序文件。 線性插入排序的基本思想是：第1遍，將初始文件中的記錄R1看作有序子文件，將R2插入這個(gè)子文件中。若R2的關(guān)鍵字小于R1的關(guān)鍵字，則R2插在R1的前面，否則R2插在R1的后面。第2遍，將R3插入前面的兩個(gè)記錄的有序子文件中，得到3個(gè)記錄的有序子文件。依此類推，繼續(xù)進(jìn)行下去，直到將Rn插入到前面的n-1個(gè)記錄的有序子文件中，最后得到n個(gè)記錄的有序文件。圖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后移一個(gè)位置，否則停止比較和移動(dòng)；最后，將Ro（即原來待插入的記錄Ri）移到j(luò)+1的位置上。由于Ri的前面有監(jiān)視哨Ro，因此不必每次判斷下標(biāo)j是否出界。算法描述如下： void insertsort(struct node r n+1,int n)/* rn+1為一維數(shù)組，其中r0為監(jiān)視哨，r1到rn為待排序的n個(gè)記錄，排序好的記錄仍放在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進(jìn)行折半插入排序 */ 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; 在上面的算法中，每插入一個(gè)R1，平均比較次數(shù)為log2i。 希爾排序希爾排序 希爾排序（Shells Method）又稱“縮小增量排序”（Diminishing Increment Sort），是由D.L.Shell在1959年提出來的。它的作法是：先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組，所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序；然后，到第二個(gè)增量d2d1重復(fù)上述分組和排序，直至所取的增量dt=1（dtdt-1d2d1），即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。先從一個(gè)具體的例子來看希爾排序。假設(shè)待排序文件有10個(gè)記錄，

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

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

8、2h，R3h，），因?yàn)楦鹘M中記錄之間的距離均為是h，故第1組至第h組的哨兵位置依次為1-h，2-h，0。如果象直接插入排序算法那樣，將待插入記錄Ri（h+1iN） 在查找插入位置之前保存到監(jiān)視哨中，那么必須先計(jì)Ri屬于哪一組，才能決定使用哪個(gè)監(jiān)視哨來保存Ri。為了避免這種計(jì)算，我們可以將Ri保存到另一個(gè)輔肋記錄X中，而將所有監(jiān)視哨R1-h，R2-h，R0的關(guān)鍵字，設(shè)置為小于文件中的任何關(guān)鍵字即可。因?yàn)樵隽渴亲兓?，所以，各趟排序中所需的監(jiān)視哨數(shù)目也不相同，但是我們可以按最大增量d1來設(shè)置監(jiān)視哨。 rectype Rn+d1； /* Rd1-1為d1個(gè)監(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； /*機(jī)器中最大整數(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插入當(dāng)前有序區(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*/讀者可能看出，當(dāng)增量h=1時(shí)，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。為什么希爾排序的時(shí)間性能優(yōu)于直接插入排序呢？我們知道直接插入排序在文件初態(tài)為正序時(shí)所需要時(shí)間最少，實(shí)際上，當(dāng)文件初基本有序時(shí)直接插入排序所需的比較和移動(dòng)次數(shù)均較少。另一面，當(dāng)n值較小時(shí)，n和n2的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度O(n2)差別不大。在希爾排序時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較近于有序狀態(tài)，所以新的國趟排序過程也較快。因此，希爾排序在較率上較直接接入排序有較大的改進(jìn)。希爾排序是不穩(wěn)定的。參見圖9-2的例

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

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

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

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

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

17、置。這時(shí)，新的根結(jié)點(diǎn)60的右子樹沒有改變，仍然是一個(gè)堆。但是，由于結(jié)點(diǎn)30下沉到左子樹的根上，使得左子樹有可能不再是堆了。按照上面所用的辦法，把這棵子樹調(diào)整為一個(gè)堆，顯然，結(jié)點(diǎn)30的左、右子樹原來都是堆，30的左、右子樹分別是40，45。由于4030，于是應(yīng)交換結(jié)點(diǎn)30和右孩子45的位置。 void adjust(struct node rm+1,int m) /* 將文件(r1,r2,rm)解釋為一棵順序二叉樹,將其中以ri為根結(jié)點(diǎn)的二叉樹調(diào)整 為一個(gè)堆,設(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個(gè)關(guān)鍵字小于temp.key的記錄*/ if(ij) Ri+=Rj; /*交換Ri和Rj*/ while(Ri.key=temp.key) & (ij) i+; /*從左向左掃描，查找第1個(gè)關(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) /* 只有一個(gè)記錄或無記錄須排序*/ i= partition (R,s1,t1); /*對Rs1到Rt1做劃分*/ quicksort (R,s1,i-1); /*遞歸處理左區(qū)間*/ quicksort (R,i+1,t1); /*遞歸處理右區(qū)間*/ 圖9-7展示了一次劃分的過程及整個(gè)快速排序的過程。圖中方括號(hào)表示無序區(qū)，方框表示基準(zhǔn)temp的關(guān)鍵字，它未參加真正的交換，只是在劃分完成時(shí)才將它放入正確的位置上。初始關(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) 最壞情況是第次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，劃分的基準(zhǔn)左邊的無序子區(qū)為空（或右邊的無序子區(qū)為空），而劃分所得的另一個(gè)非空的無序子區(qū)中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個(gè)數(shù)減少一個(gè)。因此，快速排序必須做n-1趟，每一趟中需進(jìn)行n-i次比較，故總手工藝比數(shù)次數(shù)達(dá)到最大值： Cmax= (n-i)=n(n-1)/2=O(n2)顯然，如果按上面給出的劃分算法，每次取當(dāng)前無序區(qū)的第1個(gè)記錄為

22、基準(zhǔn)，那么當(dāng)文件的記錄已按遞增序（或遞減序）排列時(shí)，每次劃分所取的基準(zhǔn)就是當(dāng)前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?，則快速排序所需的比較次數(shù)反而最多。在最好情況下，每次劃分所取的基準(zhǔn)都是當(dāng)前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準(zhǔn)的左、右兩個(gè)無序子區(qū)的長度大致相等地。設(shè)C（n）表示對長度為n的文件進(jìn)行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對長度為n的無序區(qū)進(jìn)行劃分所需的比較次數(shù)n-1。加上遞歸地對劃分所得的左、右兩個(gè)無序子區(qū)（長度n/2）進(jìn)行快速排序所需的比較總?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。 ，因?yàn)榭焖倥判虻挠涗浺苿?dòng)次數(shù)不大于比較的次數(shù)，所以，快速排序的最壞時(shí)間復(fù)雜度應(yīng)為O（n2），最好時(shí)間復(fù)雜雅興O(log2n)。為了改善最壞情況下的時(shí)間性能，可采用三者取中的規(guī)則，即在每一趟劃分開始前，首先比較R1.key，Rh.key和R(1+h)/2.key，令三者中取中值的記錄和R1交換之?？梢宰C明：快速排序的平均時(shí)間復(fù)雜度也是O(nlog2n)，它是目前基于比較的內(nèi)部排序方法 中速度最快的，快速排序亦因此而得名。

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

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

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

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

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

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

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

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

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

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