海量数据排序:内存有限时的外部排序
哪些公司问过
答案要点
- 内存有限需要外部排序,不能全部载入内存
- 分块读入内存排序,写成有序的临时文件
- K 路归并:每个文件一个缓冲,最小堆每次取最小值输出
- 堆实现的归并每次比较 O(log K)
- 另一种思路:按值范围分桶,各桶排序后拼接,要求分布较均匀
易错点
- 想把全部数据读进内存再排序
- 归并时不用堆,每次线性扫描所有块
- 分桶时数据分布不均导致某桶放不进内存
- 忽略磁盘顺序读写的重要性
面试官常见追问
- 归并时内存怎么分配?
- 如果块数很多,K 路归并放不下怎么办?
- 分桶排序要注意什么?
- 怎么减少磁盘 IO 的开销?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。