J*******g
发帖数: 381 | 1 【 以下文字转载自 CS 讨论区 】
发信人: JiayiWang (noname), 信区: CS
标 题: 请教一个初级算法问题
发信站: BBS 未名空间站 (Fri Jun 26 17:30:35 2009, 美东)
要是有海量的数据要作排序， 但是内存空间有限。 譬如4G的内存，但是有4倍于内
存的数据要排序，请教一下用什么算
法比较好啊？ 多谢！ |
e****d
发帖数: 333 | 2 我想到的比较直接的办法，不一定最好。
假设原始数据都随机。
先分成4段，分别quicksort排好存盘。
然后就对这4个文件用merge sort排。
内存一满就存盘，存盘是连续的存成一个文件就行了。
只是merge sort 的时候，对那4个文件的，要设好每次读进来的缓存大小。保险点就设
置小些，主要花读盘时间就行了。 |
J*******g
发帖数: 381 | 3 Thanks a lot!
【在 e****d 的大作中提到】
: 我想到的比较直接的办法，不一定最好。
: 假设原始数据都随机。
: 先分成4段，分别quicksort排好存盘。
: 然后就对这4个文件用merge sort排。
: 内存一满就存盘，存盘是连续的存成一个文件就行了。
: 只是merge sort 的时候，对那4个文件的，要设好每次读进来的缓存大小。保险点就设
: 置小些，主要花读盘时间就行了。
|
e****d
发帖数: 333 | 4 如果你按照我的方法写代码，要小心，在merge sort 的时候，每次写盘，缓存里一般
会有没排好序不能存盘的残留，小心处理。 |
e****d
发帖数: 333 | 5 也可以merge每次两个文件块。
lz可以看看外部排序的东东。 |
