返回信息流输入:
所输入的文件,至多包含n个正整数,每个正整数都小于n,题目中n = 10^7,如果输入时某个正整数重复出现俩次,就会产生致命的错误,这些整数,与其他任何数据都不相关.
输出:
以增序形式输出经过排序的整数列表
约束
至多只有1MB(包括程序本身)可用的主存,但是可以用的磁盘空间是充足的,运行时间至多几分钟,10秒针是最适宜的运行时间.
解决方案为：
使用一千万位的字符串表示该文件,当且仅当整数i在该文件中的时候,第i位才被设置为1,这种表示法使用了这个问题中的三中属性,输入的范围相对小一些,并且还不包括重复的数据,而且没有数据和单个整数以外的每一记录相关联
算法实现分三阶段
1 设置每个位为0
2 读取文件,将相应的位设置为1
3 检查每个位,当为1时,将整数写入
我觉得1M内存无论如何也放不下10,000,000个整数哇，即使用bit表示也不行吧？
这是一条镜像帖。来源：北邮人论坛 / cpp / #37060同步于 2010/3/26
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
【请问】编程珠玑上的开篇例题：外排序
focuson
2010/3/26镜像同步3 回复
订阅后，新回复会通过你的通知中心匿名送达。