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

system888net

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

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里就是最后的结果了.

ubuntuer

1.外部排序
  外部排序就是用来解决内存不够用的, 我可以用int A[10] 40字节那排序4G的数据...
2.bit排序
  0->A[0] 1->A[0] ....  31->A[0]
   A[i>>5] |= 1<<(i&0x01F)
   当然bit适合无重复的情况
3.   
   int A[10]
   先排序0 ~10-1以内的数据
   加10 ~ 20-1的数据
   ....
    每次直接用桶排!!!
   
   这题就是每次排200M/4=50M的数

[ 本帖最后由 ubuntuer 于 2009-8-25 21:42 编辑 ]

aaaaa5aa

原帖由 system888net 于 2009-8-25 19:04 发表
200M内存+磁盘或u盘.

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

system888net

200M内存+磁盘或u盘.

aaaaa5aa

原帖由 koolcoy 于 2009-8-25 14:36 发表

难道不能把已经归并好的部分输出到磁盘啊

到后来每个部分都大于200M怎么归并？

peimichael

这个不是典型的外排序么
那个什么扫雪车模型，课上学的，不知道实际用的多不多

cookis

编程珠玑 上第一个例子就是这个，用统计法  不是排序

koolcoy

原帖由 群雄逐鹿 于 2009-8-25 14:38 发表


同意并且经推断, 一定有磁盘

你也可以输出到网络， 然后给它取个非常好听的名字： 云排序

群雄逐鹿

原帖由 koolcoy 于 2009-8-25 14:36 发表

难道不能把已经归并好的部分输出到磁盘啊

同意并且经推断, 一定有磁盘