External Sort
External Sort
外排序算法
External Sort 外部排序
- 外排序算法的基本步骤
- 相关面试题
外排序是指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。
存储在外存上的数据以文件为基本单位，由文件系统进行读写操作，读写操作的基本单位为物理块
生成若干初始归并段（顺串）：这一过程也称为文件预处理。一种常规的方法如下：
把含有n个记录的文件，按内存大小w分成若干长度为w的子文件（归并段）；
分别将各子文件（归并段）调入内存，采用有效的内排序方法排序后送回外存。
产生m=[n/w]个初始归并段。
此时产生的若干子文件称为顺串
给你一个包含20亿个int类型整数的文件，计算机的内存只有2GB，怎么给它们排序？一个int数占4个字节，20个亿需要80亿字节，大概占用8GB的内存，而计算机只有2GB的内存，数据都装不下！可以把8GB分割成4个2GB的数据来排，然后在把他们拼凑回去。如下图：
排序的时候可以选择快速排序或归并排序等算法。为了方便，我们把排序好的2G有序数据称为有序子串。接着把两个小的有序子串合并成一个大的有序子串。
注意：读取的时候是每次读取一个it数，通过比较之后再输出。
按照这个方法来回合并，总共经过三次合并之后就可以得到8G的有序子串。
我们假设需要排序的int数有12个，内存一次只能装下3个int数。
接下来把12个数据分成4份，然后排序成有序子串：
优化策略
因为硬盘的读写速度比内存要慢的多，按照以上这种方法，每个数据都从硬盘读了三次，写了三次，要花很多时间。
解释下：例如对于数据2，我们把无序的12个数据分成有序的4个子串需要读写各一次，把2份3个有序子串合并成6个有序子串读写各一次；把2份6个有序子串合并从12个有序子串读写各一次，一共需要读写各3次。
在进行有序子串合并的时候，不采取两两合并的方法，而是可以3个子串，或4个子串一起来合并。
多路归并
为了方便讲解，我们假设内存一共可以装4个int型数据。
刚才我们是采取两两合并的方式，现在我们可以采取4个有序子串一起合并的方式，这样的话，每个数据从硬盘读写的次数各需要2次就可以了。如图：