外排序:10 亿个整数如何排序
哪些公司问过
答案要点
- 数据量大于内存,需要外排序:分块排序 + 多路归并
- 第一步:分块读入内存做内部排序,写回磁盘得到多个有序归并段
- 第二步:K 路归并,用最小堆维护各段当前最小元素,输出缓冲写盘
- 路数太多可分多轮归并;用大的缓冲区减少 IO 次数
- 优化:置换选择排序生成更长的归并段,败者树减少比较次数;值域有限时用桶排序
易错点
- 尝试一次性把全部数据读入内存
- 归并时每次只读一个元素,造成大量 IO
- 忽略磁盘读写是主要瓶颈
- 路数过多,缓冲区太小,反而变慢
面试官常见追问
- 1 亿个 int 大概占多少内存?
- 为什么用最小堆做多路归并?
- 什么是置换选择排序?
- 如果值域很小怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场