算法與數據結構課件-DSC11

第十一章.外部排序（Chapter11.ExternalSorting)待排序列記錄數量太大，不能全部存放在計算機隨機存儲器中，排序過程中需對計算機外存進行訪問，這種排序過程稱為外部排序。§11.1外存信息的存取一、磁帶信息的存取：

磁帶是在一條塑料薄膜上涂有磁性材料用以記錄數據的存儲介質。其記錄組之間有一定的空隙IRG（InterRecordGap），它不是連續運轉的設備，讀寫二、磁盤信息的存取：

磁盤是在一片塑料薄膜上涂有磁性材料用以記錄數據的存儲介質。它分成多個磁道（柱面），每個磁道又分為多個扇區，多個磁盤組成的磁盤組還涉及到盤片號（磁頭號），磁盤繞軸高速旋轉，讀寫頭則沿其一條半徑作直線運動以尋道。它也不是信息只能在運行穩定時進行，且找到要讀寫的記錄也需要一定的繞帶時間，因此，在磁帶上讀寫信息所需的時間由兩部分組成：TI/O=td+ntw，其中td

為延遲時間，即讀寫磁頭到達信息所在物理塊起始位置所需時間，tw

為傳輸一個記錄的時間。磁帶是一種順序存儲設備。§11.2外部排序的方法

總體要用歸并排序，亦即將待排序列分成若干子序列分別進入內存排成有序序列（初始歸并段），再用歸并排序將所有歸并段排序成一個有序序列。連續運轉的設備，讀寫信息只能在旋轉穩定時進行，且找到要讀寫的記錄也需要一定的尋道、尋扇區時間，因此，在磁盤上讀寫信息所需的時間由三部分組成：TI/O=tseek+tla+ntw，其中tseek

為尋道時間（seektime），tla

為尋扇區時間（latencytimetime），tw

為傳輸時間（transmissiontime）。磁盤是一種隨機存儲設備。

一般情況下，外部排序所需的總時間由三部分構成：內部排序（產生初始歸并段）所需時間（m*tIS

）、外存信息讀寫時間（d*tIO

）、內部歸并所需時間（s*utmg

）。其中tIS

是為得到一個初始歸并段進行內部排序所序的平均時間，tIO

是進行一次外存讀寫的平均時間，utmg

是對u個記錄進行內部歸并所需的時間，m為初始歸并段的個數，s為歸并的趟數，d為總的讀寫次數。但由于訪問外存儲器的時間開銷太大，即tIO

遠遠大于tmg，因此，要提高外部排序速度，就必須減少訪問外存的次數。

對同一待排序列而言，外部排序訪問外存的總次數d與歸并的趟數s成正比，而對m

個初始歸并段進行k路平衡歸并所需的趟數s=logkm，因此，增加k或減少m均能減少s。

利用敗者樹（treeofloser）可解決這一問題：類似于錦標賽排序的思想，在進行k路平衡歸并時，將相互比較過的關鍵字值較大的初始歸并段號（敗者）留在樹結點中，將關鍵字值較小的初始歸并段號（勝者）上傳，直到找到最終的勝者（最小值的段號）；將其歸并后，其下一記錄將替換它參加新的一輪比賽以找到新的最小值段號；反復此過程，直至全部k個初始歸并段合并成一個有序序列為止。此時的歸并時間為log2m(n-1)tmg，與k無關，但k也并非越大越好。§11.3多路平衡歸并的實現若單純增加k以減少s，將會增加內部歸并的時間utmg

，這將抵銷d隨s減少而得到的效益，如何解決這一矛盾呢？516128305233416283112141781015303856b3b4b0b1b2[0][1][2][3][4]

初始歸并段

0b55555516045165033002830801125058135232334482316316124128018101015291030210120110151529885-路平衡歸并的敗者樹：

例：§11.4置換-選擇排序…

利用置換-選擇排序（replacement-selectionsort）可以達到這個目的（也用敗者樹實現）：

置換-選擇排序是在選擇排序的基礎上，當最小關鍵字記錄被選出后，它空出的位置補充進一個新的記錄，以后再求最小記錄時，不能選擇比剛才的最小記錄關鍵字小的記錄，只能從大于它的記錄中尋找新的最小關鍵字記錄。反復此過程，直至工作區中所有記錄的關鍵字均比剛出去的最小記錄的關鍵字小為止，此時得到的就是一個完整的初始歸并段。

除了增加k可以減小s外，減小m也是減小s的另一有效途徑。但減小m就意味著要增加初始歸并段長度，這又受到計算機內存大小的制約，又該如何解決這個問題呢？設計算機工作區大小為W=5，試給出下面待排序列利用置換-選擇排序得到的初始歸并段：{23,45,12,5,2,6,27,39,16,44,55,24,1,13,78,123,4,21,66,168,35,3,18,33,96,51,49,72,22,41}。

例：初始歸并段1為：2,5,6,12,16,23,27,39,44,45,55,78,123初始歸并段2為：1,4,13,21,24,35,66,96,168初始歸并段3為：3,18,22,33,41,49,51,72可見，利用置換-選擇排序所得到的初始歸并段數明顯比直接用選擇排序少得多。如上面的例子，直接用選擇排序要生成六個初始歸并段，但利用置換-選擇排序后，只得到了三個歸并段。

那么，利用置換-選擇排序到底能使初始歸并段的長度增加多少呢？

E.F.Moore用類比的辦法解決了這個問題：設天上正勻速地下著大雪，有一臺掃雪機也勻速地沿著一個環形跑道在掃雪，當達到某一平衡點時，單位時間內掃雪機掃去的雪和天上下的雪的量正好相等，跑道上的積雪量保持不變，則積雪形成了一個斜面：掃雪機前面的積雪厚度最大，掃雪機后面的積雪厚度為零。此時跑道上的積雪量就相當于計算機的工作區大小W，而掃雪機工作一圈所掃去的積雪量就相當于初始歸并段的長度——2W。生成初始歸并段的時間（不考慮輸入輸出）為O(nlogW)。§11.5緩沖區及并行操作設定相應的輸入輸出緩沖區，讓輸入、輸出和內部歸并三種操作同時進行（并行操作），也能提高總的外部排序時間。但增加緩沖區數目，必將減小工作區大小W，又使得初始歸并段長度減小從而增加排序總時間。因此，外部排序總的時間與歸并排序路數k的選擇、緩沖區大小的設置以及各種外設參數的設置等有關，實際應用時要綜合考慮各種因數。§11.6最佳歸并樹

用置換-選擇排序得到的初始歸并段長度各不相同，那應如何進行k路平衡歸并呢？這實際上是建立k叉霍夫曼樹的問題：當初始歸并段總數不足（(m-1)MOD(k-1)≠0）時，需附加k-(m-1)MOD(k-1)-1個長度為零的虛段，亦即第一次歸并時只對(m-1)MOD(k-1)+1個初始歸并段歸并。建立k叉霍夫曼樹每次仍是選擇記錄數相對少的初始歸并段先進行歸并。最佳歸并樹不適合磁帶歸并排序。作業34.

已知某文件經過置換-選擇排序之后，得到長度分別為47，9，39，18，4，12，23和7的八個初始歸并段。試為3-路平衡歸并設計一個讀寫外存次數最少的歸并方案，并求出總的讀寫外存次數。§11.7磁帶歸并排序前面所介紹的各種技術除最佳歸并樹外均適合于磁帶歸并排序，但由于磁帶是順序存取設備，在實現外部排序時，有些特殊的問題需考慮。一、平衡歸并

實現k-路平衡歸并，需要2k臺磁帶機，其中k臺用于輸入，k臺用于輸出，待一趟歸并完后，輸入磁帶機改為輸出磁帶機，輸出磁帶機也改為輸入磁帶機，再進行下一趟歸并；反復此過程，直至全部記錄歸并為一段有序序列。二、多步歸并

仔細分析一下磁帶k-路平衡歸并可以發現，其實只執行一趟k-路歸并并不需要2k臺磁帶機，只需k+1臺磁帶機即可，多余的磁帶機目的是為了下一趟歸并。當然，只用k+1臺磁帶機也能實現k-路平衡歸并，即在每趟歸并完后，再將各輸出歸并段（在同一磁帶機上）分配到k臺磁帶機上用于下一趟歸并。但這需要花費很多時間，有沒有更好的辦法呢？

多步歸并排序（polyphasemerging

sorting）能解決這個矛盾。與平衡歸并不同，一趟多步歸并不是文件中的全部記錄都參與歸并。設有4臺磁帶機和17個初始歸并段，采用3-路多步歸并排序，其歸并過程為：

例：

3-路多步歸并效率比3-路平衡歸并差，但比2-路平衡歸并強。那么，初始歸并段又是如何分配在各磁帶機上的呢？利用k-階廣義費波拉契序列，當初始歸并段總數為某一費波拉契數（不足用虛段填充）時，各磁帶機上分布的初始歸并段數由下式給出：t1(k)

=fj-1(k)+fj-2(k)+fj-3(k)+…+fj-k