841
位圖排序
《編程珠璣》第一章第一題就相當的精彩，做個筆記。題目如下：輸入: 一個包含n個正整數的文件，每個正整數小於n,n等於10的7次方（一千萬）。並且文件內的正整數沒有重複和關聯數據。
輸出: 輸入整數的升序排列
約束： 限製在1M左右內存，充足的磁盤空間
假設整數占32位，1M內存可以存儲大概250000個整數，第一個方法就是采用基於磁盤的合並排序算法，第二個辦法就是將0-9999999切割成40個區間，分40次掃描（10000000/250000)，每次讀入250000個在一個區間的整數，並在內存中使用快速排序。書中提出的第三個解決辦法是采用bitmap（或者稱為bit vector）來表示所有數據集合（注意到條件，數據沒有重複），這樣就可以一次性將數據讀入內存，減少了掃描次數。算法的偽代碼如下：
階段1：初始化一個空集合
for i=[0,n)
bit[i]=0;
階段2：讀入數據i，並設置bit[i]=1
for each i in the input file
bit[i]=1;
階段3：輸出排序的結果
for i=[0,n)
if bit[i]==1
write i on the output file
這個算法的時間複雜度在O(n)，用c語言寫的版本可以在10秒內完成任務！c語言的源碼在該書主頁上有，這裏給一個java的測試版，加上我的理解注釋：
/**
* Created by IntelliJ IDEA.
* User: zhuangxd
* Date: 2008-1-7
* Time: 14:30:44
*/
public class BitSortTest {
private static final int BITSPERWORD = 32; //整數位數
private static final int SHIFT = 5;
private static final int MASK = 0x1F; //5位遮蔽 0B11111
private static final int N = 10000000;
//用int數組來模擬位數組，總計(1 + N / BITSPERWORD)*BITSPERWORD位，足以容納N
private static int[] a = new int[(1 + N / BITSPERWORD)];
public static void main(String[] args) {
bitsort(new int[]{1, 100, 2, 10000, 9999, 4567, 78902});
}
public static void bitsort(int[] array) {
for (int i = 0; i < N; i++)
clr(i); //位數組所有位清0
for (int i = 0; i < array.length; i++)
set(array[i]); //階段2
for (int i = 0; i < N; i++)
if (test(i))
System.out.println(i);
}
//置a[i>>SHIFT]的第(i & MASK)位為1，也就是位數組的第i位為1
public static void set(int i) {
a[i >> SHIFT] |= (1 << (i & MASK));
}
//置a[i>>SHIFT]的第(i & MASK)位為0,也就是位數組的第i位為0
public static void clr(int i) {
a[i >> SHIFT] &= ~(1 << (i & MASK));
}
//測試位數組的第i位是否為1
public static boolean test(int i) {
return (a[i >> SHIFT] & (1 << (i & MASK))) == (1 << (i & MASK));
}
}
文章轉自莊周夢蝶 ，原文發布時間2008-01-07
最後更新：2017-05-17 17:02:00