使用位图法进行排序和查找

如何在1MB的空间里面对一千万个整数进行排序？并且每个数都小于1千万。实际上这个需要1.25MB的内存空间（这里所说的空间是考虑用位图表示法时，每一位代表一个数，则1千万/(102410248) 约为1.25MB ）。

先来随机生成[0, n)之间不重复的随机数(关键思想为：先把所有可能数顺序放到数组，然后打乱顺序，则保证不重复)

排序

for (i = 0; i < n; ++i)
    a[i] = i;
    
for (i = 0; i < n; ++i){
    pos = rand()%(n – i) + i;
    t = a[i];
    a[i] = a[pos];
    a[pos] = t;
}  
//初始化sr
foreach() {
    sr[a[i]] = 1;
    i++;  
}
//依序输出sr

查找

假设你要查找有序排列的整数集合，但其中缺少几个数，要求查找出缺少的那几个数，这是用位图法合适；

方法跟以上查找用的一样；主要是阐述一下思想，代码仅供参考！^_^