C++实现位图排序实例
在《编程珠玑》一书里提到了一种算法导论里没有提到过的位图排序方法，这种排序方法是通过牺牲空间效率来追求时间效率（线性时间）以达到时间-空间折中与双赢的目的。本文以实例形式简单讲一下位图排序思想。
一、问题描述
1.输入：一个至多包含1千万个非负整数的文件
2.特征：①每个数都是小于10000000的非负整数；②没有重复的数字；③数据之间不存在关联关系。
3.约束：①最多1MB的内存空间可用；②磁盘空间充足；③运行时间最多几分钟，最好是线性时间。
4.输出：按升序排列的整数序列。
二、位图排序思想
由于待排序的数据记录较多，我们单纯地使用常见的排序方法时间效率较低，运行时间会很长。而且内存空间有限（限制为1MB左右），所以我们不能同时把所有整数读入内存（如果每个整数使用7个字节来存储，那么1MB内存空间只能存大约143000个数字）。当然我们可以多次读取输入文件，多次排序，但是更好的方案是使用位图排序，可以使用有限的1MB内存空间并只进行一趟排序。
1.根据待排序集合中最大的数，开辟一个位数组，用来表示待排序集合中的整数；
2.待排序集合中的数字在位数组中的对应位置置1，其他的置0；
例如，待排序集合{1,2,3,5,8,13}可以表示为：0-1-1-1-0-1-0-0-1-0-0-0-0-1
这样排序过程自然可以分为三步：
第一步：将所有的位都置为0；
第二步：通过读入文件中的每个整数，将每个对应的位都置为1；
第三步：检验每一位，如果该位为1，输出对应的整数。
注意：位图排序是使用一个二进制位而不是一个整数来表示0或1，这样可以大大地减少所需要的内存空间。使用位图排序的前提是要知道待排序序列中的最大数。位图排序的缺点是有些数没有出现过，仍要为其保留一个位。故位图排序比较适合关键字密集的序列，例如一个城市的电话号码。
伪代码如下：
/*Phase1:initializesettoempty*/ fori=[0,n) bit[i]=0 /*Phase2:insertpresentelementsintotheset*/ foreachiintheinputfile bit[i]=1 /*Phase3:writesortedoutput*/ fori=[0,n) ifbit[i]==1 writeiontheoutputfile
性能：时间复杂度可达O(n)，1MB包含8*1024*1024个位，所需内存10000000/(8*1024*1024)=1.20MB，如果不是严格限制的话可以看做基本符合要求。
三、位图排序实现
位图排序时，我们需要考虑：给出一个数，如何找到其对应位图的位置，方法就是首先找到该数对应的字节，然后在找到该数对应的位。例如：
unsignedcharbitmap[2]; /*可以表示16个数，即0～15*/
一个字节有八位，5表示第0个字节的第5位上；14表示第1个字节的第6个位上。
在这里为了简化位处理，我们使用C++标准库的bitset容器。bitset是C++提供的一种位集合的数据结构，它让我们可以像使用数组一样使用位，可以访问指定下标的bit位。和其他容器一样，bitset也是一个模板类。具体的bitset方法可以查看std::bitsetreference。
下面我们使用bitset容器进行位图排序：
/*************************************************************************
>FileName:BitSort.cpp
>Author:SongLee
************************************************************************/
#include<bitset>
#include<iostream>
usingnamespacestd;
#defineMAX20
intmain()
{
intarr[10]={5,1,2,13,7,10,0,20,16,9};
bitset<MAX+1>bit;
/*将对应位置置1*/
for(inti=0;i<10;++i)
{
bit.set(arr[i]);
/*bit.set(n)表示将第n位置1*/
}
/*输出排序结果*/
for(inti=0;i<MAX+1;++i)
{
/*bit.test(n)判断第n位是否为1*/
if(bit.test(i))
{
cout<<i<<"";
}
}
cout<<endl;
}
输出结果：01257910131620