数组插入排序的实现与特性
哪些公司问过
答案要点
- 从第二个元素开始,将当前元素插入前面已排序序列的正确位置
- 从后向前比较,比当前元素大的依次后移,找到位置后放入
- 最好 O(n)(已有序),平均和最坏 O(n²),空间 O(1)
- 稳定排序:遇到相等元素即停止,不改变相对顺序
- 适合小规模或基本有序数据,常作为 TimSort、快排的小区间优化
易错点
- 比较条件写成大于等于,导致相等元素交换,失去稳定性
- 内层循环忘记判断下标不小于 0,导致越界
- 用交换代替后移,常数开销更大
面试官常见追问
- 二分插入排序能把复杂度降到 O(n log n) 吗?
- 希尔排序和插入排序是什么关系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场