【正文】 (j=0。 jRADIX。 j++) /* 各隊列初始化為空 */ { q[j].f=0。 q[j].e=0。 } p=R[0].next。 /*鏈表的頭指針 */ while( p) {j=R[p].keys[i]。 /*取當前記錄關(guān)鍵碼的第 i位，準備入隊 */ if(!q[j].f) q[j].f=p。 /*第 j隊為空時 ,則該結(jié)點是該隊列的第 1個記錄入隊需改變頭指針 */ else R[q[j].e].next=p。/*非空時，將 p所指的結(jié)點插入到第 j個隊列的隊尾 */ q[j].e=p。 /*j隊列的尾指針指向新紀錄 */ p=R[p].next； } } (2)【 算法 916】 收集算法 :是將按關(guān)鍵碼位的大小形成的各個隊列依次鏈接起來。 void Collect(SNodeType R[ ], Q_Node q[ ]) { /*將 q[0]...q[RADIX1]各個隊列收集在一起，鏈接成一個鏈表頭指針放R[0].next */ int j=0。 /*從第 0個隊開始 */ while(q[j].f==0) j++。 /*找第 1個非空隊列 */ R[0].next=q[j].f。 /*第一個非空隊列的第一個記錄將是收集后的第 1個記錄，由 R[0].next指向 */ t=q[j].e。 /*t指向第一個非空隊列的尾結(jié)點 */ while(jRADIX) /*當沒有收集完 */ {j++。 while( jRADIX1)amp。amp。q[j].f==0) j++。 /*找不是最后一個隊列的下一個非空子表 */ if(q[j].f!=0) /*鏈接兩個非空子表 */ {R[t].next=q[j].f。 t=q[j].e。 /*t指向剛剛鏈接隊列的尾結(jié)點 */ } } R[t].next=0。 /*設置最后一個結(jié)點的空指針 */ } (3)【 算法 917】 基數(shù)排序算法 void RadixSort(SNodeType R[ ], int n) { /*排序表中的各記錄存儲在靜態(tài)鏈表 R[1].. R[n]中， R[0]為頭結(jié)點， R[0].next指向第 1個記錄 ,每個記錄的關(guān)鍵碼在R[i].keys[RADIX1].. R[i].keys[0]中 */ Q_Node q[RADIX ]。 /*定義 RADIX個隊列 */ for(i=0。 in。 i++) R[i].next=i+1。 /*按照原存儲順序鏈接成靜態(tài)鏈表 */ R[n].next=0。 for(i=0。 iKEY_NUM。 i++) /*按最低位優(yōu)先依次對各關(guān)鍵碼分配和收集 */ {Distribute(R, i, q)。 /*第 i趟分配 */ Collect(R, q)。 /*第 i趟收集 */ } } 效率分析 時間效率： 設待排序列為 n個記錄 ， d個關(guān)鍵碼 ， 關(guān)鍵碼的取值范圍為 radix， 則進行鏈式基數(shù)排序的時間復雜度為O(d(n+radix))， 其中 ， 一趟分配時間復雜度為 O(n)， 一趟收集時間復雜度為 O(radix)， 共進行 d趟分配和收集 。 空間效率： 需要 2*radix個指向隊列的輔助空間 ， 以及用于靜態(tài)鏈表的 n個指針 。 外排序 外部排序的方法 外部排序基本上由兩個相互獨立的階段組成 。 首先 ， 按可用內(nèi)存大小 ， 將外存上含 n個記錄的文件分成若干長度為 k的子文件或段 (segment)， 依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對它們進行排序 ， 并將排序后得到的有序子文件重新寫入外存 。 通常稱這些有序子文件為歸并段或順串；然后 ， 對這些歸并段進行逐趟歸并 ， 使歸并段 (有序子文件 )逐漸由小到大 ， 直至得到整個有序文件為止 。 顯然 ， 第一階段的工作已經(jīng)討論過 。 以下主要討論第二階段即歸并的過程 。 先從一個例子來看外排序中的歸并是如何進行的 ？ R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1’ R2’ R3’ R4’ R5’ R1’’ R2’’ R5’’ R1’’’ R5’’’ 有序文件 假設有一個含 10000 個記錄的文件，首先通過 10次內(nèi)部排序得到 10個初始歸并段 R1～ R10 ，其中每一段都含 1000個記錄。然后對它們作如下圖所示的兩兩歸并，直至得到一個有序文件為止。 從上面的圖中可見，由 10個初始歸并段到一個有序文件，共進行了四趟歸并，每一趟從 m個歸并段得到 個歸并段。 ? ?2/m 將兩個有序段歸并成一個有序段的過程 ， 若在內(nèi)存中進行 ，則很簡單 ， 前面討論的 2路歸并排序中的 Merge函數(shù)便可實現(xiàn)此歸并 。 但是 ， 在外部排序中實現(xiàn)兩兩歸并時 ， 不僅要調(diào)用 Merge函數(shù) ， 而且要進行外存的讀 /寫 ， 這是由于我們不可能將兩個有序段及歸并結(jié)果同時放在內(nèi)存中的緣故 。 對外存上信息的讀 /寫是以 “ 物理塊 ” 為單位 。 假設在上例中每個物理塊可以容納 200個記錄 ， 則每一趟歸并需進行 50次 “ 讀 ” 和 50次 “ 寫 ” ， 四趟歸并加上內(nèi)部排序時所需進行的讀 /寫 ， 使得在外排序中總共需進行 500次的讀 /寫 。 這種方法稱為 2路平衡歸并 。 一般情況下 ， 外部排序所需總時間 = 內(nèi)部排序 (產(chǎn)生初始歸并段 )所需時間 m*tis +外存信息讀寫的時間 d*tio +內(nèi)部歸并排序所需時間 s*utmg 其中： tis是為得到一個初始歸并段進行的內(nèi)部排序所需時間的均值； tio是進行一次外存讀 /寫時間的均值； utmg是對 u個記錄進行內(nèi)部歸并所需時間； m為經(jīng)過內(nèi)部排序之后得到的初始歸并段的個數(shù)； s為歸并的趟數(shù)； d為總的讀 /寫次數(shù) 。 由此 ， 上例10000個記錄利用 2路歸并進行排序所需總的時間為： 10*tis+500*tio+4*10000tmg 其中 tio取決于所用的外存設備 ， 顯然 ， tio較 tmg要大的多 。 因此 ， 提高排序效率應主要著眼于減少外存信息讀寫的次數(shù) d。 下面來分析 d和 “ 歸并過程 ” 的關(guān)系 。 若對上例中所得的 10個初始歸并段進行 5平衡歸并 (即每一趟將 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ù) ? ?msklo g? 可見 ， 若增加 k或減少 m便能減少 s。 下面分別就這兩個方面討論之 。 多路平衡歸并的實現(xiàn) 從上式可見 ， 增加 k可以減少 s， 從而減少外存讀 /寫的次數(shù) 。但是 ， 從下面的討論中又可發(fā)現(xiàn) ， 單純增加 k將導致增加內(nèi)部歸并的時間 utmg。 那末 ， 如何解決這個矛盾呢 ？ (1)先看 2路歸并 。 令 u個記錄分布在兩個歸并段上 ， 按Merge函數(shù)進行歸并 。 每得到歸并后的含 u個記錄的歸并段需進行 u1次比較 。 (2)再看 k路歸并 。 令 u個記錄分布在 k個歸并段上 ， 顯然 ，歸并后的第一個記錄應是 k個歸并段中關(guān)鍵碼最小的記錄 ， 即應從每個歸并段的第一個記錄的相互比較中選出最小者 ， 這需要進行 k1次比較 。 同理 ， 每得到歸并后的有序段中的一個記錄 ，都要進行 k1次比較 。 顯然 ， 為得到含 u個記錄的歸并段需進行(u1)(k1)次比較 。 由此 ， 對 n個記錄的文件進行外部排序時 ，在內(nèi)部歸并過程中進行的總的比較次數(shù)為 s(k1)(n1)。 假設所得初始歸并段為 m個 ， 則可得內(nèi)部歸并過程中進行比較的總的次數(shù)為 : ? ? mgmgk tnkkmtnkm )1)(1(l o gl o g)1)(1(l o g22 ???????????由于 kk2log1?隨 k的增加而增長 ， 則內(nèi)部歸并時間亦隨 k的增加 而增長 。 這將抵消由于增大 k而減少外存信息讀寫時間所得效益 ， 這是我們所不希望的 。 然而 ， 若在進行 k路歸并時利用“ 敗者樹 ” (Tree of Loser)， 則可使在 k個記錄中選出關(guān)鍵碼最小的記錄時僅需進行 ? ?k2log 次比較 ， 從而使總的歸并時間變?yōu)?: ? ? mgtnm )1(lo g 2 ? 顯然 ， 這個式子和 k無關(guān) ， 它不再隨 k的增長而增長 。 (3)“敗者樹 ” : 是樹形選擇排序的一種變型。相對地，我們可稱圖 88的中二叉樹為 “ 勝者樹 ” ，因為每個非終端結(jié)點均表示其左、右子女結(jié)點中 “ 勝者 ” 。反之，若在雙親結(jié)點中記下剛進行完的這場比賽中的敗者，而讓勝者去參加更高一層的比賽，便可得到一棵 “ 敗者樹 ” 。 0 2 9 20 10 3 1 4 6 15 25 12 37 48 10 15 16 9 18 20 20 22 40 12 6 Ls[4] Ls[2] Ls[1] Ls[3] Ls[0] b3 b4 b0 b1 b2 4 2 9 20 10 1 0 3 15 25 12 37 48 10 15 16 9 18 20 20 22 40 12 15 Ls[4] Ls[2] Ls[1] Ls[3] Ls[0] b3 b4 b0 b1 b2 (4) 5路歸并的敗者樹 圖 (a)即為一棵實現(xiàn) 5路歸并的敗者樹 ls[0… 4]，圖中方形結(jié)點表示葉子結(jié)點 (也可看成是外結(jié)點 )，分別為 5個歸并段中當前參加歸并的待選擇記錄的關(guān)鍵碼；敗者樹中根結(jié)點ls[1]的雙親結(jié)點 ls[0]為 “ 冠軍 ” ，在此指示各歸并段中的最小關(guān)鍵碼記錄為第三段中的記錄；結(jié)點 ls[3]指示 b1和 b2兩個葉子結(jié)點中的敗者即是 b2，而勝者 b1和 b3(b3是葉子結(jié)點 bb4和 b0經(jīng)過兩場比賽后選出的獲勝者 )進行比較，結(jié)點 ls[1]則指示它們中的敗者為 b1。 在選得最小關(guān)鍵碼的記錄之后，只要修改葉子結(jié)點 b3中的值，使其為同一歸并段中的下一個記錄的關(guān)鍵碼，然后從該結(jié)點向上和雙親結(jié)點所指的關(guān)鍵碼進行比較，敗者留在該雙親，勝者繼續(xù)向上直至樹根的雙親。如圖 (b)所示。當?shù)?3個歸并段中第 2個記錄參加歸并時，選得最小關(guān)鍵碼記錄為第一個歸并段中的記錄。為了防止在歸并過程中某個歸并段變?yōu)榭?，可以在每個歸并段中附加一個關(guān)鍵碼為最大的記錄。當選出的 “ 冠軍 ” 記錄的關(guān)鍵碼為最大值時，表明此次歸并已完成。 小結(jié) 排序也是數(shù)據(jù)處理中經(jīng)常出現(xiàn)的一種操作。排序分為內(nèi)排序和外排序，內(nèi)排序是將待排序記錄全部存在內(nèi)存的排序，外排序是對存放在外存的大型文件的排序，外排序基于對有序歸并段的歸并，而初始歸并段的產(chǎn)生又基于內(nèi)排序。 本章所介紹的各種內(nèi)排序的方法，根據(jù)排序所依據(jù)的基本思想，把排序分為插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序。其中，前三種又都包括簡單排序如直接插入排序、冒泡排序和直接選擇排序和由它們改進的排序方法，如希爾排序、快排序、堆排序等。 要求讀者掌握各種內(nèi)部排序方法的基本思想、時間和空間復雜度和排序的穩(wěn)定性情況。表 81給出了幾種排序算法性能的比較。 表 91幾種內(nèi)部排序方法的比較