快排分区函数、最坏复杂度与非递归实现
哪些公司问过
答案要点
- 分区:选基准,双指针交替从两端找不满足条件的元素填坑,返回基准最终位置
- 最坏 O(n²),出现在已有序且取端点为基准等极不平衡划分
- 随机基准、三数取中缓解最坏情况,重复元素多时用三路划分
- 非递归:显式栈保存区间边界,循环弹出分区再压入子区间
- 先处理较小区间,栈深度可控制在 O(log n)
易错点
- 指针移动顺序写反,基准选左端却先移动左指针,导致结果错误
- 相遇条件和等号处理不当,出现死循环或越界
- 非递归时压入空区间或单元素区间,产生无效循环
面试官常见追问
- Lomuto 和 Hoare 分区有什么区别?
- 工程中的排序为什么常用内省排序?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场