数组基本有序时,用什么排序方法效率最高?
哪些公司问过
答案要点
- 插入排序时间为 O(n+逆序对数),基本有序时接近 O(n),稳定且常数小
- 冒泡加提前终止标志最好 O(n),但常数和最坏行为不如插入排序
- TimSort 利用已有有序段,近乎有序数据接近线性
- 固定选首尾基准的快排在有序输入上退化为 O(n²),可用随机或三数取中
- 每个元素偏离不超过 k 时,用 k+1 大小的堆可做到 O(n log k)
易错点
- 回答快排最快,忽略基本有序时的退化
- 说冒泡和插入排序完全一样
- 只说插入排序 O(n),不说明前提是逆序对少
面试官常见追问
- 为什么快排在有序数组上会退化?
- 希尔排序适合基本有序的数据吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场