归并排序的实现与特点
哪些公司问过
答案要点
- 分治:从中间拆成两半,递归排序,再合并两个有序子数组
- 合并:双指针比较,较小的放入临时数组,最后接上剩余部分并拷回
- 相等时先取左边的元素,保证稳定性
- 时间 O(n log n)(最好最坏都是),额外空间 O(n)
- 可自底向上迭代实现;适合链表排序、外部排序,可统计逆序对
易错点
- 合并时比较用严格小于,破坏稳定性
- 每次递归都新分配临时数组,开销大
- 忘了把临时数组拷回原数组
- 分不清归并的额外空间是 O(n) 还是 O(1)
面试官常见追问
- 归并排序和快速排序怎么比较?
- 怎么用归并排序统计逆序对?
- 为什么链表适合用归并排序?
- 迭代版本怎么写?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场