有時，待排序的文件很大，計算機內(nèi)存不能容納整個文件，這時候?qū)ξ募筒荒苁褂脙?nèi)部排序了（這里做一下說明，其實所有的排序都是在內(nèi)存中做的，這里說的內(nèi)部排序是指待排序的內(nèi)容在內(nèi)存中就可以完成，而外部排序是指待排序的內(nèi)容不能在內(nèi)存中一下子完成，它需要做內(nèi)外存的內(nèi)容交換），外部排序常采用的排序方法也是歸并排序，這種歸并方法由兩個不同的階段組成：

1、采用適當?shù)膬?nèi)部排序方法對輸入文件的每個片段進行排序，將排好序的片段（成為歸并段）寫到外部存儲器中（通常由一個可用的磁盤作為臨時緩沖區(qū)），這樣臨時緩沖區(qū)中的每個歸并段的內(nèi)容是有序的。

2、利用歸并算法，歸并第一階段生成的歸并段，直到只剩下一個歸并段為止。

例如要對外存中4500個記錄進行歸并，而內(nèi)存大小只能容納750個記錄，在第一階段，我們可以每次讀取750個記錄進行排序，這樣可以分六次讀取，進行排序，可以得到六個有序的歸并段，如下圖：

每個歸并段的大小是750個記錄，記住，這些歸并段已經(jīng)全部寫到臨時緩沖區(qū)（由一個可用的磁盤充當）內(nèi)了，這是第一步的排序結(jié)果。

完成第二步該怎么做呢？這時候歸并算法就有用處了，算法描述如下：

1、將內(nèi)存空間劃分為三份，每份大小250個記錄，其中兩個用作輸入緩沖區(qū)，另外一個用作輸出緩沖區(qū)。首先對Segment_1和Segment_2進行歸并，先從每個歸并段中讀取250個記錄到輸入緩沖區(qū)，對其歸并，歸并結(jié)果放到輸出緩沖區(qū)，當輸出緩沖區(qū)滿后，將其寫道臨時緩沖區(qū)內(nèi)，如果某個輸入緩沖區(qū)空了，則從相應的歸并段中再讀取250個記錄進行繼續(xù)歸并，反復以上步驟，直至Segment_1和Segment_2全都排好序，形成一個大小為1500的記錄，然后對Segment_3和Segment_4、Segment_5和Segment_6進行同樣的操作。

2、對歸并好的大小為1500的記錄進行如同步驟1一樣的操作，進行繼續(xù)排序，直至最后形成大小為4500的歸并段，至此，排序結(jié)束。

可以用一個圖示表示上述算法的歸并效果：

以上對外部排序如何使用歸并算法進行排序進行了簡要總結(jié)，提高外部排序需要考慮以下問題：

1、如何減少排序所需的歸并趟數(shù)。

2、如果高效利用程序緩沖區(qū)，使得輸入、輸出和CPU運行盡可能地重疊。

3、如何生成初始歸并段（Segment）和如何對歸并段進行歸并。

?

轉(zhuǎn)載于:https://www.cnblogs.com/codeMedita/p/7425291.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的排序之外部排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。