磁盤檔案排序
問題描述，來自《程式設計珠玑》：
輸入：一個最多含有n個不相同的正整數的檔案，其中每個數都小于等于n，且n=10^7。
輸出：得到按從小到大升序排列的包含所有輸入的整數的清單。
條件：最多有大約1mb的記憶體空間可用，但磁盤空間足夠。且要求運作時間在5分鐘以下，10秒為最佳結果。
分析：
1、歸并排序。你可能會想到把磁盤檔案進行歸并排序，但題目要求中，你隻有1mb的記憶體空間可用，是以，歸并排序這個方法不行。
2、位圖方案。例如正如《程式設計珠玑》一書上所述，用一個20位長的位字元串來表示一個所有元素都小于20的簡單的非負整數集合，邊框用如下字元串來表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
上述集合中各數對應的位置則置1，沒有對應的數的位置則置0。
參考《程式設計珠玑》一書上的位圖方案，針對10^7個資料量的磁盤檔案排序問題，可以這麼考慮，由于每個7位十進制整數表示一個小于1000萬的整數。可以使用一個具有1000萬個位的字元串來表示這個檔案，其中，當且僅當整數i在檔案中存在時，第i位為1。采取這個位圖的方案是因為我們面對的這個問題的特殊性：1、輸入資料限制在相對較小的範圍内，2、資料沒有重複，3、其中的每條記錄都是單一的正整數，沒有任何其它與之關聯的資料。
是以，此問題用位圖的方案分為以下三步進行解決：
第一步，将所有的位都置為0，進而将集合初始化為空。
第二步，通過讀入檔案中的每個整數來建立集合，将每個對應的位都置為1。
第三步，檢驗每一位，如果該位為1，就輸出對應的整數。
經過以上三步後，産生有序的輸出檔案。令n為位圖向量中的位數（本例中為10000000），程式可以用僞代碼表示如下：
不過很快，我們就将意識到，用此位圖方法，嚴格說來還是不太行，空間消耗10^7/8還是大于1m（1m=1024*1024空間，小于10^7/8）。
既然如果用位圖方案的話，我們需要約1.25mb（若每條記錄是8位的正整數的話，則10000000/(1024*1024*8) ~= 1.2m）的空間，而現在隻有1mb的可用存儲空間，那麼究竟該作何處理呢？可以多次使用位圖進行排序。
3、多路歸并。把這個檔案分為若幹大小的幾塊，然後分别對每一塊進行排序，最後完成整個過程的排序。k趟算法可以在kn的時間開銷内和n/k的空間開銷内完成對最多n個小于n的無重複正整數的排序。比如可分為2塊（k=2，1趟反正占用的記憶體隻有1.25/2=0.625m），1~4999999，和5000000~9999999先周遊一趟，處理1~4999999的資料塊（用5000000/8=625000個字的存儲空間來排序0~4999999之間的整數），然後再第二趟，對5000001~1000000這一資料塊處理。
針對這個要分兩趟給磁盤檔案排序的具體問題編寫完整代碼，如下:
上述的位圖方案，共需要掃描輸入資料兩次，具體執行步驟如下：
第一次，隻處理1—4999999之間的資料，這些數都是小于5000000的，對這些數進行位圖排序，隻需要約5000000/8=625000byte，也就是0.625m，排序後輸出。
第二次，掃描輸入檔案時，隻處理4999999-10000000的資料項，也隻需要0.625m（可以使用第一次處理申請的記憶體）。是以，總共也隻需要0.625m。
磁盤檔案排序的c實作
1、内排序
由于要求的可用記憶體為1mb，那麼每次可以在記憶體中對250k的資料進行排序，然後将有序的數寫入硬碟。
那麼10m的資料需要循環40次，最終産生40個有序的檔案。
2、多路歸并排序
（1）将每個檔案最開始的數讀入（由于有序，是以為該檔案最小數），存放在一個大小為40的first_data數組中；
（2）選擇first_data數組中最小的數min_data，及其對應的檔案索引index；
（3）将first_data數組中最小的數寫入檔案result，然後更新數組first_data（根據index讀取該檔案下一個數代替min_data）；
（4）判斷是否所有資料都讀取完畢，否則傳回（2）。
完整代碼如下：
測試資料：生成1000萬個不重複的正整數
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
http://www.cnblogs.com/luxiaoxun/archive/2012/09/12/2681268.html