•输入
–给出至多10,000,000个正整数的序列
•特征：
–每个数都小于10,000,000
–数据不重复且 数据之间不存在关联关系
•输出：增序输出序列
•约束：
–内存容量1MB
–磁盘空间充足
–运行时间至多几分钟---最好线性时间
位图排序：
•引入位图排序的原因
–对计数排序算法进行空间压缩
•思想
–采用一个二进制位对应一个整数
•前提
–要知道待排序数的最大数
•存储
•使用字符或整形都可以
优化
•优化的原因
–我们需要10,000,000个数表示10,000,000个位
–1MB的包含8*1024*1024个位
–所需内存容量：10,000,000/(8*1024*1024) = 1.20MB
•假如严格限制为1MB，可以采用的策略：
–两次遍历待排序列
•两次遍历待排序序列
–思想：把数据分成两部分，分别执行位图排序
–具体思路：
•第一次对1- 5,000,000之间的数排序
•之后再对5,000,001 -10,000,000之间的数排序
–需要存储空间为：5,000,000/(8*1024*1024) = 0.596MB
–总体上消耗的空间为0.596MB。
位图排序使用范围及应用
•位图排序使用范围
–(1)非负整数
–(2)每个整数最多出现一次
–(3)最大整数小于N
–(4)整数之间相互独立
•相关应用
–位图法存数据
–使用位图法判断数是否存在重复
–给40亿个不重复的unsignedint的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中
