排序(位图数据结构)

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

位图/位向量

表示一个整数合集{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

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

(编程珠玑)