问题的提出
一个最多包含n个正整数的文件，每个数都小于n,其中n=10^7。假设最多只有1M的内存空间可用，在考虑空间和时间的优化的情况下，请问如何对其进行排序？
常规思想
我们假设这些整数都是用整型存储(一般整型的大小为4个字节)，那么1M字节可以存储250 000个数据。由于输入文件最大可能有10^7个数据，因此可以通过遍历输入文件40次来完成排序。第一次将在[0,249 999]范围内的整数读入到内存中，第二次将在[250 000,499 999]范围内的整数读入到内存中，依此类推。每读入一次数据，就对这些数据进行排序(可以采用一些排序算法)并输出。显然，我们要对文件进行反复的读写，这不是我们所期望的。下面我们提出一种更加合理的算法—位图排序算法。
位图排序算法
如果我们想一次读取文件的全部内容(最大可能有1000万个整数)，问题在于如何用1M的内存来表示这些数。我们可以用位图表示集合。我们可以用一个长度为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 集合中有数值的位置都置为1，其它所有位置为0.
这样我们就用一个具有1000万个位的字符串表示了这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。因此我们可以分下面三步来解决这一问题：
- 将字符串的所有位置为0即初始化
- 逐一读取文件中的每个整数，并将以该整数为下标的对应为置为1
- 逐一检查字符串的每一位，如果为1，则输出这一元素的下标
时间、空间的折中与双赢
我们在很多问题中，都遇到着时间和空间的折中，毛泽东在论持久战中也说过以空间换时间(据说是蒋介石先提出来的)。但是上面的程序是：减少程序空间需求的同时也减少了其运行时间。因为需要处理的数据变少了，从而处理数据所需要的时间变少了，同时没有反复的读取文件，进一步避免了磁盘的访问时间。当然，只有当原始设计非最佳方案时，才有可能时空双赢。
奥卡姆的剃刀
设计者确定其设计已经达到完美的标准不是不能再添加任何东西，而是不能再减少任何东西。
原文： http://blog.csdn.net/tengweitw/article/details/45932981
作者：nineheadedbird
