第一章 開篇

首先作者提出一個(gè)實(shí)際問題：

如何給磁盤的某個(gè)文件排序，更具體來說就是是對(duì)一個(gè)最多包含1千萬條記錄，每條記錄都是7位整數(shù)的文件，而且只有1MB的內(nèi)存可以使用

從實(shí)際問題中提煉出更明確的數(shù)學(xué)定義：

輸入：一個(gè)最多包含n個(gè)整數(shù)的文件，每個(gè)數(shù)都小于n，，其中n=10^7�？梢员ＷC輸入文件中不存在重復(fù)整數(shù)
輸出：按升序排列的輸入整數(shù)的列表
約束：1MB左右的內(nèi)存空間，充足的磁盤存儲(chǔ)空間。運(yùn)行時(shí)間最多幾分鐘，控制在10秒內(nèi)不再需要進(jìn)一步優(yōu)化

考慮一般的解法，直接讀入所有的整數(shù)，然后進(jìn)行快排堆排之類的排序，時(shí)間復(fù)雜度很明顯是O(nlogn),但空間復(fù)雜度是O(n),即如果n=10^7時(shí)，用4個(gè)字節(jié)的int型存儲(chǔ)每個(gè)整數(shù)，那么需要的空間是(4*107)/210210=38MB,很顯然超出了內(nèi)存限制，而考慮實(shí)際n的大小限制和每個(gè)整數(shù)只會(huì)出現(xiàn)一次的限制，而所謂的排序也只是把從文件中的整數(shù)按在1－n內(nèi)出現(xiàn)的順序輸出而已，因此只要對(duì)n之內(nèi)出現(xiàn)的整數(shù)做一下標(biāo)記最后輸出標(biāo)記過的整數(shù)就可以了，考慮到這，位向量（也叫位圖）就成了比較合適的數(shù)據(jù)結(jié)構(gòu)的選擇，每個(gè)位的0、1值表示一個(gè)數(shù)字是否出現(xiàn)過，實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(n),考慮n取最大值10^7時(shí)，需要的空間為107/8/210/210=1.2MB,代碼實(shí)現(xiàn)如下：

  本文關(guān)鍵詞：編程珠璣，由筆耕文化傳播整理發(fā)布。