1、第十一章. 外部排序 （Chapter 11. External Sorting) 待排序列記錄數(shù)量太大，不能全部存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中，排序過(guò)程中需對(duì)計(jì)算機(jī)外存進(jìn)行訪問(wèn)，這種排序過(guò)程稱為外部排序。11.1 外存信息的存取一、磁帶信息的存?。?磁帶是在一條塑料薄膜上涂有磁性材料用以記錄數(shù)據(jù)的存儲(chǔ)介質(zhì)。其記錄組之間有一定的空隙 IRG（Inter Record Gap），它不是連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，讀寫(xiě)二、磁盤(pán)信息的存?。?磁盤(pán)是在一片塑料薄膜上涂有磁性材料用以記錄數(shù)據(jù)的存儲(chǔ)介質(zhì)。它分成多個(gè)磁道（柱面），每個(gè)磁道又分為多個(gè)扇區(qū)，多個(gè)磁盤(pán)組成的磁盤(pán)組還涉及到盤(pán)片號(hào)（磁頭號(hào)），磁盤(pán)繞軸高速旋轉(zhuǎn)，讀寫(xiě)頭則

2、沿其一條半徑作直線運(yùn)動(dòng)以尋道。它也不是信息只能在運(yùn)行穩(wěn)定時(shí)進(jìn)行，且找到要讀寫(xiě)的記錄也需要一定的繞帶時(shí)間，因此，在磁帶上讀寫(xiě)信息所需的時(shí)間由兩部分組成：TI/O = td + n tw，其中 td 為延遲時(shí)間，即讀寫(xiě)磁頭到達(dá)信息所在物理塊起始位置所需時(shí)間， tw 為傳輸一個(gè)記錄的時(shí)間。磁帶是一種順序存儲(chǔ)設(shè)備。11.2 外部排序的方法 總體要用歸并排序，亦即將待排序列分成若干子序列分別進(jìn)入內(nèi)存排成有序序列（初始?xì)w并段），再用歸并排序?qū)⑺袣w并段排序成一個(gè)有序序列。連續(xù)運(yùn)轉(zhuǎn)的設(shè)備，讀寫(xiě)信息只能在旋轉(zhuǎn)穩(wěn)定時(shí)進(jìn)行，且找到要讀寫(xiě)的記錄也需要一定的尋道、尋扇區(qū)時(shí)間，因此，在磁盤(pán)上讀寫(xiě)信息所需的時(shí)間由三部分組

3、成：TI/O = tseek + tla + n tw，其中 tseek 為尋道時(shí)間（seek time）， tla 為尋扇區(qū)時(shí)間（latency time time）， tw 為傳輸時(shí)間（transmission time）。磁盤(pán)是一種隨機(jī)存儲(chǔ)設(shè)備。 一般情況下，外部排序所需的總時(shí)間由三部分構(gòu)成：內(nèi)部排序（產(chǎn)生初始?xì)w并段）所需時(shí)間（ m * tIS ）、外存信息讀寫(xiě)時(shí)間（ d * tIO ）、內(nèi)部歸并所需時(shí)間（ s * u tmg ）。其中 tIS 是為得到一個(gè)初始?xì)w并段進(jìn)行內(nèi)部排序所序的平均時(shí)間， tIO 是進(jìn)行一次外存讀寫(xiě)的平均時(shí)間， u tmg 是對(duì) u 個(gè)記錄進(jìn)行內(nèi)部歸并所需的時(shí)間，

4、m 為初始?xì)w并段的個(gè)數(shù)，s 為歸并的趟數(shù)，d 為總的讀寫(xiě)次數(shù)。 但由于訪問(wèn)外存儲(chǔ)器的時(shí)間開(kāi)銷太大，即 tIO 遠(yuǎn)遠(yuǎn)大于 tmg ，因此，要提高外部排序速度，就必須減少訪問(wèn)外存的次數(shù)。 對(duì)同一待排序列而言，外部排序訪問(wèn)外存的總次數(shù) d 與歸并的趟數(shù) s 成正比，而對(duì) m 個(gè)初始?xì)w并段進(jìn)行 k 路平衡歸并所需的趟數(shù) s = log k m ，因此，增加 k 或減少 m 均能減少 s。516128305 23 3416 28 3112 14 178 10 1530 38 56b3b4b0b1b201234 初始?xì)w并段 0b555555160451650330028308011250581352323

5、 34 4823163161241280181010 15 2910302101201101515 29 885 - 路平衡歸并的敗者樹(shù)： 例：11.4 置換 - 選擇排序 利用置換-選擇排序（replacement-selection sort）可以達(dá)到這個(gè)目的（也用敗者樹(shù)實(shí)現(xiàn)）： 置換 - 選擇排序是在選擇排序的基礎(chǔ)上， 當(dāng)最小關(guān)鍵字記錄被選出后，它空出的位置補(bǔ)充進(jìn)一個(gè)新的記錄，以后再求最小記錄時(shí)，不能選擇比剛才的最小記錄關(guān)鍵字小的記錄，只能從大于它的記錄中尋找新的最小關(guān)鍵字記錄。反復(fù)此過(guò)程，直至工作區(qū)中所有記錄的關(guān)鍵字均比剛出去的最小記錄的關(guān)鍵字小為止，此時(shí)得到的就是一個(gè)完整的初始?xì)w并段

6、。 除了增加 k 可以減小 s 外，減小 m 也是減小 s 的另一有效途徑。 但減小 m 就意味著要增加初始?xì)w并段長(zhǎng)度，這又受到計(jì)算機(jī)內(nèi)存大小的制約，又該如何解決這個(gè)問(wèn)題呢？ 那么，利用置換-選擇排序到底能使初始?xì)w并段的長(zhǎng)度增加多少呢？ E.F.Moore用類比的辦法解決了這個(gè)問(wèn)題：設(shè)天上正勻速地下著大雪，有一臺(tái)掃雪機(jī)也勻速地沿著一個(gè)環(huán)形跑道在掃雪，當(dāng)達(dá)到某一平衡點(diǎn)時(shí)，單位時(shí)間內(nèi)掃雪機(jī)掃去的雪和天上下的雪的量正好相等，跑道上的積雪量保持不變，則積雪形成了一個(gè)斜面：掃雪機(jī)前面的積雪厚度最大，掃雪機(jī)后面的積雪厚度為零。此時(shí)跑道上的積雪量就相當(dāng)于計(jì)算機(jī)的工作區(qū)大小 W，而掃雪機(jī)工作一圈所掃去的積雪量

7、就相當(dāng)于初始?xì)w并段的長(zhǎng)度 2 W。 生成初始?xì)w并段的時(shí)間（不考慮輸入輸出）為 O ( n logW )。11.5 緩沖區(qū)及并行操作 設(shè)定相應(yīng)的輸入輸出緩沖區(qū)，讓輸入、輸出和內(nèi)部歸并三種操作同時(shí)進(jìn)行（并行操作），也能提高總的外部排序時(shí)間。但增加緩沖區(qū)數(shù)目，必將減小工作區(qū)大小 W，又使得初始?xì)w并段長(zhǎng)度減小從而增加排序總時(shí)間。因此，外部排序總的時(shí)間與歸并排序路數(shù) k 的選擇、緩沖區(qū)大小的設(shè)置以及各種外設(shè)參數(shù)的設(shè)置等有關(guān)，實(shí)際應(yīng)用時(shí)要綜合考慮各種因數(shù)。11.6 最佳歸并樹(shù) 用置換-選擇排序得到的初始?xì)w并段長(zhǎng)度各不相同，那應(yīng)如何進(jìn)行 k 路平衡歸并呢？這實(shí)際上是建立 k 叉霍夫曼樹(shù)的問(wèn)題：當(dāng)初始?xì)w并段總

8、數(shù)不足（ ( m - 1 ) MOD ( k - 1 ) 0 ）時(shí)，需附加 k - ( m - 1 ) MOD ( k - 1 ) -1 個(gè)長(zhǎng)度為零的虛段，亦即第一次歸并時(shí)只對(duì) ( m - 1 ) MOD ( k - 1 ) + 1 個(gè)初始?xì)w并段歸并。建立 k 叉霍夫曼樹(shù)每次仍是選擇記錄數(shù)相對(duì)少的初始?xì)w并段先進(jìn)行歸并。最佳歸并樹(shù)不適合磁帶歸并排序。作 業(yè)34. 已知某文件經(jīng)過(guò)置換-選擇排序之后，得到長(zhǎng)度分別為 47，9，39，18，4，12，23 和 7 的八個(gè)初始?xì)w并段。 試為 3-路平衡歸并設(shè)計(jì)一個(gè)讀寫(xiě)外存次數(shù)最少的歸并方案，并求出總的讀寫(xiě)外存次數(shù)。11.7 磁帶歸并排序 前面所介紹的各種

9、技術(shù)除最佳歸并樹(shù)外均適合于磁帶歸并排序，但由于磁帶是順序存取設(shè)備，在實(shí)現(xiàn)外部排序時(shí)，有些特殊的問(wèn)題需考慮。一、平衡歸并 實(shí)現(xiàn) k-路平衡歸并，需要 2k 臺(tái)磁帶機(jī)，其中 k 臺(tái)用于輸入，k 臺(tái)用于輸出，待一趟歸并完后，輸入磁帶機(jī)改為輸出磁帶機(jī)，輸出磁帶機(jī)也改為輸入磁帶機(jī)，再進(jìn)行下一趟歸并；反復(fù)此過(guò)程，直至全部記錄歸并為一段有序序列。二、多步歸并 仔細(xì)分析一下磁帶 k-路平衡歸并可以發(fā)現(xiàn)，其實(shí)只執(zhí)行一趟 k-路歸并并不需要 2k 臺(tái)磁帶機(jī)，只需 k + 1 臺(tái)磁帶機(jī)即可，多余的磁帶機(jī)目的是為了下一趟歸并。當(dāng)然，只用 k + 1 臺(tái)磁帶機(jī)也能實(shí)現(xiàn) k-路平衡歸并，即在每趟歸并完后，再將各輸出歸并段（在同一磁帶機(jī)上）分配到 k 臺(tái)磁帶機(jī)上用于下一趟歸并。但這需要花費(fèi)很多時(shí)間，有沒(méi)有更好的辦法呢？ 多步歸并排序（ polyphase merging sorting ）能解決這個(gè)矛盾。與平衡歸并不同，一趟多步歸并不是文件中的全部記錄都參與歸并。那么，初始?xì)w并段又是如何分配在各磁帶機(jī)上的呢？ 利用 k-階廣義費(fèi)波拉契序列，當(dāng)初始?xì)w并段總數(shù)為某一費(fèi)波拉契數(shù)（不足用虛段填充）時(shí)，各磁帶機(jī)上分布的初始?xì)w并段數(shù)由下式給出：t1(k) = fj-1(k) + fj-2(k) + fj-3(k) + + fj-k(k) t2(k) =