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