《Programming pearls》中有对该算法的介绍。 该算法的复杂度为O(X)，X为欲排序的最大的数。不适合于有重复数据的排序，重复的数据会被当作一个数据输出。
还是看代码吧！c程序实现：选自《Programming pearls》
/* bitsort.c -- bitmap sort from Column 1 * Sort distinct integers in the range [0..N-1] */ #include#define BITSPERWORD 32 // 定义每个int类型可以容纳32位 #define SHIFT 5 // 32=2^5 #define MASK 0x1F // 5位的屏蔽 #define N 10000000 // 位数组总共有多少位 int a[1 + N/BITSPERWORD]; // 位数组用int数组来实现 void set(int i){ a[i>>SHIFT] |= (1<<(i & MASK)); } //置1第i位 /* 提取数组当中的第i位 因为每个int容纳32位， i/32的整数部分就是在int数组当中哪个元素里面，位移替代除法 i/32的余数部分就是int数组当中相应元素对应的位数 比如 i＝61， 那么 i/32 = 1 表示在a[1]元素当中 i＝61， i/32的余数是29＝i&mask, 表示在a[1]元素的第29位保存 */ void clr(int i){ a[i>>SHIFT] &= ~(1<<(i & MASK)); } //清0第i位 int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); } //提取第i位的值 int main() { int i; for (i = 0; i < N; i++) clr(i); // 把数组每一位都设置为0 // 因为逐位操作效率不高，可以用下面的三行对整型数组赋值的方式取代 /* Replace above 2 lines with below 3 for word-parallel init int top = 1 + N/BITSPERWORD; for (i = 0; i < top; i++) a[i] = 0; */ while (scanf("%d", &i) != EOF) // 根据输入的数值，设置对应的位 set(i); for (i = 0; i < N; i++) // 检测哪一位是1 if (test(i)) printf("%d ", i); return 0; }
python语言实现：摘自：http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/528942
1 # Python implementation of bitsort algorithm from "Programming Pearls" 2 #http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/528942 3 4 def bitsort(filename, maxn): 5 """ Sort a file named 'filename' which 6 consists of maxn integers where each 7 integer is less than maxn """ 8 9 # Initialize bitmap10 a = [0]*maxn11 12 # Read from file and fill bitmap13 for line in file(filename):14 n = int(line.strip())15 # Turn bits on for numbers16 if n