外部排序（External Sorting） 题目描述 假设你有一个包含 10 亿个整数的超大文件（大小远超内存容量），内存一次只能容纳 100 万个整数。请设计一个算法，将这个文件中的整数按升序排序，并将结果保存到新文件中。 解题过程 1. 问题分析 数据量太大，无法全部加载到内存中进行排序（即无法直接用内部排序算法如快速排序解决）。 需要利用磁盘分批处理数据，再合并结果，这类方法称为 外部排序 。 2. 核心思路：分治 + 归并 外部排序通常分为两个阶段： 分割与内部排序 ：将大文件分割成多个能装入内存的小块，每块单独排序后保存为临时文件。 多路归并 ：将所有有序的临时文件合并成最终的有序大文件。 3. 具体步骤 步骤 1：分割与内部排序 每次从大文件中读取最多 100 万个整数（内存容量上限）到内存。 使用高效的内部排序算法（如快速排序）对这批数据排序。 将排序后的数据写入一个临时文件（例如 temp_1.txt ）。 重复上述过程，直到处理完整个大文件，得到多个有序的临时文件（假设为 temp_1.txt , temp_2.txt , ..., temp_N.txt ）。 示例 ： 10 亿整数 ÷ 100 万/块 = 1000 个临时文件。 步骤 2：多路归并 同时打开所有临时文件（每个文件有一个读指针）。 由于内存限制，不能一次性加载所有文件的数据，但可以每次从每个文件读取一小部分（如 1000 个数）到内存的 缓冲区 。 使用一个 最小堆（优先队列） 来高效选择当前最小的元素： 初始化时，从每个临时文件读取第一个元素（及其来源文件标识）加入最小堆。 每次从堆顶取出最小元素，写入最终结果文件。 从该元素对应的临时文件中读取下一个元素加入堆（若文件未读完）。 重复直到堆为空，所有文件处理完毕。 关键优化 ： 缓冲区管理：为每个临时文件分配一个输入缓冲区，当缓冲区为空时，从磁盘批量读取下一批数据。 堆的大小等于临时文件的数量（本例中最多 1000 个），内存占用可控。 4. 复杂度分析 时间主要消耗在磁盘 I/O 和内部排序： 内部排序阶段：每个块排序时间为 \(O(M \log M)\)（M 为块大小），总时间 \(O(N \log M)\)（N 为总数据量）。 归并阶段：每层归并需扫描所有数据，磁盘 I/O 量约为 \(O(N \log K)\)（K 为归并路数）。 空间复杂度：由内存限制决定（块大小 + 缓冲区）。 5. 扩展优化 若临时文件数量太多（如 K 很大），可先进行多轮归并（例如先 100 路归并生成更大的有序文件，再最终归并）。 使用 SSD 或优化磁盘顺序读写可提升 I/O 效率。 通过以上步骤，即可在有限内存下对超大规模数据完成排序。