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

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

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

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

<b>方法</b><b>2</b><b>（位圖法）：</b><b></b>

我們想使用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/4≈1MB）的字元串，并将其每一bit設定為0；

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

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

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

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

<b> </b>

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 是否為1，1則有存在，0則不存在。