位图排序

algorithm

本篇记述一下习题 1.6-3 的解题笔记及感想

现在知道很多种高效排序算法如快排、归并排序、堆排序等等，但有时或许针对特定问题有更加有效的手段来解决。

问题

首先大致描述一下问题，比如我们现在有一个记录了大量数字的文件，这些数字不重复，数字都小于 10^6，使用位图数据结构对其中所有数字进行排序。

向量坐标标记法

解题思路，首先把所有的数字在一个位向量结构中表示出来
我们知道，通常整形（int）使用 32 位空间来表示，我们的目标就是使用一位来标记一个数字，具体怎么做呢。比如可用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数的集合：

# {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

这个集合就表示了 {1, 2, 3, 5, 8, 13}，此字符串中代表集合中数字的位都置 1，其余为 0

这样一来就可以使用 100w + 1 个位的字符串来表记这个文件的所有数字。

解题思路转化为三步：
1. 将所有位置 0
2. 把读入的每个数字对应的位置 1
3. 遍历整个位图结构，顺序输出所有为 1 的位置对应的数字

位操作

要使用位图结构进行排序，首先要解决的问题就是如何通过位逻辑运算来实现位向量。
其实很简单，代码如下：

#define MASK 0x1F
#define N 1000000
int a[1 + N/32]
void set(int i){
    a[i >> 5] |= (1 << (i & MASK))
}
void clr(int i){
    a[i >> 5] &= ~(1 << (i & MASK))
}
int check(int i){
    return a[i >> 5] & (1 << (i & MASK))
}

排序

接下来的排序实现就很简单了

int main(void){
    int i;
    for(i=0;i<N;i++){
        clr(i);
    }
    while(scanf("%d", &i) != EOF){
        set(i);
    }
    for(i=0;i<N;i++){
        if(check(i)){
            printf("%d\n", i);
        }
    }
    return 0;
}

这种排序方式能够极大的节省排序过程中的空间开销，当然对于内存中的排序来说，快排是相当高效的且实现极为精简。但是当你的内存无法全部装下待排序数据时，位图就将是一个很好的选择。

‘阻碍解题者正确理解问题或取得答案的心智壁垒’ -- Adams - 概念壁垒