快速排序的原理与实现
哪些公司问过
答案要点
- 核心思想:选基准 pivot 分区,再对左右两部分递归排序(分治)
- 平均 O(n log n),最坏 O(n²)(如已排序数组且固定选首元素为基准)
- 空间复杂度平均 O(log n)(递归栈);不是稳定排序
- 优化:三数取中或随机选基准、小区间改用插入排序、先递归较短的一侧
- 实践中快的原因:原地分区、缓存友好、常数项小
易错点
- 说快排最坏也是 O(n log n)
- 固定选第一个元素做基准,遇到有序数据就退化
- 忽略大量重复元素的情况:二路划分会退化,应使用三路划分
- 把快排说成稳定排序
面试官常见追问
- 快速排序是稳定的吗?为什么?
- 怎么避免最坏情况?
- 数组基本有序时用什么排序?
- 快排和归并排序怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场