Warning: Undefined array key "HTTP_REFERER" in /www/wwwroot/prod/www.enjoyasp.net/wp-content/plugins/google-highlight/google-hilite.php on line 58

1M = 1024k
1K = 1024bit
1bit = 8位
一个整数占32位(4bit)，那么1M共可存放的整数个数为：1024*1024/4=262144个

题目：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。
约束：最多有1MB的内存空间可用，有充足的磁盘存储空间。
直接读取所有文件入内存进行排序是不现实的，因为最多有1MB空间，最大可存放的数字是262144个
，可以分段取：从头到尾一段一段的取数据，在0-250000的放入内存并排序输出
从头到尾一段一段的取数据， 在250000-500000的放入内存并输出
从头到尾一段一段的取数据， 在500000-750000的放入内存并输出
从头到尾一段一段的取数据， 在750000-1000000的放入内存并输出

位图法排序:hash对应
定义一字符串，长度为10^7,初始每位为0，每位的顺序对应每个数字，分段读入数字，将对应位设置为1，
如：对于数字3，将此字符串的第三位设置为1即可。
然后输出为1的位数即可，不需排序。
与上边的方法相比，上边的方法要40次全文件扫描，而此方法仅需一次，并用结果不用排序
以空间换时间。

应用范围：1，知道上限。2，数字没有重复

推广：
给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中
unsign int范围为0~2^32-1(4294967295≈5*10^9) 使用位图hash对应5*10^9/8/10^3/10^3 = 625MB.

1. 我们使用625M的字符串。每一位设置为0.
2. 将40亿个unsign int 遍历一遍。使用位图法将字符串中的对应位转化为1。
3. 读取“再给一个数i” 查看bit[i] 是否为1，1则有存在，0则不存在。