外部排序
标签: 数据结构
学习人数: 6585

外部排序

         给你一个包含20亿个int类型整数的文件,计算机的内存只有2GB,怎么给它们排序?一个int数占4个字节,20个亿需要80亿字节,大概占用8GB的内存,而计算机只有2GB的内存,数据都装不下!可以把8GB分割成4个2GB的数据来排,然后在把他们拼凑回去。如下图:

         排序的时候可以选择快速排序或归并排序等算法。为了方便,我们把排序好的2G有序数据称为有序子串。接着把两个小的有序子串合并成一个大的有序子串。

         注意:读取的时候是每次读取一个int数,通过比较之后再输出。

         按照这个方法来回合并,总共经过三次合并之后就...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】设外存上有120个初始归并段,进行12路归并时,为实现最佳归并,需要补充的虚段个数是
A.1   B. 2   C. 3   D. 4

参考答案:B


登录后发布评论

暂无评论,来抢沙发