位图排序

时间：2011-01-06 来源：donotblock

位图排序：任意个(MAX_NUMBERS个) 0到固定值(MAX_VALUE)之间的数排序
时间复杂度O(n), 空间几乎是O(1)，空间需求很低
假定int的长度是32位，即一个int可以编码32个数字（简单起见，一个bit代表一个数字，实际可以编码的范围就是unsigned int的最大值，但计算比较复杂），那么0到n之间的数字就可以用最多n/32+1个整形表示，每个int的每个bit代表一个数。。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_VALUE (800000000)
#define MAX_NUMBERS (100)

int main(void){
    int size = MAX_VALUE/32+1;
    int* bits_array = (int *)calloc(size,sizeof(int));
    printf("Input numbers:\n");
    int i,p = 0;
    int array_index = 0;
    int bit_index = 0;
    srand((unsigned)time(0));
    for(i=0;i<MAX_NUMBERS;i++){
        int v = (int)(MAX_VALUE * (rand()/(RAND_MAX+1.0)));
        if(p){
           printf(",");
        }
        printf("%d",v);
        p=1;
        array_index = v/32;
        bit_index = v % 32;
        bits_array[array_index] |= 1 << bit_index;
    }

    printf("\nSorted Numbers:\n");
    int bits;
    int b;
    p=0;
    for(i=0;i<size;i++){
        bits = bits_array[i];
        int j;
        for(j=0;j<32;j++){
            b = bits & (1 << j);
            if(b != 0){
                if(p){
                    printf(",");
                }

                printf("%d",i*32+j);
                p = 1;
            }
        }
    }

    free(bits_array);
    return 0;
}