21-算法与数据结构
第 282 题:大文件的external sort实现?k-way merge?
题目
大文件的external sort实现?k-way merge?
完整讲解
一、外部排序目的
数据量超过内存,无法一次性排序,需分块读入、排序、再合并。核心:利用磁盘顺序 IO,多路归并降低轮数。
二、流程与 k-way merge
阶段一:按内存能容纳的大小(如 M 条记录)读入、内排(快排等)、写出为有序段(run),得到多个有序文件。阶段二:k-way merge:同时打开 k 个有序段,用最小堆维护当前 k 个候选最小元;每次取堆顶输出,并从对应段补入下一条,直到所有段读完。k 越大,归并轮数越少,但需要 k 路缓冲与堆大小。
三、实现要点
内排阶段可并行(多块同时排序)。k-way 时堆中元素需带「来自哪一段」信息;段读完则从堆中移除该路。磁盘 IO 顺序读顺序写,性能好。可扩展为多轮 k-way(若段数远大于 k)。
面试要点
- 外部排序:分块读入、内排、写出有序段;再 k 路归并。
- k-way merge:用最小堆维护 k 个当前最小值;取堆顶输出并从对应段补入。
- 内排可并行;k 大可减少轮数但占缓冲;顺序 IO 友好。
- 堆中需记录元素来自哪一段,段读完则撤掉该路。
记忆要点
- 两阶段:内排成多段 → k-way 归并。
- k-way:最小堆 + 每路一个当前值;取堆顶、补该路下一条。
- k 大则轮数少;顺序 IO;可多轮 k-way。