插入排序在某些情况下可以达到 O(N) 的时间复杂度，那么快速排序在哪些情况下可以优化到更快？其最优、平均和最坏时间复杂度分别是多少？
考察说明
考察对排序算法时间复杂度的准确理解，特别是特定输入下的优化边界
回答思路
- 准确说出快排最优、平均、最坏时间复杂度及对应输入场景
- 指出快排在基本有序或数据量小时可通过切换插入排序等策略优化
- 分析快排的常数因子和实际性能，避免仅凭大O结论误导
- 理解时间复杂度描述的是渐进增长率，优化O(NlogN)到更快通常依赖特定数据特征
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。