【算法思想】位圖排序算法

一個最多包含n個正整數的檔案，每個數都小于n,其中n=10^7。假設最多隻有1M的記憶體空間可用，在考慮空間和時間的優化的情況下，請問如何對其進行排序？

我們假設這些整數都是用整型存儲(一般整型的大小為4個位元組)，那麼1M位元組可以存儲250 000個資料。由于輸入檔案最大可能有10^7個資料，是以可以通過周遊輸入檔案40次來完成排序。第一次将在[0,249 999]範圍内的整數讀入到記憶體中，第二次将在[250 000,499 999]範圍内的整數讀入到記憶體中，依此類推。每讀入一次資料，就對這些資料進行排序(可以采用一些排序算法)并輸出。顯然，我們要對檔案進行反複的讀寫，這不是我們所期望的。下面我們提出一種更加合理的算法—位圖排序算法。

如果我們想一次讀取檔案的全部内容(最大可能有1000萬個整數)，問題在于如何用1M的記憶體來表示這些數。我們可以用位圖表示集合。我們可以用一個長度為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.

這樣我們就用一個具有1000萬個位的字元串表示了這個檔案，其中，當且僅當整數i在檔案中存在時，第i位為1。是以我們可以分下面三步來解決這一問題：

将字元串的所有位置為0即初始化

逐一讀取檔案中的每個整數，并将以該整數為下标的對應為置為1

逐一檢查字元串的每一位，如果為1，則輸出這一進制素的下标

我們在很多問題中，都遇到着時間和空間的折中，毛澤東在論持久戰中也說過以空間換時間(據說是蔣介石先提出來的)。但是上面的程式是：減少程式空間需求的同時也減少了其運作時間。因為需要處理的資料變少了，進而處理資料所需要的時間變少了，同時沒有反複的讀取檔案，進一步避免了磁盤的通路時間。當然，隻有當原始設計非最佳方案時，才有可能時空雙赢。

作者：nineheadedbird