问题是这样的,对于一组具有如下特性的数据:
- 都是非负整数
- 没有重复的数据
- 数据量很大
如何利用一种比快速排序还快的算法来给这组数据排序。
对于这组数据的特殊性,我们可以考虑利用位图的方法:首先我们申请一块内存空间并把这块内存的所有位都置0,然后依次读入这组数据,如果读入的数据为 i ,那么就这块内存的第 i 个bit为置为 1,数据读入完成之后,我们就可以从头开始一位一位地依次遍历这块内存,如果第 i 个bit位为 1 那么就输出 i ,最后输出的数据就是原始数据的从小到大的一个排序了。
代码:
1 |
|
FAQ
Q: 如果每个数至多出现10次呢?
A: 可以用 4 个 bit 位来保存一个数出现的次数
Q: 如果不知道出现多少次呢?
A: 可以参考之前的一篇文章:如何给数百万考生的成绩排序
读 《编程珠玑》 笔记