謝謝absolute同學提出的問題。

部分解答（還有沒有完成的部分）： 

增加內容：

在寫了這篇博客之后，又將《編程珠璣》拿出來將里面的內容看了一些，不過倒是有些地方沒看明白了，這里寫出來看看有沒有同學能看出來我哪里理解錯了（應該不會是寫錯了）

在《編程珠璣》中，這個問題是被作為一個故事來引入的。為了讓沒有該本書的同學更加清楚題意，我來簡單描述一下。（補充：這本書很薄，一共連答案217頁，售價RMB 28.00，大家一般買還能打折，可以買本來看看。我在CSDN上找到了相關的下載，為中英文都有的，而且是PDF格式。不過不知道英文是怎么排版的，還有就是有源碼比較好，鏈接如下：http://d.download.csdn.net/down/323362/Wuaner，OK，題外話結束。）

一開始程序員提出的問題很簡單，“我該如何對磁盤文件進行排序”。

【外排序，解決方案一 – 歸并排序】

OK，首先就找本“常見的數據結構書”來看看外排序吧。我這里原本有兩本，不過有本書不知道扔在哪里，就取了殷人昆的那本黃書~其9.7節介紹了外排序。

其中介紹了，外排序多使用歸并排序的方法。

書中將排序過程分為兩個階段，第一個階段建立為外排序所用的內存緩沖區，根據它們的大小將輸入文件劃分為若干段，然后用某種有效的內排序方法對各段進行排序，這些經過排序的段叫做初始歸并段或初始順串，當它們生成后就被寫到外存中去；

第二個階段仿照內排序中所介紹過的歸并樹模式，把第一個階段生成的初始歸并段加以歸并，一趟趟地擴大歸并段和減少歸并段個數，直到最后歸并成一個大歸并段（有序文件）為止。

這里第一個階段我們應該比較熟悉，其實和內排序差不多，區別就是分段輸入，以及輸出初始歸并段到硬盤文件中。

外排序和內排序主要的區別就是在將硬盤中的多個有序文件歸并到一個最終的有序文件。

過程：

簡單的2路歸并，對兩個歸并段進行歸并時。僅需把這兩個歸并段中的對象逐塊讀入內存，進行比較后，寫入大歸并段，然后再進行讀出，所以這種方法能夠對很大的歸并段進行歸并。而其他的內排序方法很難用于外排序。包括插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、基數排序。

這種方法，需要1次讀入輸入文件，多次讀入/讀出中間文件，1次讀出輸出文件。

之后回到書上的內容來，此時作者回答了程序員的問題，在流行編程書籍中的磁盤排序程序大概有10多個函數，200行程序代碼（有這么多嗎？）對于這些代碼，實現和測試大概最多需要花費程序員1周的時間。

這當然不是最好的答案，所以才有了之后的交談。還是用談話的內容來介紹這一段比較好。斜體為作者的問題，然后是程序員的回答。

需要排序的內容究竟是什么？文件中有多少記錄？每個記錄的格式是什么？

該文件包含至多10000000個記錄，每條記錄都是一個7位整數。

等一下。假如文件那么小的話，為什么還要費力地使用磁盤排序呢？為什么不在主存儲器中對它進行排序呢？

盡管機器有很多MB的主存儲器，但是該排序功能屬于某個大型系統中的一部分。我想實際上我可能只有1MB的空閑主存。（一個可以看出以前就算是大型系統，內存還是很緊俏啊，還有就是如何能夠估算出自己能夠使用的內存呢？因為現在我們的程序都是架在虛存上面的，每個進程都有屬于自己的4G空間。）

你能將有關記錄方面的內容說得更詳細一點嗎？

每個記錄都是一個7位正整數，并且沒有其他的關聯數據，每個整數至多只能出現一次。

作者主要通過上面的對話，將問題了解得更清楚了。同時，根據其他的對話，最終了解到這個文本是美國的電話號碼的一個存儲文件。在美國，電話號碼由3位區號與7位其他號碼組成。撥打包含免費區號800的電話是不收費的。實際的免費電話號碼數據庫包含有大量的信息，包括免費電話號碼，撥打的實際號碼，用戶名稱和地址等等。

程序員所要處理的就是這樣的一個文本數據庫，將要進行排序的整數就是那些免費電話號碼。輸入文件是一個號碼列表（其他信息都被刪除了。由此可見，即使是這樣的一個系統內的一個小模塊，也在前面還做了其他的工作，這里的輸入文件已經是經過處理的了。），并且同一號碼出現兩次以上將是一個錯誤（那這個錯誤是否需要處理，由誰來保證？）。預期的輸出是一個包含大量號碼，并且以升序的方式進行排序的文件。

同時關于性能，實際環境同時也定義了性能需求。在與系統進行長時間的會話期間，用戶請求排序文件的頻率大約是每小時一次。在完成排序之前，用戶不能做任何事情。因此排序時間不能太長，最合適的運行時間是10秒鐘。

【整理之后，精確的問題陳述】

輸入：

所輸入的是一個文件，至多包含n個正整數，每個正整數都要小于n，這里的n為10^7。如果輸入時某一個整數出現了兩次，就會產生一個致命的錯誤。這些整數與其他任何數據都不關聯。

輸出：

以增序形式輸出經過排序的整數列表。（這里應該補充一下是文件形式嗎？）

約束：

至多（大概）只有1MB的可用主存，但是可用磁盤空間非常充足。運行時間至多只允許幾分鐘，最適宜的時間大概為10秒鐘。

【解決方案二 – 多通道排序】

將每個號碼存儲在7個字節(byte)里，1M空間共有=1024*1024=1048576 bytes。

所以1M中共能存儲149796個號碼。

如果將每個號碼表示成32位的整數（也就是4個bytes），那1M中共能存儲262144個號碼。

（書中的數字分別為143000和250000。）

下面就對這種情況下，使用多通道程序進行外排序。

因為一共有10000000個整數，而1M中我們使用250000個號碼存儲，所以需要使用40個通道。

第一個通道中將0到249999之間的任意整數讀到內存中，并對這250000個整數進行排序，然后將它們寫入輸出文件中。

第二個通道對250000到499999之間的整數進行排序，然后也是同樣寫入輸出文件中。

依次類推，直到第40個通道。

第40個通道將排序9750000到9999999之間的整數，然后寫入輸出文件中。

注意，這里意思是輸出文件是同一個文件。

快速排序在主存中相當有效，它只需要20行代碼。因此整個程序只需1到2頁的代碼即可實現，并且該程序還有一個令人滿意的特性，即我們不必擔心使用中間磁盤文件的問題。

40個通道的算法不使用中間文件，需要多次讀取輸入文件，但只進行一次輸出文件的寫入操作。 

有些疑問，怎么做到是同一個輸出文件的。難道輸出之后，整個文件就是有序的了？沒有想明白。大家看看呢？