今天要说的是个经典的排序问题，从《编程珠玑》上看来的，题目是这样的：

输入：一个文件中存储着不超过10,000,000个正整数，且每个数都小于10,000,000。这些正整数不会
重复，而且相互独立，之间不存在关联关系。

输出：完成排序的正整数列表。

要求：时间复杂度和空间复杂度尽量低。

首先想到的是归并排序(百度百科的解释在这里)，但由于归并要保存中间过程产生的有序数据列表，结合庞大的数据量，空间的消耗过大。

排除！

然后再来看常用的快速排序(百度百科的解释在这里)，快速排序不需要记录中间数据，但是快排是一种多趟程序，会频繁的读取文件(或者将全部数据读入内存，那就会存在和归并排序一样的缺点)，效率低。

再排除。

看看理想的算法流程应该像下面这样。

从这个理想图可以看出来，现在的问题归结为如何才能一次性的把这不超过10,000,000个正整数读入到内存中。

好了，现在我们正式介绍一下题目中的名词：位向量。所谓位向量就是由一些二进制位组成的向量。我们可以用位向量来表示一个数组，例如数组

{1,2,3,5,8,13}

可以表示成

{0,1,1,1,0,1,0,0,1,0,0,0,0,1}

索引值等于原数组中元素的位为1，否则为0。

这种表示法是有前提的

1) 数组中都是非负整数；

2) 数组中不存在重复的数;

3) 数组所有元素小于某个特定值。

具体来说就是，可以用20位来表示一个所有元素为非负整数，值各不相同且最大值不超过20的数组。

换句话说，在满足条件的情况下，这种表示法可以用一个bit表示一个正整数，那一次性读入10,000,000个正整数也就不成问题。我们的理想算法也就呼之欲出了，下面是步骤：

第一步，初始化这个比特位集合中的所有位为0

for i = [0,  10,000,000)

    bit[i] = 0

第二步，读入待排序的正整数

for each i in the input file

    bit[i] = 1

第三步，输出排序结果

for i = [0, 10,000,000)

    if bit[i] == 1

       write i on the output file

这三步即完成整个排序过程。怎么样，代码是不是简洁而高效？

再想想还有什么问题没有？对，问题是C++中并没有二进制位的数据类型。别担心，通过C++提供的位操作，我们仍然能够实现位向量表示法。代码实现如下：

const int bitsPerWord = 32;//int型为32位
const int shift = 5;       //2的5次方
const int mask = 0x1F;     //模数
const int n = 10000000;
static int a[1 + n / bitsPerWord];

void set(int i)
{
    a[i >> shift] |= (1 << (i & mask));
}
void clr(int i)
{
    a[i >> shift] &= ~(1 << (i & mask));
}
int test(int i)
{
    return a[i >> shift] & (1 << (i & mask));
}

如果你看不懂位操作，没关系，我也刚搞懂，下面是我加的一些注释，希望能有点帮助。

Read the rest of this entry »