一、抽象问题
作者在被问到一个问题：“怎样给一个磁盘文件排序”时，起初想到的是一些有关如何在磁盘上实现归并排序的简单思想。而当深究问题的细节时会发现，通过磁盘上的归并排序不能是的问题被很好的解决。于是，对问题进行更客观、更易用的形式描述：
输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7。如果输入文件中有重复的数则出错。
输出：升序排列输入整数的列表，并重写入原文件中。
约束：最大有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间若能在10秒以内则不需要进一步优化。
二、程序设计
1、一种直观的利用磁盘归并排序的思想的解决方案是如果用32位整数来存储每个7位数字的话，1MB空间内科存储250000个号码。因此，可以使用遍历输入文件40次的程序来完成排序。第一次对0~249999之间的整数排序，第二次对250000到499999之间的数排序，以此类推，最后经过40次的文件读写，完成整个文件的排序。此方法有多次的文件的读写，运行时间会很长，不可取。
2、用位图或位向量表示集合。每个7位十进制的整数表示一个小于1000万的整数，我们使用一个具有1000万位的字符串来表示这个文件。若整数i存在于文件中，则第i位为1，否则为0。这种表示利用了一些属性：输入数据限制在相对较小的范围内；数据没有重复；对每条记录而言，除了单一整数外，没有任何其他相关数据。
可分三个阶段来编程，第一阶段将所有位初始化为0，第二阶段读入文件中的每个整数来建立集合，将每个对应的位都设置为1，第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。
三、原理
对小问题的仔细分析有时可得到明显的益处。该实例阐明了一下原理：
1、明确的问题；
2、位图数据结构，该数据结构描述了一个有限定义域内的稠密集合，其中每一个元素最多出现一次并且没有其他任何数据与该元素相关联；
3、多趟算法，多次读入数据，每次完成一步；
4、时间-空间的权衡；
5、简单的设计，简单的设计的标准不是不能再增加任何东西，而是不能再减少任何东西。
四、本章问题的一个位图算法实现
//位图排序法，时空高效的至高境界
#include <stdio.h>
#include <math.h>
#include <time.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
#define M 20
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));
}
int myRand() /* 产生一个0~1之间的随机数 */
{
int num;
num = rand() % 10000000;
return num;
}
int main(void) {
int i;
int j;
int arr[M];
int count=0;
for (i = 0; i < N; i++) {
clr(i);
}
//while (scanf("%d", &i) != EOF) {
// set(i);
//}
srand( (unsigned)time( NULL ) ); //注意这个随机数种子不能放在产生随机数myRand()函数中，否则每次调用都会产生几乎同一个随机数
printf("The count of array is %d:/n",M);
for (j = 0; j < M; j++) { //供简单的正确性测试
arr[j]=myRand(); //注意，输入的数不能重复 //否则当只输入一次
printf("%d/t",arr[j]);
}
for (j = 0; j < M; j++) { //供简单的正确性测试
set(arr[j]);
}
printf("/nAfter Sorted:/n");
for (i = 0; i < N; i++) {
if (test(i)) {
printf("%d/t", i);
count++;
}
}
printf("/nAfter sorted count is %d/n",count); //打印出排序后的数字个数，如果有重复数字作为输入，则排序后数字的个数会比排序前少。
return 0;
}
五、习题1.9解答
使用更多的空间来换取更少的时间存在一个问题：初始化空间本身需要消耗大量的时间。设计一种技术，在第一次访问响亮的时将其初始化为0。方案应该使用常量时间进行初始化和向量访问，使用的额外空间应正比于向量的大小。此方法在空间很廉价、时间很宝贵且向量很稀疏的情况下才可考虑使用。
解答：借助于两个额外的n元向量from、to和一个整数top。就可以使用标识来初始化向量data[0...n-1]。如果元素data[I]已被初始化，那么from[i]<toop且to[from[i]]=i。因此，from是一个简单的标识，to和top一起确保了from中不会被写入内存里的随机内容。data、from、to向量关系如下所示：
变量top初始为0，下面的代码实现对数组元素i的首次访问：
from[i] = top;
to[top] = i;
data[i] = 0;
top++;