手写快速排序及其复杂度
哪些公司问过
答案要点
- 分治:选基准分区,左边不大于、右边不小于基准,再递归
- 分区常用双指针交换,最后把基准放到分界位置
- 平均时间 O(n log n),最坏 O(n²),出现在有序数组且固定取端点为基准
- 随机基准或三数取中可避免最坏情况
- 原地、不稳定,递归栈平均 O(log n);快速选择求第 k 大平均 O(n)
易错点
- 分区边界写错导致死循环
- 只会说平均复杂度,不提最坏情况和原因
- 基准固定取端点,遇到有序数据退化
面试官常见追问
- 快速排序为什么不稳定?
- 数据里有大量重复元素怎么办?
- 快速排序和归并排序怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场