[数据结构]利用位图排序

[cpp] view plaincopy

 

#include <stdio.h>
#include <stdlib.h>

#define INT_BY_BIT 32
#define MASK 0x1F
#define SHIFT 5

#define N 1000000

int a[N/INT_BY_BIT+1];
void set_bit(int x) {a[x>>SHIFT] |= 1 << (x & MASK);}
void clear_bit(int x) {a[x>>SHIFT] &= ~(1<<(x & MASK));}
int test_bit(int x){return a[x>>SHIFT]&(1<<(x & MASK));}

int main()
{
//  int a[N/INT_BY_BIT+1];
    int i;
    for(i=0;i<N;i++)
    {
        clear_bit(i);
    }
    while (scanf("%d",&i) != EOF)
    {
        set_bit(i);
    }
    for(i=0;i<N;i++)
    {
        if(test_bit(i))
        {
            printf("%d",i);
            printf(" ");
        }
    }
    return 0;
}

1，如果某个数字可能出现最多8次，应该如何用位图排序？
答：可以用一个字节来表示一个数

2，如果有10000000个数字，但是内存只有1M，而10000000需要1.25M，用过如何排序？
答：可以通过两趟排序完成，第一趟排序1到5000000，第二次排序5000000到10000000