磁盘文件排序
问题描述，来自《编程珠玑》：
输入：一个最多含有n个不相同的正整数的文件，其中每个数都小于等于n，且n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为***结果。

分析：

1、归并排序。你可能会想到把磁盘文件进行归并排序，但题目要求中，你只有1MB的内存空间可用，所以，归并排序这个方法不行。

2、位图方案。例如正如《编程珠玑》一书上所述，用一个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。

参考《编程珠玑》一书上的位图方案，针对10^7个数据量的磁盘文件排序问题，可以这么考虑，由于每个7位十进制整数表示一个小于1000万的整数。可以使用一个具有1000万个位的字符串来表示这个文件，其中，当且仅当整数i在文件中存在时，第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性：1、输入数据限制在相对较小的范围内，2、数据没有重复，3、其中的每条记录都是单一的正整数，没有任何其它与之关联的数据。
所以，此问题用位图的方案分为以下三步进行解决：
第一步，将所有的位都置为0，从而将集合初始化为空。 
第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。 
第三步，检验每一位，如果该位为1，就输出对应的整数。 
经过以上三步后，产生有序的输出文件。令n为位图向量中的位数（本例中为10000000），程序可以用伪代码表示如下：

//第一步，将所有的位都初始化为0   
for i ={0,....n}  
    bit[i]=0;  
  
//第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。   
for each i in the input file  
    bit[i]=1;  
  
//第三步，检验每一位，如果该位为1，就输出对应的整数。   
for i={0...n}  
    if bit[i]==1  
      write i on the output file  

不过很快，我们就将意识到，用此位图方法，严格说来还是不太行，空间消耗10^7/8还是大于1M（1M=1024*1024空间，小于10^7/8）。
既然如果用位图方案的话，我们需要约1.25MB（若每条记录是8位的正整数的话，则10000000/(1024*1024*8) ~= 1.2M）的空间，而现在只有1MB的可用存储空间，那么究竟该作何处理呢？可以多次使用位图进行排序。

3、多路归并。把这个文件分为若干大小的几块，然后分别对每一块进行排序，最后完成整个过程的排序。k趟算法可以在kn的时间开销内和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。比如可分为2块（k=2，1趟反正占用的内存只有1.25/2=0.625M），1~4999999，和5000000~9999999先遍历一趟，处理1~4999999的数据块（用5000000/8=625000个字的存储空间来排序0~4999999之间的整数），然后再第二趟，对5000001~1000000这一数据块处理。

针对这个要分两趟给磁盘文件排序的具体问题编写完整代码，如下:

View Code

上述的位图方案，共需要扫描输入数据两次，具体执行步骤如下：
第一次，只处理1—4999999之间的数据，这些数都是小于5000000的，对这些数进行位图排序，只需要约5000000/8=625000Byte，也就是0.625M，排序后输出。
第二次，扫描输入文件时，只处理4999999-10000000的数据项，也只需要0.625M（可以使用第一次处理申请的内存）。因此，总共也只需要0.625M。

磁盘文件排序的C实现

1、内排序
由于要求的可用内存为1MB，那么每次可以在内存中对250K的数据进行排序，然后将有序的数写入硬盘。
那么10M的数据需要循环40次，最终产生40个有序的文件。

2、多路归并排序
（1）将每个文件最开始的数读入（由于有序，所以为该文件最小数），存放在一个大小为40的first_data数组中； 
（2）选择first_data数组中最小的数min_data，及其对应的文件索引index； 
（3）将first_data数组中最小的数写入文件result，然后更新数组first_data（根据index读取该文件下一个数代替min_data）； 
（4）判断是否所有数据都读取完毕，否则返回（2）。

完整代码如下：

View Code

测试数据：生成1000万个不重复的正整数

View Code