> 作者：Hawstein > 出處：[http://hawstein.com/posts/make-thiner-programming-pearls.html](http://www.hawstein.com/posts/make-thiner-programming-pearls.html) > 聲明：本文采用以下協議進行授權：?[自由轉載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0](http://creativecommons.org/licenses/by-nc-nd/3.0/deed.zh)?，轉載請注明作者及出處。 ## 開篇 具體化你的解決的問題。下面是A和B的對話。 ~~~ A：我該如何對磁盤文件進行排序？ B：需要排序的內容是什么？文件中有多少條記錄？每個記錄的格式是什么？ A：該文件包含至多10,000,000個記錄，每條記錄都是一個7位整數。 B：如果文件那么小，為什么要使用磁盤排序呢？為什么不在主存中對它排序？ A：該功能是某大型系統中的一部分，大概只能提供1MB主存給它。 B：你能將記錄方面的內容說得更詳細一些嗎？ A：每個記錄是一個7位正整數，沒有其它的關聯數據，每個整數至多只能出現一次。 ... ... ~~~ 經過一系統的問題，我們可以將一個定義模糊不清的問題變得具體而清晰： ~~~ 輸入： 所輸入的是一個文件，至多包含n個正整數，每個正整數都要小于n，這里n=10^7。 如果輸入時某一個整數出現了兩次，就會產生一個致命的錯誤。 這些整數與其它任何數據都不關聯。 輸出： 以增序形式輸出經過排序的整數列表。 約束： 大概有1MB的可用主存，但可用磁盤空間充足。運行時間至多允許幾分鐘， 10秒鐘是最適宜的運行時間。 ~~~ 如果主存容量不是嚴苛地限制在1MB，比如說可以是1MB多，或是1~2MB之間， 那么我們就可以一次性將所有數據都加載到主存中，用Bitmap來做。 10,000,000個數就需要10,000,000位，也就是10,000,000b = 1.25MB。 程序可分為三個部分：第一，初始化所有的位為0；第二，讀取文件中每個整數， 如果該整數對應的位已經為1，說明前面已經出現過這個整數，拋出異常，退出程序 (輸入要求每個整數都只能出現一次)。否則，將相應的位置1；第三， 檢查每個位，如果某個位是1，就寫出相應的整數，從而創建已排序的輸出文件。 如果主存容量嚴苛地限制在1MB，而使用Bitmap需要1.25MB， 因此無法一次載入完成排序。那么，我們可以將該文件分割成兩個文件， 再分別用Bitmap處理。分割策略可以簡單地把前一半的數據放到一個文件， 后一半的數據放到另一個文件，分別排序后再做歸并。 也可以把文件中小于某個數(比如5,000,000)的整數放到一個文件，叫less.txt， 把其余的整數放到另一個文件，叫greater.txt。分別排序后， 把greater.txt的排序結果追加到less.txt的排序結果即可。