编程珠玑: 开篇
问题引入
输入：一个最多包含 n 个正整数的文件，每个数都小于 n，其中 n = 10^7。并且输入文件中的正整数没有重复数据，数据之间没有任何关联。
输出：按照升序排列输出整数列表。
约束：最多有 1MB 内存，但是有充足的磁盘空间使用。要求程序运行时间最多有几分钟。
程序设计
磁盘文件归并排序
通过优化基于磁盘的归并排序实现；这种做法需要生成中间文件，并且程序运行时要多次读取中间文件
多趟排序
文件中的正整数最大为 10^7，假设每个数都使用 32 位整数来表示，则每个整数需要 4 Byte，那么在 1 MB 内存中最多存储 250000 个数字。因此可以通过多次遍历输入文件来完成排序：在第一趟遍历中，将 0 — 249999 之间的整数都读入到内存中，并对这 250000 个数进行内存排序，然后写入到输出文件中；同理，第二趟遍历将 25000 -499999 之间的整数读到内存中并排序，然后顺序写入到输出文件；依此类推。这样，基本需要 40 次输入文件的遍历可以将所有整数顺序输出。
这种方法的好处是没有产生中间文件，但是付出的代价是需要遍历输入文件 40 次。
位图排序
优势：读取输入文件一次，并且没有中间文件产生。
位图数据结构描述了一个有限定义域内的稠密集合，其中每一个元素最多出现一次并且没有其他任何数据与该元素相关联。
即使这些条件没有完全满足（例如存在重复元素或者额外的数据），也可以用有限定义域内的键作为一个表项更复杂的表格的索引。
位图或位向量表示集合：当整数 i 在原数组中存在时，则位图中第 i 位为 1；否则为 0。用一个长度为 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
在上面的问题中，我们使用一个具有 10^7 个位的数组表示整个文件中整数的集合，当整数 i 在文件中存在时，第 i 位为 1.
使用位图来实现利用了三个在排序问题中并不常见的属性：
- 输入数据限制在相对较小的范围内
- 数据没有重复
- 对每个记录而言，除了单一整数外，没有任何其他关联数据
实现
位图排序实现分为三步：
- 所有位置 0
- 通过遍历输入文件来建立集合，将每个对应的位都置为 1
- 遍历位图数组，如果该位为 1，则输出对应的整数
// initialize
for i = [0,n)
bit[i] = 0
// insert present elements into set
for i in the file
bit[i] = 1
// write sorted output
for i = [0,n)
if bit[i] == 1
write i output
引申
- 通过位逻辑运算实现位向量
- 如何生成 0 至 n-1 之间的 k 个不同的随机整数
- 如果每个整数不是最多出现 1 次，而是最多出现 10 次，如何处理