用迭代器实现模板版快速排序
哪些公司问过
答案要点
- 模板参数为迭代器类型和比较器,区间左闭右开,默认 std::less
- 用 std::distance、std::next 取基准,std::partition 完成划分
- 基准归位后递归两侧,长度小于 2 时返回
- 和容器解耦,只依赖迭代器类别
- 优化:三数取中、小区间插入排序、三路划分、先处理小侧、内省排序
易错点
- 区间边界混用左闭右开和闭区间,导致越界或死循环
- 固定选首元素为基准,有序输入退化为 O(n^2)
- 大量重复元素时两路划分效率很差
面试官常见追问
- 你觉得这个快排有什么可以优化的地方?
- 怎么改成非递归?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场