快排遇到全相等数组为什么退化及三路划分
哪些公司问过
答案要点
- 随机选key只防有序输入被针对,对全相等元素无效
- Lomuto划分在全等数组上每次一边n-1、一边0,递归深度n,复杂度O(n²)
- 三路划分:lt/i/gt把数组分成小于、等于、大于三段,只递归两端
- 全等数组用三路划分一趟结束,复杂度O(n)
- Hoare式双指针遇等于也停下交换,能把相等元素均分,保持O(n log n)
易错点
- 以为随机选key就能解决所有退化情况
- 双指针扫描遇到等于key不停下,同样会一边倒
- 三路划分中与gt交换后i仍前进,漏检换过来的元素
面试官常见追问
- 三路划分具体怎么移动指针?
- 怎样防止快排递归过深导致栈溢出?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场