外部排序

定义与基本思想

外部排序（External Sorting）是指数据量太大，无法全部装入内存时，借助外部存储（如磁盘）进行的排序。其基本思想是：将大文件分成若干能放入内存的小块，分别排序后再多路归并。

外部排序演示

块1：

84

块2：

57

块3：

13

块4：

62

当前阶段：分块排序

下一步

常见算法

多路归并排序

• 将大文件分成若干小块，分别读入内存排序（如归并排序）
• 将已排序的小块（称为“归并段”）多路归并成大文件
• 可采用二路、四路或多路归并，减少归并次数

多路归并的实现

外部排序的归并阶段需要从多个归并段中不断选出最小元素。若采用 k 路归并，用败者树可以在 $O(\log_2 k)$ 时间内选出最小元素，减少比较次数。

• 败者树：锦标赛思想，记录每轮比较的“败者”，根结点为“冠军”（最小元素）。k 路归并每趟选最小只需 $O(\log_2 k)$ 次比较
• 置换-选择排序：生成尽可能长的初始归并段。内存中维护一个最小堆，每当输出一个最小元素，就从输入文件读入一个新元素替补，从而生成比内存容量更长的归并段，减少归并趟数
• 最佳归并树：当各归并段长度不等时，用类似哈夫曼树的方法构造最佳归并树，使带权路径（I/O 次数）最小，虚段（空归并段）补零

归并趟数的推导

设初始归并段数为 r，采用 k 路归并，则归并趟数 $S = \lceil \log_k r \rceil$。每趟归并都要读写一遍全部数据，因此减少归并趟数（增大 k 或减少 r）能显著减少磁盘 I/O。

应用场景

• 大型数据库、搜索引擎日志、海量数据分析等
• 任何单机内存无法容纳全部数据的排序任务

时间复杂度分析

• 排序阶段：$O(n\log n)$（每块内排序）
• 归并阶段：$O(n\log_k n)$，$k$为归并路数
• 总体复杂度：$O(n\log n)$
• 空间复杂度：主要受磁盘 I/O 和缓冲区大小影响

习题

习题 1

简述外部排序的基本流程及适用场景。

习题 2

外部排序常用的归并方式有哪些？其复杂度如何？

上一章节排序掌握各种排序算法的原理、实现、性能分析及其应用。

下一章节排序的起源与实际意义介绍排序问题的历史、现实应用和产生动因。