外部排序

定义与基本思想

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

外部排序演示

块1：

84

块2：

57

块3：

13

块4：

62

当前阶段：分块排序

下一步

常见算法

多路归并排序

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

应用场景

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

时间复杂度分析

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

练习题

练习 1

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

参考答案

解题思路：分块排序+多路归并，适合大数据。

详细步骤：

1. 分块排序，生成归并段
2. 多路归并成大文件
3. 适用于内存无法容纳全部数据的场景

答案：分块+归并，适合大数据排序。

练习 2

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

参考答案

解题思路：二路、多路归并，复杂度分析。

详细步骤：

1. 二路、四路、多路归并
2. 复杂度 $O(n\log_k n)$，$k$为路数

答案：常用多路归并，复杂度 $O(n\log_k n)$。