问题来源
在实际运用场景里，经常会遇到把大量数据有序输出，文件的排序等等问题。一般的排序算法针对数据量不大的情况下，二叉树排序和快速排序针对现实中的随机数据时间复杂度为O(NlgN),性能表现已经很不错了，因此这两种方法被广泛使用。
但是，在企业级数据量情况下，这两种排序耗费的时间就会显著增长，以至需要非常长的时间才能得到结果，而且在排序的过程中，由于插入和选择结点的操作会使得CPU满负荷工作，这对于长期工作的服务器来说是不利的。
因此，在这种海量数据排序的需求刺激下，产生了一种简易的”哈希”方法，那就是位图排序。
排序思想
位图排序的思想非常简单，那就是将一个个数据映射到它在有序的数轴上的一点，这个数轴可以是一个数组，数字的大小就是哈希因子，所以在遍历一遍数据集，设置好这些数字的点表示之后，我们就可以根据相应位置的状态，反过来来确定数据集中是否有这个数字，由于我们是有序的遍历的，因此查找出来的数字也是有序的，这样间接地达到了我们的目的。
位图很像数学中的数轴的概念，有哪些数字，就会在相应的位置标记它们，最后数据都是有序的。而且这种方法，一个数字占用的位置只有一个bit,对于0~2<<32的4字节非负整数范围来说，最大的数为42亿，在实际应用场景下基本足够，而所需要的空间占用大概只需要2<<32/8/1024^2=512M的内存，在内存占用上和效率上都有着无可比拟的优势。
实际测试
说了这么多，当然需要实际测试一番，才能证明位图排序真的在海量数据排序上具有优势。
例如在我的服务器上，随机生成1000W个整数，现在需要将它们排序。那么对于快速排序，二叉树排序和位图排序，分别需要多少时间呢？
- 机器环境GCC5.3.1,编译参数-std=c++11 -O3
- 源代码详见topcoder
###1. 快排
- 主要分为partiiton和sort两个阶段，使用STL自带的快排实现
- 注意,STL的sort会在递归sort层数过多时变成堆排序，虽然时间复杂度都是O(NlgN),但是这种测试只是作为一种参考
- 而且系统在每一次递归调用时都会保存栈信息，递归层数太多会导致栈溢出。所以，在海量数据排序一次性排序中，使用快排并不现实。基本都会借助归并的思想去分块排序然后合并。
STL的sort所用时间
###2. 二叉树排序
- 测试中使用的红黑树实现的有序multiset,由于红黑树查询、删除、插入的时间复杂度均为O(lgK),因此遍历一遍数据之后时间复杂度就是O(NlgN)了
- 但是可能在茶如大量数据时频繁创建和改变节点属性，因此综合性能可能不如快速排序。以下的时间即可说明这个问题。
红黑树实现的排序所用时间
###3. 位图排序
- 位图排序可以看做是一种特殊的哈希排序。使用元素数值作为哈希函数
- 但是这种方法在有重复元素的环境下，需要在遍历设置位图状态时，记录重复元素的个数。
- 另一个问题就是C/C++程序运行时分配的栈空间是有限制的，分配几百M的内存运行时就会报错，所以我们需要使用dynamic_bitset,这种动态bitset由boost库实现，是在堆上分配的内存，因此突破了限制。
-与bitset不同之处还有dynamic_bitset的set效率没有STL bitset高。
位图实现的排序所用时间
总结
- 在上面的结果中，可以看出，因为快排不是单纯地快排，STL内部的内存分配等都有优化，因此出现了比位图排序快的情况
- 在海量数据情况，一次将数据排序是不可能的，因此这次的测试规模只是反映一种简单的比较。实际情况中，需要结合排序和分治的思想。
- 位图排序的用途不只是排序，由于它每个比较的单元只占用1bit,很适合处理大量数据和文件的问题，在Linux的多路复用I/O函数select中,它作为文件描述符的状态集使用，每次查询bit位数值就可以判断相应文件描述符IO状态。