主要是闡述位圖在排序中的使用. ### 問題描述 位圖排序是一種效率極高(復雜度可達O(n))并且很節省空間的一種排序方法，但是這種排序方法對輸入的數據是有比較嚴格的要求(數據不能重復，大致知道數據的范圍)。位圖排序即利用位圖或者位向量來表示集合。可以說算法中用到位操作的很多，因為速度快，空間小，比如哈有bitmask dp。文中的問題可以抽象為對[1:10000000]區間內的隨機排列進行排序，而且內存限制在1m左右。外部排序可能是第一個閃近腦子里的答案。作者在文中的解法就是利用bitmap算法，每一個bit代表一個數字，用10000000個比特位就可以將所有的數字表示出來。然后遍歷，設置1為存在，0為不存在，然后順序輸出即可。 而且是更加貼近現實的：“你手中有一百萬張紙，每張紙上是一個大學生的資料，你需要將他們按照年紀排序，你怎么做？誰更聰明，一個計算機科學博士還是你的母親？在?Google?從事多年面試工作的?Paul?Tyma?將這個問題交給他的母親解答。從未學過計算機科學的?Tyma?夫人做的比受過高等教育的人還要出色。許多應試者會建議快速排序算法，而 Tyma?夫人的答案比他們的方法要快上?20?倍。有時候創造力只是常識。答案：將紙堆上的第一張拿下來，看看年齡，如果他是?21?歲，就放到?21?歲的紙堆里，如果下一個是?19?歲，就放到?19?歲的紙堆里。如此這般，任何記錄你只需要看一次，當你完成后，將不同年齡的紙堆順序排列即可。”不過這類問題的特殊性就是數據范圍比較集中，比如1到10000000，年齡一般都在1-200之間，后一個題帶有明顯的計數排序和hash的影子。 再舉個例子，假如有一個集合{3,5,7,8,2,1}，我們可以用一個8位的二進制向量set[1-8]來表示該集合，如果數據存在，則將set相對應的二進制位置1，否則置0.根據給出的集合得到的set為{1,1,1,0,1,0,1,1}，然后再根據set集合的值輸出對應的下標即可得到集合{3,5,7,8,2,1}的排序結果。這個就是位圖排序的原理。**** ### **實現概要** 由是觀之，用位圖或位向量表示集合。可用一個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。 在我們的實際問題中，每個7位十進制整數表示一個小于1 000萬的整數。我們使用一個具有1 000萬個位的字符串來表示這個文件，其中，當且僅當整數i在文件中存在時，第i位為1。（那個程序員后來找到了200萬個稀疏位，習題5研究了最大存儲空間嚴格限制為1 MB的情況。）這種表示利用了該問題的三個在排序問題中不常見的屬性：輸入數據限制在相對較小的范圍內；數據沒有重復；而且對于每條記錄而言，除了單一整數外，沒有任何其他關聯數據。 若給定表示文件中整數集合的位圖數據結構，則可以分三個自然階段來編寫程序。第一階段將所有的位都置為0，從而將集合初始化為空。第二階段通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。第三階段檢驗每一位，如果該位為1，就輸出對應的整數，由此產生有序的輸出文件。令n為位向量中的位數（在本例中為10 000 000），程序可以使用偽代碼表示如下： ~~~ /* phase 1: initialize set to empty */ for i = [0, n) bit[i] = 0 /* phase 2: insert present elements into the set */ for each i in the input file bit[i] = 1 /* phase 3: write sorted output */ for i = [0, n) if bit[i] == 1 write i on the output file ~~~ ### 位圖排序的應用 1. 給40億個不重復的unsigned int的整數，沒有排過序，然后再給一個數，如果快速判斷這個數是否在那40億個數當中。因為unsigned int數據的最大范圍在在40億左右，40*10^8/1024*1024*8=476，因此只需申請512M的內存空間，每個bit位表示一個unsigned int。讀入40億個數，并設置相應的bit位為1.然后讀取要查詢的數，查看該bit是否為1，是1則存在，否則不存在。 2. 給40億個unsigned int的整數，如何判斷這40億個數中哪些數重復？同理，可以申請512M的內存空間，然后讀取40億個整數，并且將相應的bit位置1。如果是第一次讀取某個數據，則在將該bit位置1之前，此bit位必定是0；如果是第二次讀取該數據，則可根據相應的bit位是否為1判斷該數據是否重復。 由于在C語言中沒有bit這種數據類型，因此必須通過位操作來實現。假如有若干個不重復的正整數，范圍在[1-100]之間，因此可以申請一個int數組，int數組大小為100/32+1。因此要進行置1位操作，必須先確定邏輯位置：字節位置(數組下標)和位位置。 字節位置=數據/32;(采用位運算即右移5位) 位位置=數據%32;(采用位運算即跟0X1F進行與操作)。 ### C實現代碼： ~~~ #include <stdio.h> #define MAX 1000000 #define SHIFT 5 #define MASK 0x1F #define DIGITS 32 int a[1+MAX/DIGITS]; void setbit(int n) //將邏輯位置為n的二進制位置為1 { a[n>>SHIFT] |= (1<<(n&MASK)); //n>>SHIFT右移5位相當于除以32求算字節位置，n&MASK相當于對32取余即求位位置， } //然后將1左移的結果與當前數組元素進行或操作，相當于將邏輯位置為n的二進制位置1. void clearbit(int n) { a[n>>SHIFT] &= ~(1<<(n&MASK)); //將邏輯位置為n的二進制位置0，原理同set操作 } int test(int n) { return a[n>>SHIFT] & (1<<(n&MASK)); //測試邏輯位置為n的二進制位是否為1 } int main(int argc, char *argv[]) { int i,n; for(i=0;i<MAX;i++) { clearbit(i); } while(scanf("%d",&n)!=EOF) { setbit(n); } for(i=0;i<MAX;i++) { if(test(i)) printf("%d ",i); } return 0; } ~~~ 在C++中提供了bitset這種集合，專門用來進行位操作，因此實現起來比較容易 ### C ++實現代碼： ~~~ #include <iostream> #include <bitset> #define MAX 1000000 bitset<MAX+1> bit; int main(int argc, char *argv[]) { using namespace std; int n,i; while(scanf("%d",&n)!=EOF) { bit.set(n,1); } for(i=0;i<=MAX+1;i++) { if(bit[i]==1) printf("%d ",i); } return 0; } ~~~ **轉載請注明出處：**[http://blog.csdn.net/utimes/article/details/8759635](http://blog.csdn.net/utimes/article/details/8759635)