归并排序与快速排序的区别及如何选择
哪些公司问过
答案要点
- 快排先划分后递归,归并先递归后合并
- 归并稳定、最坏 O(n log n)、需 O(n) 额外空间
- 快排平均 O(n log n)、最坏 O(n²)、原地、不稳定
- 快排常数小、缓存友好,随机或三数取中选基准防退化
- 要稳定、外部排序、链表排序选归并;内存紧张求快选快排
易错点
- 说快排最坏也是 O(n log n),忽略有序输入下的退化
- 说归并排序是原地排序,数组归并需要 O(n) 额外空间
- 把快排的空间复杂度说成 O(1),递归栈平均需 O(log n)
面试官常见追问
- 什么是排序算法的稳定性?
- 标准库的排序用的是什么?
- 大量数据内存放不下怎么排?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场