位图向量排序有三大优点：1）速度快，复杂度为O （n）；2）内存需要少；3）排序时间与输入元素数据无关，但它也有三个很严苛的限制：1）整数；2）元素值在一定范围之内（与机器内存有关）3）没有重复。它的本质是使用位数组的下标来记录元素值，，而数组的值表示该元素下标是否存在，因此达到节省内存、加快速度的目标（节省内存是针对元素比较密集的情况，过于稀疏的情况未必就节省内存）。 比如说要表示包含1-5范围内的整数的一个集合，只需要一个字节（8位），而不是20个字节。但是需要把这八个位看作是一个具有八个元素的数组，如果某个元素为1，那么表示这个元素的下标在整数集里，如果为0则表示不存在下标表示的整数。因此1-5的整数可以表示为： 0 1 1 1 1 1 0 0 表示完成后，就可以扫描数组，输出排序结果。 但是当前的程序语言（除了一些库）中并没有bit数据类型，所以需要找到一种方法，进行bit位与选用的数据类型的转换，为了简单，可以使用unsigned char类型来表示bit位，每个unsigned char元素c有八位，要判断第a位是否为1，可以使用该元素与一个只在第a位上为1而在其他位上都为0的数b（八位表示的数）相与，结果为0，表示a位为0，非0，则a位为1。要设置某一位的值，只需将a与b相或即可（原理嘛，用笔在纸上写写就知道了）。数b如何求呢，第一位为1其他位为0的数是128，其它位为1的数就可以通过对128进行右移位运算得到。准备工作完成：
;//为了使算法对负数也有效，所以将最小值和最大值也作为输入void sort(int *array,int value_count,int min_value,int max_value){if(min_value >= max_value) return;bit_map_count = (max_value – min_value + 1 + 7) / 8;[bit_map_count];));int* p = array;for (int i = 0; i < value_count; ++i,++p){//保证value非负，因为数组下标是非负的int value = *p – min_value;//元素值除以8，得到表示该元素的位图向量所在字节的下标int index = value >> 3;//求摸则得到元素在字节中所处的位置int pos_in_byte = value % 8;//设置相应的位为1bit_map[index] = bit_map[index] | (128>>pos_in_byte);}p = array;for (int i = 0; i < bit_map_count; ++i){unsigned char c = bit_map[i];for (int j = 0; j < 8; ++j){//判断相应位是否为1if( c & (128>>j)){//恢复输入元素的原值，并将其添加到输出数组中*p = (i<<3) + j + min_value;++p;}}}}int _tmain(int argc, _TCHAR* argv[]){int n = 10;int array[] = {0,-1,-2,-3,-4,-5,-6,-7,-8,-9};for (int i = 0; i < n; ++i){cout<<array[i]<<‘ ‘;}cout<<endl;sort(array,n,-9,98);for (int i = 0; i < n; ++i){cout<<array[i]<<‘ ‘;}cout<<endl;}
程序正确运行，sort函数还有可以改进的地方：将b的值先计算出来，然后就可以把与b相关循环展开。
让所有的愁向后飞去。请不要回头去追你因该向前奔跑，因为快乐在前方!
