编程珠玑 第二版 第一章例子的思考

weiqiboy

问题：
输入，输入为一个文件，至多包含n个正整数，每个正整数都小于n，这里n=10 的7次方（最多用40MB主存空间）。
如果输入时某个整数出现了两次，就会产生致命错误。
输出：以增序输出经过排序的整数列表。
约束：只有1MB的可用主存（代码除外）；但磁盘空间非常充足。

解决方法：分40次读入输入文件，第一次读入0-249999之间的数（最多占1MB），排序后输出到文件中，
第二次读入250000-499999之间的数，排序后输出到文件，第40次读入排序9750000-9999999之间的整数
并输出到文件，至此所有数据都已经排好序。这个方法确实很巧妙，但我想说的是排序方法，书中指出
用快速排序很快，但我想在没有多余空间的情况下是否能用快速排序呢？并且在目前这种情况下，快速排序
未必是最快的方法。基于排序对象是整数而且无重复数据的这一事实，我们可以设一个250000个元素的整数数组，第一次
输入（0-249999）可以各就各位，即0存入元素0，249999存入元素249999，一遍即可排好序，而且也无须
额外的存储空间，第二次（250000-499999）把每个待排序的数减去250000，一样可以与数组一一对应，第三次则减去500000，
以后以此类推。

[ 本帖最后由 weiqiboy 于 2007-12-20 17:25 编辑 ]

evaspring

doctorjxd

看过。