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 次就可以了。如图：