輸入:

所輸入的文件,至多包含n個正整數,每個正整數都小于n,題目中n = 10^7,如果輸入時某個正整數重復出現倆次,就會產生致命的錯誤,這些整數,與其他任何數據都不相關.

輸出:

以增序形式輸出經過排序的整數列表

約束

至多只有1MB(包括程序本身)可用的主存,但是可以用的磁盤空間是充足的,運行時間至多幾分鐘,10秒針是最適宜的運行時間.

作者第一個方案使用基于磁盤的合并排序.將每個號碼用32位整數表示,可以在1MB的空間里存儲250000個號碼,使用一個帶有40個通道的程序,在第一個通道中將前250000的任意整數讀入內存,并對它們進行排序,可以使用高效的快速排序,但是完成整個任務,我們要犧牲讀文件40次的代價.最后作者引出了另外一種解決方案位圖和位向量:

我們可以用一個20位的字符串可以表示小于20的非負數集合.例如,我們可以將集合{1,2,3,5,8,13}存儲在下面字符串中:

集合中代表數字的各個位設置為1 ,而其他的位全部設置為0

     在上面問題中,我們使用一千萬位的字符串表示該文件,當且僅當整數i在該文件中的時候,第i位才被設置為1,這種表示法使用了這個問題中的三中屬性,輸入的范圍相對小一些,并且還不包括重復的數據,而且沒有數據和單個整數以外的每一記錄相關聯

算法實現分三階段

1 設置每個位為0

2 讀取文件,將相應的位設置為1

3 檢查每個位,當為1時,將整數寫入

這些函數使用常量來設置，清除并測試位值