排序(位图数据结构)

对于规模比较大的数据集，但又不是特别特别大的数据集来说，使用位图数据结构的排序是一个不错的选择。注：要求数据没有重复。

位图/位向量

表示一个整数合集{1，2，3，5，8，13}可以使用如下字符串：

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

这种表示方法，1MB大小的空间可以表示月800万个数字，与十进制的7位数字1000万接近。

// phase 1: initialize set to empty
for i = [0,n]
    bit[i] = 0;

// phase 2: insert present elements into the set
for each i in the input file
    bit[i] = 1;

//phase 3: write sorted output

for i = [0,n]
    if bit[i] == 1  
        write i on the output file

位图数据结构还可以用来检查数据集的重复性

（编程珠玑）