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

reiase

想办法用统计方法加速...

koolcoy

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

归并的时候内存铁定不够

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

群雄逐鹿

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

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

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

koolcoy

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


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

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

cookis

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

peimichael

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

aaaaa5aa

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

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

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

system888net

200M内存+磁盘或u盘.

aaaaa5aa

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

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

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 编辑 ]