开篇提出了一个排序问题
问题描述：在一个磁盘文件中存在10000000左右个正整数，不存在重复元素，每个数在区间[1, 10000000]中。
输出：将这些整数升序排列，并存到一个磁盘文件里。
约束：大约有1M的内存空间可用，运行时间在10秒左右。
分析：对于1千万左右的数字，我们至少要用4个字节来存储。如果同时将1千万个这样的数字读入内存，大约需要38M左右的内存，
这远远超过题目要求。这种情况下，需要对磁盘文件进行多趟的排序，这样的话代码会很复杂，而且很难满足时间要求。
解决方法：文中提出用位图（或者叫位向量）来表示集合。比如，数字集合{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}。可见将位图中第i位置为1，来表示数字i。如例子中位图的第1，2，3，5，8, 13位被置为1.
位图的优点：
节省内存空间。对于题目中的1千万个数据，只需要1千万位（1M左右）的内存就可以满足要求。省略了排序过程。位图本身就有顺序，因此满足时间要求。相关代码：
这是书中给的参考代码：
#include <iostream> #include <cmath> using namespace std; #define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 unsigned int a[1 + N/BITSPERWORD] = {0}; //将位图的第i位置为1 void set(unsigned int i){ a[i >> SHIFT] |= (1 << (i & MASK)); } //将位图的第i位置为0 void clr(unsigned int i){ a[i >> SHIFT] &= ~(1 << (i & MASK)); } //检查位图第i位 int test(unsigned int i){ return a[i >> SHIFT] & (1 << (i & MASK)); } int main(){ set(32); cout << a[1] << endl; return 0; }这是我自己写的代码：
#define N 10000000 bool a[1 + N] = {0}; void myset(int i){ a[i] = true; } void myclr(int i){ a[i] = false; } int mytest(int i){ return a[i] ? pow(2, i) : 0; } int main(){ myset(5); cout << mytest(5) << endl; return 0; }问题扩展：
第五题：内存空间不足怎么办？原题中给的内存是1M，如果现在只有0.8M的内存，这时候需要怎么办呢？
解答：由于内存的限制使得不能一次将数据全部读入内存。可以进行多趟读取。比如，进行两趟读取。第一趟只处理1到5百万的数据，第二趟处理5百万到1千万的数据。这样一来，内存只需要0.5M（之前的一半）， 而消耗的时间将是之前的两倍。
第六题：如果每个数字可能重复出现，且最多有10个相同的数字该怎么办？
解答：原题中的位图，对于每一位，0表示没有出现，1表示出现。如果一个数字可能出现多次，那么这个数字的状态将会有，出现0次，出现1次， 出现2次，，，出现10次的情况，一共会有11中状态，那么至少需要4位才能表示这11种状态。这种情况下，用4位表示一个数字出现的次数，内存的消耗将会是之前的4倍。
第十题：一个商店的客户名单中，用客户的电话号码为关键字来标记客户资料。请问怎么设计客户资料的数据库，使得对客户资料的插入和检索更为高效？
解答：对于电话号码来说，前面几位数字很有可能出现相同的情况，而最后两位是随机出现的。用10 * 10个箱子组成一个二维矩阵，矩阵的每一行（列）都表示0到9这十个数字，行、列组成电话号码的最后两位，将对应的用户资料放入对应的箱子中。这种思想类似于散列表的思想。通过简答的操作，就可以在效率上提高很多。
