第一章 開篇

首先作者提出一個實際問題：

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

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

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

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

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