摘要:
輸入:所輸入的文件,至多包含n個正整數,每個正整數都小于n,題目中n = 10^7,如果輸入時某個正整數重復出現倆次,就會產生致命的錯誤,這些整數,與其他任何數據都不相關.輸出:以增序形式輸出經過排序的整數列表約束至多只有1MB(包括程序本身)可用的主存,但是可以用的磁盤空間是充足的,運行時間至多幾分鐘,10秒針是最適宜的運行時間.作者第一個方案使用基于磁盤的合并排序.將每個號碼用32位整數表示,可以在1MB的空間里存儲250000個號碼,使用一個帶有40個通道的程序,在第一個通道中將前250000的任意整數讀入內存,并對它們進行排序,可以使用高效的快速排序,但是完成整個任務,我們要犧牲讀文件
閱讀全文