【正文】 Merge2Sorted(a, i, i+len1, p2, b+k )。 else //剩一段 ,或不剩 for (j=i。 j=p2。 j++) b[k++]=a[j]。 } 顯然 ， 該算法的 執(zhí)行時(shí)間 近似為 s*p/2， 即 O(s*m)。 這里 ， p為段數(shù) ， 而 s為段長(zhǎng) 。 167。 二路歸并排序 有了上面的幾個(gè)算法的支持就可以容易地實(shí)現(xiàn)歸并排序了 。 這種歸并排序稱為二路歸并排序 。 二路歸并排序的基本思想是：如果序列中有 n個(gè)記錄 ， 可以先把它看成 n個(gè)段 ， 每個(gè)段中只包含一個(gè)記錄 ， 因而都是排好序的 。 二路歸并排序是先將從頭起的兩連相鄰的段合并（ 若段數(shù)為奇數(shù) ， 則最后一段照抄 ， 下同 ） ，完成一趟歸并 ， 得到 「 n/2]個(gè)較大的有序段 ， 每個(gè)段包含 2個(gè)記錄 （ 最后一段長(zhǎng)度可能不足 ） 。然后 ， 再進(jìn)行第 2趟歸并 ， 這趟是在上趟的基礎(chǔ)上進(jìn)行 ， 歸并后 ， 得到 「「 n/2]/2]個(gè)有序段 ，每個(gè)段包含 4個(gè)記錄 （ 最后一段長(zhǎng)度可能不足 ） 。如此反復(fù)多趟 ， 直到最后合并成一個(gè)有序段（ 包含了全部記錄 ） ， 排序即告完成 。 例如 ， 設(shè)初始輸入序列為 26， 5， 77， 1， 61， 11， 59， 15， 48， 15， 48， 19 , 6 則對(duì)其采用歸并排序法進(jìn)行排序 ， 其歸并過(guò)程如下 （ 方括號(hào)表示有序段 ， 每行為一趟歸并的結(jié)果 ） ： [26] [5] [77] [1] [ 61] [11] [59] [15] [48] [ 19] [6] [ 5 26 ] [ 1 77 ] [ 11 61 ] [15 59 ] [ 19 48 ] [6] [ 1 5 26 77 ] [11 15 59 61 ] [6 19 48 ] [ 1 5 11 15 26 59 61 77 ] [6 19 48] [ 1 5 6 11 15 19 26 48 59 61 77 ] 應(yīng)用 MMergeSorted()， 可以寫(xiě)出對(duì)包含 n個(gè)記錄的序列進(jìn)行若干趟二路歸并排序算法 。 具體程序如下 。 void SortMerge(int a[], long p1, long p2, int b[]) {//2路歸并排序 ， 將 a[p1]~a[p2]中的元素排序 ， 結(jié)果在 b[0]~b[p2p1]中 long len。 len=1。 while (lenp2p1+1) { MMergeSorted(a, p1, p2, len, b)。 //將 a[p1]~a[p2]中的長(zhǎng)度為 len的相鄰有序段兩兩合并到 b[0]~b[p2p1] len = len*2。 MMergeSorted(b, 0,p2p1, len, a+p1)。 //將 b[0]~a[p2p1]中的長(zhǎng)度為 len的相鄰有序段兩兩合并到 a[p1]~a[p2] } } 粗略地分析一下該算法 。 設(shè)記錄個(gè)數(shù)為 n， 由于每趟都是兩兩合并 （ 2路合并 ） ， 所以 ， 每趟歸并后段長(zhǎng)度都是上次段長(zhǎng)的 2倍 ， 特別地 ， 最后一趟后 ， 段長(zhǎng)變?yōu)?n， 所以 ， 歸并的趟數(shù) m滿足： n/2m=1， 從而 m=log2n. 由于每趟歸并時(shí) ，每個(gè)記錄恰好被輸出一次 ， 所以 ， 每趟歸并的時(shí)間為 n， 從而 ， 完成全部歸并的總時(shí)間代價(jià)為 O（ nlog2n） 。 至于空間復(fù)雜度 ， 顯然需要附加一倍的存儲(chǔ)開(kāi)銷 。 從這方面看 ， 歸并排序并不優(yōu)秀 ， 但是 ， 歸并排序很適合用在外排序中 。另外 ， 二路歸并排序是穩(wěn)定的 。 從另一角度看 ， 二路歸并排序的過(guò)程是一棵二叉樹(shù) 。 初始的 n個(gè)記錄做為 n個(gè)葉子 ， 第 1趟歸并是將這 n個(gè)葉子兩兩歸并 ， 每?jī)蓚€(gè)結(jié)點(diǎn)歸并后的結(jié)果 ， 都分別用一個(gè)新結(jié)點(diǎn)表示 ，該新結(jié)點(diǎn)作為所合并的兩個(gè)結(jié)點(diǎn)的父親 。 下一趟是在上一趟的基礎(chǔ)上按類似方法生成新結(jié)點(diǎn) ， 這樣 ， 最后一趟歸并后 ， 形成根結(jié)點(diǎn) 。 從這里也看出 ， 2路歸并排序速度很快 ，相當(dāng)于二叉樹(shù)的 “ 收縮 ” （ 樹(shù)結(jié)點(diǎn)的生長(zhǎng)的逆方向 ） 。 在 n較大時(shí) ， 歸并排序所需時(shí)間較堆排序省 。 167。 外排排簡(jiǎn)介 在許多實(shí)際應(yīng)用系統(tǒng)中，經(jīng)常遇到要對(duì)數(shù)據(jù)文件中的記錄進(jìn)行排序處理。由于文件中的記錄往往很多、信息量龐大，整個(gè)文件所占據(jù)的存儲(chǔ)單元遠(yuǎn)遠(yuǎn)超過(guò)一臺(tái)計(jì)算機(jī)的內(nèi)存容量。因此，無(wú)法把整個(gè)文件讀入內(nèi)存中進(jìn)行排序。于是，就有必要研究適合于處理大型數(shù)據(jù)文件的排序技術(shù)。通常，這種排序往往需要借助于具有更大容量的外存設(shè)備才能完成。相對(duì)于僅用內(nèi)存進(jìn)行排序（又稱為內(nèi)排序）而言，這種排序方法就叫做外排序。 在實(shí)際應(yīng)用中 ， 由于使用的外存設(shè)備不同 ， 通常又可以分為磁盤(pán)文件排序和磁帶文件排序兩大類 。 磁帶排序和磁盤(pán)排序的基本步驟相類似 ， 它們的主要不同之處在于初始?xì)w并段在外存貯介質(zhì)中的分布方式 ， 磁盤(pán)是直接存取設(shè)備 ， 磁帶是順序式存取設(shè)備 。 外部排序基本上由兩個(gè)相對(duì)獨(dú)立的階段組成 。 首先 ，按可用內(nèi)存大小 ， 將外存上含 n個(gè)記錄的文件分成若干長(zhǎng)度為 h的子文件 ， 依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序 ， 并將排序后得到的有序子文件重新寫(xiě)入外存 ， 通稱這些有序子文件為 歸并段 或 順串 。 然后 ，對(duì)這些歸并段進(jìn)行逐趟歸并 ， 使歸并段逐漸由小到大 ，直至得到整個(gè)有序文件為止 。 對(duì)順串的歸并 ， 最簡(jiǎn)單的是運(yùn)用類似于內(nèi)部排序中的歸并算法 。 與內(nèi)排序中的歸并算法主要不同是 ， 隨著歸并的進(jìn)行 ， 有序段 （ 順串 ） 不斷擴(kuò)大 ， 以至于內(nèi)存緩沖區(qū)不能將它們完全容納 ， 需要分段從外存讀入 。 同樣在輸出時(shí) ， 也需要分段輸出到外存 。 本章小結(jié) （注意：所有的 本章小節(jié) 都用楷體，但英文仍用 Times New Noman） 排序不僅是線性表的重要的操作 ， 也代表著一類重要的算法設(shè)計(jì)方法 。 本章共介紹了四種內(nèi)排序算法 ， 它們是：插入排序 ， 交換排序 （ 冒泡排序 、 快速排序 ） 、 選擇排序 （ 直接選擇排序 、 堆排序 ） 和歸并排序 。這幾種均為基于比較的排序 ， 即排序過(guò)程的實(shí)現(xiàn)主要靠關(guān)鍵字的關(guān)系大小比較 。 另有一類排序算法 ， 它們的 （ 排序的 ） 進(jìn)行 ， 不主要依賴關(guān)鍵字的關(guān)系比較 。 這類算法典型的有基數(shù)排序 、 桶排序 、 計(jì)數(shù)排序等 ， 它們均可在線性時(shí)間復(fù)雜度內(nèi)完成 。 但是 ， 這些方法的適用范圍一般都有限 。 這幾種算法我們?cè)谶@里沒(méi)有介紹 ， 有興趣的讀者可以參閱有關(guān)資料 。 一般說(shuō)來(lái) ， 比較簡(jiǎn)單的排序 （ 如直接插入 、 直接選擇 、 冒泡排序等 ）所需要的時(shí)間代價(jià)大 ， 為 O（ n2） ， 但在某些特殊情況下可能取得很好的效果 。 例如 ， 當(dāng)初始序列已排序或接近排序的情況下 ， 直接插入排排序和改進(jìn)的冒泡排序的時(shí)間代價(jià)可能達(dá)到 O（ n） 量級(jí) 。 對(duì)一些較復(fù)雜的排序算法 ， 如快速排序 、 堆排序 、 歸并排序等 ， 平均情況下的時(shí)間復(fù)雜度為 O(nlog2n)。 比較起來(lái) ， 堆排序和歸并排序?qū)Ω鞣N情況的時(shí)間復(fù)雜度差別不大 ， 但對(duì)快速排序 ， 其在最壞情況下退步為 O(n2)， 發(fā)生在初始記錄已排好序的時(shí)侯 。 事實(shí)上 ， 快速排序?qū)Τ跏加涗浥帕泻?“ 亂 ” 的情況更有效 。 對(duì)基于比較的排序 ， 復(fù)雜度是否還有比 O(log2n)更低的算法 ？ 回答是否定 。 有人早已證明 ， 對(duì)基于比較的排序 ， 平均狀況下的時(shí)間復(fù)雜度都不會(huì)比 O(log2n)更低 。這就知道我們 ， 如果想尋找更快的排序方法 ， 就不要盯在 “ 比較 ” 上了 ， 必須超越這種思維才可能發(fā)現(xiàn)數(shù)量級(jí)更低的算法 。 但一個(gè)顯然的事實(shí)是 ， 再低也低不過(guò)O(n)。 快速排序和歸并排序都需要較大的輔助空間 。 對(duì)快速排序 ， 如果不加控制 （ 如遞歸算法 ） ， 對(duì)輔助空間的需求可能達(dá)到 O(n)， 但若每次對(duì)分割后的較大的部分進(jìn)棧 （ 先分割較小的部分 ） ， 則平均情況下輔助空間的量為 O(log2n)。 對(duì)歸并排序 ， 固定需要與原始數(shù)據(jù)個(gè)數(shù)等量的輔助空間 。 歸并排序方法多用于外排序 。 在穩(wěn)定性方面 ， 快速排序 、 堆排序 、 直接選擇排序等是不穩(wěn)定的排序 ， 其它排序是穩(wěn)定的 。 外排序的基本方法是歸并 。 歸并的思想本來(lái)是簡(jiǎn)單的；但為了減少訪問(wèn)外存的次數(shù) ， 減少外設(shè)的臺(tái)數(shù)和輸入輸出緩沖區(qū)的個(gè)數(shù) ， 并使主機(jī)和外設(shè)盡量并行工作 ，這就給外排序的討論增加了難度 。 在算法構(gòu)思方面 ， 值得認(rèn)真地學(xué)習(xí)這幾種排序算法 。 同樣一個(gè)問(wèn)題 ， 考慮的角度不同 ， 就導(dǎo)致不同的方法 ， 例如 ， 插入觀點(diǎn)導(dǎo)致插入排序 ， 交換觀點(diǎn)導(dǎo)致冒泡排序 、 分割觀點(diǎn)導(dǎo)致快速排序 、 選拔觀點(diǎn)導(dǎo)致直接選擇排序 、 樹(shù)形選拔觀點(diǎn)導(dǎo)致堆排序 ， 合并觀點(diǎn)導(dǎo)致歸并排序 。 習(xí) 題 1． 對(duì)于給定的一組鍵值： 83， 40， 63， 13， 84， 35，96， 57， 39， 79， 61， 15， 分別畫(huà)出應(yīng)用直接插入排序 、 直接選擇排序 、 快速排序 、 歸并排序?qū)ι鲜鲂蛄信判蛑懈魈说慕Y(jié)果 。 2． 對(duì)上題給出的關(guān)鍵字 ， 畫(huà)出堆排序中的： a)建堆期間每次堆調(diào)整后的結(jié)果 （ 樹(shù) ） ； b)每次 “ 輸出 交換 ”后的結(jié)果 （ 樹(shù) ） 。 3． 本章介紹的各排序方法中哪些是穩(wěn)定的 ？ 哪些是不穩(wěn)定的 ？ 對(duì)不穩(wěn)定的舉例說(shuō)明 。 4． 設(shè)計(jì)一個(gè)針對(duì)單鏈表的直接選擇排序算法 。 5． 插入排序中找插入位置的操作可以通過(guò)二分查找的方法來(lái)實(shí)現(xiàn) 。 試寫(xiě)一個(gè)針對(duì)這種改進(jìn)的插入排序算法 。 6． 一個(gè)線性表中的元素為正整數(shù)或負(fù)整數(shù) 。 設(shè)計(jì)一個(gè)算法 ， 將正整數(shù)和負(fù)整數(shù)分開(kāi) ， 使線性表前一半為負(fù)整數(shù) ， 后一半為正整數(shù) 。 不要求對(duì)這些元素排序 ， 但要求盡量減少交換次數(shù) 。 7． 冒泡也可以向前 “ 冒 ” ， 就每次交換都從記錄集的最后開(kāi)始 ，將最小記錄 “ 冒 ” 到最前面 。 請(qǐng)寫(xiě)出這種冒泡的子程序 。 8． 冒泡也可以從前后兩端 “ 同時(shí) ” （ 實(shí)際實(shí)現(xiàn)時(shí)可以是交替 ）向中間 “ 冒 ” ， 即兩邊 “ 夾擊 ” ， 將兩邊各自最大的記錄夾在中間 ， 然后再將它們中最大者置換到最后 ， 完成一趟冒泡 。請(qǐng)寫(xiě)出這種冒泡的子程序 。 9． 已知 （ k1， k2， … ， kn） 是堆 ， 試寫(xiě)一個(gè)算法將 （ k1， k2， … ，kn， kn+1） 調(diào)整為堆 。 按此思想寫(xiě)一個(gè)從空堆開(kāi)始一個(gè)一個(gè)添入元素的建堆算法 （ 提示：增加一個(gè) kn+1后應(yīng)從葉子方向調(diào)整 ） 。 10． 設(shè)計(jì)一個(gè) n路合并子程序 。 這里 n=2， 且要求 n的具體值做為子程序參數(shù)給出給出 。