coding小世界

第一章 开篇

首先作者提出一个实际问题：

如何给磁盘的某个文件排序，更具体来说就是是对一个最多包含1千万条记录，每条记录都是7位整数的文件，而且只有1MB的内存可以使用

从实际问题中提炼出更明确的数学定义：

输入：一个最多包含n个整数的文件，每个数都小于n，，其中n=10^7。可以保证输入文件中不存在重复整数
输出：按升序排列的输入整数的列表
约束：1MB左右的内存空间，充足的磁盘存储空间。运行时间最多几分钟，控制在10秒内不再需要进一步优化

考虑一般的解法，直接读入所有的整数，然后进行快排堆排之类的排序，时间复杂度很明显是O(nlogn),但空间复杂度是O(n),即如果n=10^7时，用4个字节的int型存储每个整数，那么需要的空间是(4*107)/210210=38MB,很显然超出了内存限制，而考虑实际n的大小限制和每个整数只会出现一次的限制，而所谓的排序也只是把从文件中的整数按在1－n内出现的顺序输出而已，因此只要对n之内出现的整数做一下标记最后输出标记过的整数就可以了，考虑到这，位向量（也叫位图）就成了比较合适的数据结构的选择，每个位的0、1值表示一个数字是否出现过，实现的时间复杂度为O(n),空间复杂度为O(n),考虑n取最大值10^7时，需要的空间为107/8/210/210=1.2MB,代码实现如下：

  本文关键词：编程珠玑，由笔耕文化传播整理发布。