位向量排序

1、位向量表示0～N的整数
在普通机器上，一个int型整数有4个字节，共32位，我们可以通过这32位中不同的位来表示不同的整数；
创建一个数组array[100]，利用类的概念，array[0]存放32个除32等于0的整数，它的模数在32位中的相应位表示，相应的array[1]存放除32等于1的整数；
如：
[cpp]  
int i = 5;       // 5/32 = 0;     5%32 = 5  
int j = 12;      // 12/32 = 0;    12%32 = 12  
int k = 31;      // 31/32 = 0;    31%32 = 31  
int m = 34;      // 34/32 = 1;    34%32 = 2  
int n = 40;      // 40/32 = 1;    40%32 = 8  
此时，这5个数在array中的存储就应该是下面这种情况：
array[0] = 0000 0100 0000 1000 0000 0000 0000 0001b
array[1] = 0010 0000 1000 0000 0000 0000 0000 0000b
array[2] = ... = array[99] = 0
模数在相应的位将0置为1，这样就可以表示相应的整数了；
2、位向量排序
[cpp]  
int main(void)  
{  
    int i;  
    for(i = 0;i < N;i++)  
        clr(i);//复位整个数组  
    while(scanf("%d",&i) != EOF)  
        set(i);//把将要排序的数在数组中用位向量标记  
    for(i = 0;i < N;i++)  
        if(test(i))//用于比较i是否在数组中标记，若有标记就可以按顺序输出  
            printf("%d\n",i);  
    return 0;  
}  
 
N为需要排序的整数的可能最大值，clr函数将整个数组复位，然后set函数就是利用位向量的表示法将想排序的整数在数组中做一个标记；
当我们遍历0～N的整数的时候，需要排序的整数肯定在这N个数里面，只要利用test函数检测i是否在数组中标记，就可以知道此数是否为我们要排序的数，如果有标记，直接输出即可，这样就可以达到排序的目的了；
3、算法分析
时间复杂度：O(N)；
空间复杂度：O(N/32 + 1)；
4、源码——代码分享

补充：软件开发 , C++ ,

上一个：POJ 3159 Candies
下一个：项目4-正整数类