现在的位置: 首页 > 综合 > 正文

怎样 对40亿个8位正整数进行排序

2014年01月20日 ⁄ 综合 ⁄ 共 487字 ⁄ 字号 评论关闭

这里可以借鉴快速排序的思想,将整个数据量进行分解,取8位正整数的中间值128,凡是大于这个数的值都放入文件b,小于128的都放入文件a。

然后再按照这种方法一直分解直到任意一边的数量小于1千万为止,然后使用快速排序对这1千万进行排序,最后将结果存入文件中,然后便不再对该数据集进行处理。

由于内存牵涉到运算的效率和性能,所以,每分解一次,都要将分解的结果放入文件中。


最后就是对这些所有的文件中的结果进行合并,这里可以考虑用一个链表存放所有文件结果集的次序(也是所有排序结果的次序)

所以,总结一下:

1. 使用文件代替以前的数组,对数据按照快速排序的思想进行分解

2. 当某一结果集分解到足够小,比如小于1千万时,此时对该数据运用快速排序,然后将排序结果放入文件中,并且不在对该数据集进行处理

3. 合并所有结果,按照递归的思想,可以使用一个链表记录那些文件存放了结果集,并且是有序的存放的。
你可以定义一个struct结构体,


其他解决方案:

你也可以采用分布式的方法进行运算,但是仍然得对所有数据采用快排的思想的分解。

将原任务不仅要分解成较小的规模,还应该考虑到所有的结果方便组装成为最总的结果 

抱歉!评论已关闭.