程式設計珠玑--位圖法排序

位圖法是《程式設計珠玑》第一章中出現的磁盤排序算法。

題目：一個最多包含n個正整數的檔案，每個數都小于n，其中n=10^7,且所有正整數都不重複。求如何将這n個正整數升序排列。

限制：最多有1MB的記憶體空間可用，有充足的磁盤存儲空間。

分析:這個題目的最大亮點是隻有1MB的記憶體空間，我們可以通過計算得出，記憶體隻有1MB可以儲存的int（4byte）有10^3*10^3/4=250 000個号碼。而包含正整數的檔案約為10^7個int大小。這意味着無法将所有檔案中的正整數一次讀取進入到記憶體空間中去進行排序算法。是以衍生出下面兩種方法：

方法1（多通道法）:

題目中的限制為所有正整數都不重複。這代表：

輸入檔案中範圍在1~249 999的正整數至多隻有250 000個，至多占記憶體為1MB。

輸入檔案中範圍在250 000~499 999的正整數至多隻有250 000個，至多占記憶體問1MB。

…..

多通道方法：

第1遍周遊檔案，将檔案中範圍在1~ 249 999的正整數讀取進入1MB記憶體，排序（可以使用各種排序方法），将排序後的正整數存儲在磁盤檔案temp中

第2遍周遊檔案，将檔案中範圍在250 000~499 999的正整數讀取進入1MB記憶體，排序，将排序後的正整數加入存儲在磁盤檔案temp中

….

第40遍周遊檔案，将檔案中範圍在10^7-250 000~10^7的正整數讀取進入1MB記憶體，排序，将排序後的整數加入存儲在磁盤檔案temp中

輸出temp檔案

此方法缺點是非常明顯的：需要周遊40次檔案，意味着讀取輸入檔案40次，并且需要一個和中間檔案temp。

因而我們使用更好的排序方法。

方法2（位圖法）：

我們想使用hash映射，将對應的正整數映射到位圖集合中。即将正整數映射到bit集合中，每一個bit代表其映射的正整數是否存在。

比如{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

我們可以使用具有10^7位的字元串來表示這個檔案。其中，當且僅當整數i在檔案中存在時候，第i位為1

位圖法方法：

建立有個10^7位（10^7/8/1024/1024≈1MB）的字元串，并将其每一bit設定為0；

讀取包含正整數的檔案，對每一個i，将記憶體中bit[i] 位設定成1.

按位順序讀取字元串。當讀取到bit[j] 為1時輸出（int）j。

根據位圖法演變解決以下QQ面試題目：

給40億個不重複的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中

unsign int範圍為0~2^32-1(4294967295≈5*10^9) 使用位圖hash對應5*10^9/8/10^3/10^3 = 625MB.

我們使用625M的字元串。每一位設定為0.

将40億個unsign int 周遊一遍。使用位圖法将字元串中的對應位轉化為1。

讀取“再給一個數i” 檢視bit[i] 是否為1，1則有存在，0則不存在。

本文轉自軒脈刃部落格園部落格，原文連結：http://www.cnblogs.com/yjf512/archive/2010/11/04/1868899.html，如需轉載請自行聯系原作者