第一章 开篇

程序设计中需求的明确化非常重要，开篇两人的对话对此进行了说明

A：我该如何对磁盘文件进行排序？B：需要排序的内容是什么？文件中有多少条记录？每个记录的格式是什么？A：该文件包含至多10,000,000个记录，每条记录都是一个7位整数。B：如果文件那么小，为什么要使用磁盘排序呢？为什么不在主存中对它排序？A：该功能是某大型系统中的一部分，大概只能提供1MB主存给它。B：你能将记录方面的内容说得更详细一些吗？A：每个记录是一个7位正整数，没有其它的关联数据，每个整数至多只能出现一次。..

之后我们获得了明晰的需求

输入：所输入的是一个文件，至多包含n个正整数，每个正整数都要小于n，这里n=10^7。如果输入时某一个整数出现了两次，就会产生一个致命的错误。这些整数与其它任何数据都不关联。输出：以增序形式输出经过排序的整数列表。约束：大概有1MB的可用主存，但可用磁盘空间充足。运行时间至多允许几分钟，10秒钟是最适宜的运行时间。

在有限的条件下，我们有多种的解决方案，最直接的，由于内存只能容纳一小部分数据，因此将数据分为40份，每次读取一份进行快速排序，写入中间文件中，最后进行统一的归并可以获得需要的结果。然而多次的读写文件操作将为大大降低程序的效率，需要更为优越的办法。

位图在实际运用中十分常见，我们可以用10000000位的字符串来表示这个数据集，对于有的数据就在相应的位上置1，反之则置0。从而我们的算法可以简化成以下3个步骤：第一，初始化所有的位为0；第二，读取文件中每个整数， 如果该整数对应的位已经为1，说明前面已经出现过这个整数，抛出异常，退出程序 (输入要求每个整数都只能出现一次)。否则，将相应的位置1；第三， 检查每个位，如果某个位是1，就写出相应的整数，从而创建已排序的输出文件。

实例中，问题的定义占据了非常重要的地位，明晰的定义将有助于针对性的解决问题，同时巧妙的数据结构表达将极大的节省代码量和时间成本。

 

第二章 啊哈 算法

第一章介绍了如何定义一个编程问题，第二章则介绍下一步，即如何利用原语来解决问题，其中主要就3个算法问题进行展开。

问题一：给定一个包含32位整数的顺序文件，它至多只能包含40亿个这样的整数， 并且整数的次序是随机的。请查找一个此文件中不存在的32位整数。 在有足够主存的情况下，你会如何解决这个问题？ 如果你可以使用若干外部临时文件，但可用主存却只有上百字节， 你会如何解决这个问题？

如果在内存无限的情况下，我们可以使用第一章中的位图技术进行求解。同时问题还提出如果内存只有上百字节，在若干外部临时文件的帮助下的情况。如此可以利用二分法的思想，因为二进制中每一位要么是0要么是1，对这40亿数来说，进行如下操作：从最高位到最低位，对于最高位为1的分在一组，最高位为0的分在另一组，这样40亿数据就被分配成了两组了，若两组数有相同的个数，那么我们可以判断这两组数中都缺少了全体数（2^32个）中的某一个或者多个数，可以任选一组再次进行二分法。若两组数目不同，我们可以肯定是小的那部分数据肯定缺少了某一个或者多个数。因此对小的那组进行二分法，最终就能找到缺少的数。

 

问题二：请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3， 那么向量abcdefgh旋转之后得到向量defghabc。

该问题有多种的解法。一是借助中间量t，将x[0]的数放入t中，将x[0]置为x[i]，x[i]置为x[2i]并直到x[0]的元素结束这次移动，之后开始移动x[1]并以此类推直到完全移动完成。

另一种方法是利用三次的反转达到目的，显得更为巧妙

reverse(0, i-1); // cbadefghreverse(i, n-1); // cbahgfedreverse(0, n-1); // defghabc

 

问题三：给定一本英语单词词典，请找出所有的变位词集。例如，因为“pots”， “stop”，“tops”相互之间都是由另一个词的各个字母改变序列而构成的， 因此这些词相互之间就是变位词。

这里需要用到一种签名的概念，因为对某一个单词中字母打乱并一一匹配其它单词的程序需要的时间令人难以置信，因此我们需要从另一个角度来考虑问题。首先将每个单词按字母表顺序进行排序，比如“deposit”和“deiopst”的签名都是“deiopst”，接着将签名进行排序，可以将具有相同签名的单词排到一起，最终将这些具有相同签名的单词输出就可以得到需要的变位词集了。