4G的整形排序，可用内存为200M，怎么排？

system888net

原帖由 aaaaa5aa 于 2009-8-25 19:16 发表

200M内存+磁盘或u盘.，怎么实现

举一个最笨的方法(注意是最笨的,也不严谨,实际中不要去用,只是用来说明一个道理)来说明.
比如10个数字:
int n[]={3,1,2,8,4,6,5,9,0,7};

内存只能同时放3个数字,那么:
1. 读3个数字出来.     3,1,2 比较出最小的, min=1,并在一个文件current_i_file中写入下标1
2. 读2个数字出来.     8,4,min 比较出最小的, min=1
3. 读2个数字出来.     6,5,min 比较出最小的, min=1
4. 读2个数字出来.     9,0,min 比较出最小的, min=0 ,并在一个文件current_i_file中写入下标8
5. 读1个数字出来.     7,min 比较出最小的, min=0
6. 将min的值写入结果文件result_file,并且把current_i_file里的内容8追加到文件delete_i_file中.
7. 继续读数字,同时判定如果下标在delete_i_file中则跳过.
.....重复1....6

最后result_file里就是最后的结果了.

system888net

实际上I/O非常快的时候(比如并行I/O网格系统),的确可以使用有限的内存做很多事情.

net_robber

原帖由 flyingbox 于 2009-8-25 13:11 发表

归并的时候内存会不会不够？

归并的时候，需要的内存很小











两个有序数组，如何归并？？
这里可以使用相同的方法

peimichael

对于外排序，归并的时候你用于存放数据的内存只要能存下两个数字就够了

starwing83

既然是整数，当然基排是最快的啦……

diepics

原帖由 system888net 于 2009-8-25 21:40 发表
实际上I/O非常快的时候(比如并行I/O网格系统),的确可以使用有限的内存做很多事情.

赞

ajianglaoka

看 编程珠玑 第一章 位图技术。

A.com

既然是整数,如无重复,可用简单序列法,去除空位即得最终结果.如有重复,则需要用另一个表记录重复数字以及重复次数.

deadlylight

原帖由 ajianglaoka 于 2009-8-26 09:48 发表
看 编程珠玑 第一章 位图技术。

位图排序是不是要n/8的内存才够
n=4G，内存要512M才够

redor

原帖由 flyingbox 于 2009-8-25 13:11 发表

归并的时候内存会不会不够？

您老没写过归并程序啊？