外部排序

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

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

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

         按照这个方法来回合并，总共经过三次合并之后就可以得到8G的有序子串。

         我们假设需要排序的int数有12个，内存一次只能装下3个int数。

         接下来把12个数据分成4份，然后排序成有序子串：

         然后把子串进行两两合并：

         输出哪个元素就在那个元素所在的有序子串再次读入一个元素：

         继续

         重复直到合并成一个包含6个int有序子串：

         再把两个包含6个int的有序子串合并成一个包含12个int数据的最终有序子串：

优化策略

         因为硬盘的读写速度比内存要慢的多，按照以上这种方法，每个数据都从硬盘读了三次，写了三次，要花很多时间。

         解释下：例如对于数据2，我们把无序的12个数据分成有序的4个子串需要读写各一次，把2份3个有序子串合并成6个有序子串读写各一次；把2份6个有序子串合并从12个有序子串读写各一次，一共需要读写各3次。

         在进行有序子串合并的时候，不采取两两合并的方法，而是可以3个子串，或4个子串一起来合并。

多路归并

 &...

课后习题

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

参考答案：B