【正文】 s m m+1 t R1: 18 25 37 38 46 46 75 78 80 s t 【 算法 911】 兩個(gè)有序表的合并 void Merge(datatype R[ ], datatype R1[ ], int s, int m , int t) { /*設(shè)兩個(gè)有序子表 R[s]..R[m]和 R[m+1]..R[t] */ /*將兩個(gè)有序子表合并為一個(gè)有序表 R1[s]..R1[t]*/ i=s。 k=s。amp。 else R1[k++]=R[j++]。 while (j=t) R1[k++]=R[j++]。 2. 2路歸并算法 2路歸并的基本思想是：只有 1個(gè)元素的表總是有序的，所以將排序表 R[1..n]，看作是 n個(gè)長(zhǎng)度為 len=1的有序子表，對(duì)相鄰的兩個(gè)有序子表兩兩合并到 R1[1..n]，使之生成表長(zhǎng) len=2的有序表；再進(jìn)行兩兩合并到 R[1..n]中， … ，直到最后生成表長(zhǎng) len=n的有序表。 56 47 69 48 27 98 56 59 38 28 66 47 56 48 69 27 98 56 59 28 38 66 47 48 56 69 27 56 59 98 28 38 66 27 47 48 56 56 59 69 98 28 38 66 27 28 38 47 48 56 56 59 66 69 98 【 算法 912】 一趟歸并算法 void MergePass(datatype R[ ], datatype R1[ ], int len, int n) {/*len是本趟歸并中有序表的長(zhǎng)度，從 R[1]..R[n]歸并到 R1[1]..R1[n]中 */ for(i=1。 i=i+2*len) Merge(R, R1, i, i+len1, i+2*len1)。 /*一組半的情況 */ else if(i=n) while(i=n) R1[i++]=R[i++]。 while(lenn) { MergePass(R,R1,len,n)。 MergePass(R1,R ,len,n)。 else {m=(s+t)/2。 /*遞歸地將 R[s…m] 歸并為有序的 R1[s…m]*/ MSort(R, R1, m+1, t)。 /*將 R1[s…m] 和 R1[m+1…t] 歸并到 R[s…t]*/ } } void MergeSort(datatype R[ ], datatype R1[ ], int n) {/*對(duì)排序表 R[1]..R[n]作歸并排序 */ MSort(R, R1,1, n)。 對(duì) n個(gè)元素的表 ， 將這 n個(gè)元素看作葉結(jié)點(diǎn) ， 若將兩兩歸并生成的子表看作它們的父結(jié)點(diǎn) ， 則歸并過(guò)程對(duì)應(yīng)由葉向根生成一棵二叉樹(shù)的過(guò)程 。 第 9章 排序 基本概念 插入排序 交換排序 選擇排序 歸并排序 分配排序（基數(shù)排序） 基數(shù)排序是一種借助于多關(guān)鍵碼排序的思想 ， 是將單關(guān)鍵碼按基數(shù)分成 “ 多關(guān)鍵碼 ” 進(jìn)行排序的方法 。 為得到排序結(jié)果 ， 我們討論兩種排序方法 。 再對(duì)每個(gè)組分別按面值進(jìn)行排序 ，最后 ， 將 4個(gè)組連接起來(lái)即可 。 再按花色給出 4個(gè)編號(hào)組 (梅花 、 方塊 、 紅心 、 黑心 )， 將 2號(hào)組中牌取出分別放入對(duì)應(yīng)花色組 ， 再將 3號(hào)組中牌取出分別放入對(duì)應(yīng)花色組 ， …… ， 這樣 ， 4個(gè)花色組中均按面值有序 ， 然后 ，將 4個(gè)花色組依次連接起來(lái)即可 。 將關(guān)鍵碼拆分為若干項(xiàng) ， 每項(xiàng)作為一個(gè) “ 關(guān)鍵碼 ” ， 則對(duì)單關(guān)鍵碼的排序可按多關(guān)鍵碼排序方法進(jìn)行 。 由于這樣拆分后 ， 每個(gè)關(guān)鍵碼都在相同的范圍內(nèi) (對(duì)數(shù)字是 0～ 9， 字符是‘ a’～ ‘ z’)， 稱這樣的關(guān)鍵碼可能出現(xiàn)的符號(hào)個(gè)數(shù)為 “ 基 ” ，記作 RADIX。 基于這一特性 ， 用 LSD法排序較為方便 。 如此重復(fù) d次即可 。 示例 99：以靜態(tài)鏈表存儲(chǔ)待排記錄 ， 頭結(jié)點(diǎn)指向第一個(gè)記錄 。 278 109 063 930 589 184 505 269 008 083 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 269 589 109 008 278 505 184 083 063 930 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (a)初始記錄的靜態(tài)鏈表 (b)第一趟按個(gè)位數(shù)分配，修改結(jié)點(diǎn)指針域， 將鏈表中的記錄分配到相應(yīng)鏈隊(duì)列中 930 063 083 184 505 278 008 109 589 269 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 589 184 083 930 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (c)第一趟收集：將各隊(duì)列鏈接起來(lái)，形成單鏈表 (d)第一趟按十位數(shù)分配，修改結(jié)點(diǎn)指針域， 將鏈表中的記錄分配到相應(yīng)鏈隊(duì)列中 109 008 505 269 063 278 505 008 109 930 063 269 278 083 184 589 (e)第二趟收集：將各隊(duì)列鏈接起來(lái)，形成單鏈表 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (f)第一趟按百位數(shù)分配，修改結(jié)點(diǎn)指針域， 將鏈表中的記錄分配到相應(yīng)鏈隊(duì)列中 083 063 008 589 505 930 008 063 083 109 184 269 278 505 589 930 (g)第三趟收集：將各隊(duì)列鏈接起來(lái)，形成單鏈表。 184 109 278 269 數(shù)據(jù)結(jié)構(gòu) 設(shè)采用靜態(tài)鏈表存儲(chǔ)排序表，相關(guān)的數(shù)據(jù)類型定義如下： define MAXNUM … /* MAXNUM 為足夠大的數(shù) */ define KEY_NUM … /*關(guān)鍵碼的位數(shù) */ define RADIX 10 /*關(guān)鍵碼基數(shù)，設(shè)關(guān)鍵碼為十進(jìn)制整數(shù) */ typedef struct { keytype keys[KEY_NUM]； /*關(guān)鍵碼字段 */ … /*其它字段 */ int next； /*指針字段 */ }SNodeType； /*靜態(tài)鏈表結(jié)點(diǎn)類型 */ typedef struct { int f。 } Q_Node。 /* RADIX個(gè)隊(duì)列的頭尾指針向量 */ 算法 (1)【 算法 915】 分配算法 void Distribute(SNodeType R[ ], int i, Q_Node q[RADIX ]) { /*靜態(tài)鏈表 R中的記錄已按關(guān)鍵碼的低 i位有序，現(xiàn)按 kyes[i1]分配到相應(yīng)的隊(duì)列中 ,R[0].next是靜態(tài)鏈表 R的頭指針 ,分配結(jié)束后， q[j].f和 q[j].e分別是第 j個(gè)隊(duì)列的頭尾指針 */ for(j=0。 j++) /* 各隊(duì)列初始化為空 */ { q[j].f=0。 } p=R[0].next。 /*取當(dāng)前記錄關(guān)鍵碼的第 i位，準(zhǔn)備入隊(duì) */ if(!q[j].f) q[j].f=p。/*非空時(shí)，將 p所指的結(jié)點(diǎn)插入到第 j個(gè)隊(duì)列的隊(duì)尾 */ q[j].e=p。 void Collect(SNodeType R[ ], Q_Node q[ ]) { /*將 q[0]...q[RADIX1]各個(gè)隊(duì)列收集在一起，鏈接成一個(gè)鏈表頭指針?lè)臨[0].next */ int j=0。 /*找第 1個(gè)非空隊(duì)列 */ R[0].next=q[j].f。 /*t指向第一個(gè)非空隊(duì)列的尾結(jié)點(diǎn) */ while(jRADIX) /*當(dāng)沒(méi)有收集完 */ {j++。amp。 /*找不是最后一個(gè)隊(duì)列的下一個(gè)非空子表 */ if(q[j].f!=0) /*鏈接兩個(gè)非空子表 */ {R[t].next=q[j].f。 /*t指向剛剛鏈接隊(duì)列的尾結(jié)點(diǎn) */ } } R[t].next=0。 /*定義 RADIX個(gè)隊(duì)列 */ for(i=0。 i++) R[i].next=i+1。 for(i=0。 i++) /*按最低位優(yōu)先依次對(duì)各關(guān)鍵碼分配和收集 */ {Distribute(R, i, q)。 /*第 i趟收集 */ } } 效率分析 時(shí)間效率： 設(shè)待排序列為 n個(gè)記錄 ， d個(gè)關(guān)鍵碼 ， 關(guān)鍵碼的取值范圍為 radix， 則進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+radix))， 其中 ， 一趟分配時(shí)間復(fù)雜度為 O(n)， 一趟收集時(shí)間復(fù)雜度為 O(radix)， 共進(jìn)行 d趟分配和收集 。 外排序 外部排序的方法 外部排序基本上由兩個(gè)相互獨(dú)立的階段組成 。 通常稱這些有序子文件為歸并段或順串；然后 ， 對(duì)這些歸并段進(jìn)行逐趟歸并 ， 使歸并段 (有序子文件 )逐漸由小到大 ， 直至得到整個(gè)有序文件為止 。 以下主要討論第二階段即歸并的過(guò)程 。然后對(duì)它們作如下圖所示的兩兩歸并，直至得到一個(gè)有序文件為止。 ? ?2/m 將兩個(gè)有序段歸并成一個(gè)有序段的過(guò)程 ， 若在內(nèi)存中進(jìn)行 ，則很簡(jiǎn)單 ， 前面討論的 2路歸并排序中的 Merge函數(shù)便可實(shí)現(xiàn)此歸并 。 對(duì)外存上信息的讀 /寫(xiě)是以 “ 物理塊 ” 為單位 。 這種方法稱為 2路平衡歸并 。 由此 ， 上例10000個(gè)記錄利用 2路歸并進(jìn)行排序所需總的時(shí)間為： 10*tis+500*tio+4*10000tmg 其中 tio取決于所用的外存設(shè)備 ， 顯然 ， tio較 tmg要大的多 。 下面來(lái)分析 d和 “ 歸并過(guò)程 ” 的關(guān)系 。 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1’ R2’ 有序文件 可見(jiàn) ， 對(duì)同一文件而言 ， 進(jìn)行外部排序時(shí)所需讀 /寫(xiě)外存的次數(shù)和歸并的趟數(shù) s成正比 。 下面分別就這兩個(gè)方面討論之 。但是 ， 從下面的討論中又可發(fā)現(xiàn) ， 單純?cè)黾?k將導(dǎo)致增加內(nèi)部歸并的時(shí)間 utmg。 令 u個(gè)記錄分布在兩個(gè)歸并段上 ， 按Merge函數(shù)進(jìn)行歸并 。 (2)再看 k路歸并 。 同理 ， 每得到歸并后的有序段中的一個(gè)記錄 ，都要進(jìn)行 k1次比較 。 由此 ， 對(duì) n個(gè)記錄的文件進(jìn)行外部排序時(shí) ，在內(nèi)部歸并過(guò)程中進(jìn)行的總的比較次數(shù)為 s(k1)(n1)。 這將抵消由于增大 k而減少外存信息讀寫(xiě)時(shí)間所得效益 ， 這是我們所不希望的 。 (3)“敗者樹(shù) ” : 是樹(shù)形選擇排序的一種變型。反之，若在雙親結(jié)點(diǎn)中記下剛進(jìn)行完的這場(chǎng)比賽中的敗者，而讓勝者去參加更高一層的比賽，便可得到一棵 “ 敗者樹(shù) ” 。 在選得最小關(guān)鍵碼的記錄之后，只要修改葉子結(jié)點(diǎn) b3中的值，使其為同一歸并段中的下一個(gè)記錄的關(guān)鍵碼，然后從該結(jié)點(diǎn)向上和雙親結(jié)點(diǎn)所指的關(guān)鍵碼進(jìn)行比較，敗者留在該雙親，勝者繼續(xù)向上直至樹(shù)根的雙親。當(dāng)?shù)?3個(gè)歸并段中第 2個(gè)記錄參加歸并時(shí)，選得最小關(guān)鍵碼記錄為第一個(gè)歸并段中的記錄。當(dāng)選出的 “ 冠軍 ” 記錄的關(guān)鍵碼為最大值時(shí)，表明此次歸并已完成。排序分為內(nèi)排序和外排序，內(nèi)排序是將待排序記錄全部存在內(nèi)存的排序，外排序是對(duì)存放在外存的大型文件的排序，外排序基于對(duì)有序歸并段的歸并，而初始?xì)w并段的產(chǎn)生又基于內(nèi)排序。其中，前三種又都包括簡(jiǎn)單排序如直接插入排序、冒泡排序和直接選擇排序和由它們改進(jìn)的排序方法，如希爾排序、快排序、堆排序等。表 81給出了幾種排序算法性能