外部排序
外部排序（External Sorting）是指数据量太大，无法全部装入内存时，借助外部存储（如磁盘）进行的排序。其基本思想是：将大文件分成若干能放入内存的小块，分别排序后再多路归并。
点击“执行一步”观察算法状态变化。
多路归并排序
- 将大文件分成若干小块，分别读入内存排序（如归并排序）
- 将已排序的小块（称为“归并段”）多路归并成大文件
- 可采用二路、四路或多路归并，减少归并次数
多路归并的实现
外部排序的归并阶段需要从多个归并段中不断选出最小元素。若采用 k 路归并，用败者树可以在 时间内选出最小元素，减少比较次数。
- 败者树：锦标赛思想，记录每轮比较的“败者”，根结点为“冠军”（最小元素）。k 路归并每趟选最小只需 次比较
- 置换-选择排序：生成尽可能长的初始归并段。内存中维护一个最小堆，每当输出一个最小元素，就从输入文件读入一个新元素替补，从而生成比内存容量更长的归并段，减少归并趟数
- 最佳归并树：当各归并段长度不等时，用类似哈夫曼树的方法构造最佳归并树，使带权路径（I/O 次数）最小，虚段（空归并段）补零
归并趟数的推导
设初始归并段数为 r，采用 k 路归并，则归并趟数 。每趟归并都要读写一遍全部数据，因此减少归并趟数（增大 k 或减少 r）能显著减少磁盘 I/O。
- 大型数据库、搜索引擎日志、海量数据分析等
- 任何单机内存无法容纳全部数据的排序任务
- 排序阶段：（每块内排序）
- 归并阶段：，为归并路数
- 总体复杂度：
- 空间复杂度：主要受磁盘 I/O 和缓冲区大小影响
习题 1
简述外部排序的基本流程及适用场景。
解题思路：
本题考查外部排序的基本流程与适用场景。外部排序处理的是数据总量超出内存容量、必须存放在磁盘外存上的情形，因此标准做法是“内排序 + 外归并”两个阶段。
详细步骤：
- 分块排序，生成归并段：把大文件分成若干块，每块读入内存用内排序（如快速排序）排好序后写回磁盘，形成初始归并段。
- 多路归并成大文件：同时打开多个归并段，每次从各段读一条记录进行比较归并，直到所有段合并完毕，输出有序文件。
- 适用于内存无法容纳全部数据的场景：内排序阶段决定每块的大小，外归并阶段决定同时可归并的路数，整体开销由“块内排序 + 多路归并”两阶段构成。
最终答案：
分块+归并，适合大数据排序。
习题 2
外部排序常用的归并方式有哪些？其复杂度如何？
解题思路：
本题考查外部排序中归并方式的选择与复杂度分析。归并路数越多，单趟合并处理的归并段越多、总趟数越少，但所需的缓冲区也越多，因此总时间可写成 。
详细步骤：
- 二路归并：每次合并两个归并段，实现最简单，但归并趟数最多，所需缓冲空间最少。
- 四路、多路归并：一次合并 个归并段，归并趟数降为 ，代价是需要 路缓冲区。
- 复杂度分析：总时间复杂度为 ，其中 为归并路数；实际系统通常取与外存块数相当的 来折中速度与缓冲开销。
最终答案：
常用多路归并，复杂度 。