快速排序的最坏情况与优化方法
哪些公司问过
答案要点
- 最坏情况是划分极不平衡,时间退化为 O(n²),常见于有序或逆序数组配固定基准
- 大量重复元素也可能导致划分不平衡
- 随机基准或三数取中避免有序输入退化
- 三路划分处理大量重复元素,小区间改用插入排序
- 内省排序在递归过深时切换堆排序,保证最坏 O(n log n)
易错点
- 只说有序数组最坏,忽略重复元素的情况
- 以为随机化后最坏复杂度就变成 O(n log n),实际只是概率极低
- 说 std::sort 是纯快排,实际是内省排序
面试官常见追问
- 三路快排是怎么做的?
- 数组 TopK 怎么做,复杂度多少?
- 快排为什么通常比堆排序快?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场