本篇记述一下习题 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 个位的字符串来表记这个文件的所有数字。
解题思路转化为三步：
- 将所有位置 0
- 把读入的每个数字对应的位置 1
- 遍历整个位图结构，顺序输出所有为 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 - 概念壁垒