磁盘文件排序
<div id="cnblogs_post_body">磁盘文件排序问题描述，来自《编程珠玑》：
输入：一个最多含有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），程序可以用伪代码表示如下：
<div class="cnblogs_code">//第一步，将所有的位都初始化为0 for i ={0,....n} bit=0; //第二步，通过读入文件中的每个整数来建立集合，将每个对应的位都置为1。 for each i in the input file bit=1; //第三步，检验每一位，如果该位为1，就输出对应的整数。 for i={0...n} if bit==1 write i on the output file
页:
[1]