1. 定位导航
前面已经知道，算法分析不能只看某一次运行结果，而要看输入规模变大后的增长趋势。
插入排序是理解“输入形态影响运行时间”的好例子。
对于同样长度的数组：
[1, 2, 3, 4, 5] [3, 1, 5, 2, 4] [5, 4, 3, 2, 1]它们的长度都是 5，但插入排序的执行成本不同。
2. 概念术语
| 术语 | 定义 | 在插入排序中的体现 |
|---|---|---|
| 输入形态 | 输入数据的原始排列状态 | 已有序、随机、逆序 |
| 比较次数 | 判断前面元素是否大于当前元素的次数 | arr[i] > key |
| 移动次数 | 把较大元素向后挪动的次数 | arr[i + 1] = arr[i] |
| 最好情况 | 最有利的输入 | 数组已经有序 |
| 最坏情况 | 最不利的输入 | 数组完全逆序 |
| 平均情况 | 一般随机输入下的期望表现 | 部分元素需要移动 |
| 运行时间 | 比较和移动共同造成的成本 | 随输入形态变化 |
关键澄清：
- 插入排序不是对所有输入都一样慢。
- 已有序数组下，插入排序非常快。
- 完全逆序数组下，插入排序会退化到平方级。
- 复杂度分析要区分“输入规模”和“输入形态”。
3. 为什么插入排序的时间不固定
插入排序的核心动作是：
把当前元素插入到前面已经排好序的部分中。如果当前元素本来就比前面元素大，就不用移动。
如果当前元素比前面很多元素都小，就要一路向前比较、移动。
所以插入排序的运行时间取决于：
当前元素需要向前移动多远。如果数组接近有序，大部分元素几乎不用动。
如果数组完全逆序，每个元素都要移动很远。
4. 最好情况：数组已经有序
考虑输入：
[1, 2, 3, 4, 5]插入排序从第二个元素开始处理。
每次只需要和前一个元素比较一次，就知道当前元素已经在正确位置。
例如处理2：
1 <= 2不用移动。
处理3：
2 <= 3不用移动。
所以最好情况下：
- 每轮只做一次比较；
- 基本没有元素移动；
- 总比较次数大约是
n - 1。
因此最好情况是：
O(n) O(n)O(n)
5. 最坏情况：数组完全逆序
考虑输入：
[5, 4, 3, 2, 1]这个输入对插入排序非常不友好。
处理4时，需要把5向后移动。
处理3时，需要把5、4都向后移动。
处理2时，需要把5、4、3都向后移动。
处理1时，需要把所有前面的元素都向后移动。
也就是说，每一轮都要移动大量元素。
如果数组长度是n，最坏情况下移动次数近似为：
1+2+3+⋯+(n−1) 1 + 2 + 3 + \cdots + (n - 1)1+2+3+⋯+(n−1)
这个和等于：
n(n−1)2 \frac{n(n - 1)}{2}2n(n−1)
所以最坏情况是：
O(n2) O(n^2)O(n2)
6. 平均情况：随机输入
随机输入时，每个元素大概不会总是在最前，也不会总是在最后。
可以粗略理解为：
平均每个元素需要向前移动前面已排序部分的一半距离。所以平均情况下，总移动次数仍然接近平方级，只是常数比最坏情况小。
因此插入排序平均情况通常也是：
O(n2) O(n^2)O(n2)
这说明：插入排序在随机大数组上并不是理想选择。
7. 动态推演：运行轨迹对比
下面动态图对比了最好情况和最坏情况。
可以看到：
- 最好情况中，每轮比较很少，移动次数几乎为 0；
- 最坏情况中，每轮都会发生大量移动；
- 同样是 5 个元素，运行成本差距已经很明显；
- 当
n变大时，这种差距会更大。
8. 数值推导：为什么最坏情况是平方级
最坏情况下，第几轮最多移动多少次？
| 处理轮次 | 最多移动次数 |
|---|---|
| 第 2 个元素 | 1 |
| 第 3 个元素 | 2 |
| 第 4 个元素 | 3 |
| … | … |
| 第 n 个元素 | n - 1 |
总移动次数就是：
1+2+3+⋯+(n−1) 1 + 2 + 3 + \cdots + (n - 1)1+2+3+⋯+(n−1)
根据等差数列求和公式：
1+2+3+⋯+(n−1)=n(n−1)2 1 + 2 + 3 + \cdots + (n - 1) = \frac{n(n - 1)}{2}1+2+3+⋯+(n−1)=2n(n−1)
展开后：
n(n−1)2=n2−n2 \frac{n(n - 1)}{2} = \frac{n^2 - n}{2}2n(n−1)=2n2−n
保留最高阶项后，就是平方级：
O(n2) O(n^2)O(n2)
9. 代码实践：统计比较和移动次数
下面用代码统计三种输入下的比较次数和移动次数。
definsertion_sort_count(nums):arr=nums[:]comparisons=0moves=0forjinrange(1,len(arr)):key=arr[j]i=j-1whilei>=0:comparisons+=1ifarr[i]>key:arr[i+1]=arr[i]moves+=1i-=1else:breakarr[i+1]=keyreturnarr,comparisons,moves cases={"最好情况：已有序":[1,2,3,4,5],"平均情况：随机":[3,1,5,2,4],"最坏情况：逆序":[5,4,3,2,1],}forname,numsincases.items():sorted_arr,comparisons,moves=insertion_sort_count(nums)print(f"{name}")print(f"输入:{nums}")print(f"输出:{sorted_arr}")print(f"比较次数:{comparisons}, 移动次数:{moves}")print()可能输出：
最好情况：已有序 输入: [1, 2, 3, 4, 5] 输出: [1, 2, 3, 4, 5] 比较次数: 4, 移动次数: 0 平均情况：随机 输入: [3, 1, 5, 2, 4] 输出: [1, 2, 3, 4, 5] 比较次数: 8, 移动次数: 4 最坏情况：逆序 输入: [5, 4, 3, 2, 1] 输出: [1, 2, 3, 4, 5] 比较次数: 10, 移动次数: 10从结果可以明显看到：
已有序 < 随机 < 逆序这正是最好、平均、最坏情况的差别。
10. 最好、平均、最坏的趋势对比
如果把输入规模继续放大，三种情况的趋势可以画成下面这样：
这里的重点是：
- 最好情况接近线性增长；
- 平均情况接近平方增长；
- 最坏情况也是平方增长；
- 平均情况和最坏情况差别主要体现在常数，而不是增长量级。
所以我们经常说插入排序：
最好情况 O(n) 平均情况 O(n²) 最坏情况 O(n²)11. 常见误区
误区一：插入排序永远是 O(n²)
不准确。
插入排序最坏情况和平均情况通常是O(n²)，但最好情况是O(n)。
误区二：只要数据量小，就不用分析
也不对。小数据量下，复杂度影响较小，但分析仍然能帮助你理解算法行为。
误区三：逆序只是一个特殊例子，不重要
逆序输入代表最坏情况。工程中最坏情况很重要，因为系统不能只在“输入友好”时稳定。
误区四：移动次数和比较次数可以完全忽略
不能。不同实现中，移动成本可能很明显，尤其当元素对象很大时。
12. 现代延伸
插入排序虽然不是大规模通用排序的首选，但它仍然非常有用。
常见使用场景包括：
| 场景 | 原因 |
|---|---|
| 小数组排序 | 实现简单，常数小 |
| 数据接近有序 | 运行时间接近线性 |
| 混合排序中的小片段 | 复杂排序算法会在小区间切换到插入排序 |
| 在线插入场景 | 新元素逐个到达时便于维护局部有序 |
| 教学和算法分析 | 很适合理解循环不变式、输入形态和复杂度 |
很多工业级排序实现并不是单一算法，而是组合策略。
例如大数组用更适合整体排序的算法，小数组或接近有序片段再切换到插入排序，这样可以兼顾理论复杂度和实际性能。
13. 思考题
- 为什么插入排序在数组已经有序时是
O(n)？ - 为什么完全逆序时移动次数是
1 + 2 + ... + (n-1)？ - 平均情况下为什么仍然是平方级？
- 插入排序适合哪些真实工程场景？
- 如果数组元素是很大的对象，移动次数会带来什么额外影响？
14. 本篇小结
本篇围绕插入排序运行时间，重点讲清楚了三种情况：
- 最好情况：数组已有序，比较少，移动少，接近
O(n)； - 最坏情况：数组完全逆序，每轮都大量移动，接近
O(n²)； - 平均情况：随机输入下通常仍然接近
O(n²)； - 输入形态会显著影响插入排序的实际运行时间；
- 插入排序虽然不适合大规模乱序数据，但在小数组和接近有序场景中依然有价值。
算法分析不能只看一个输入样例，而要同时关注：
最好情况、最坏情况、平均情况这才是理解算法性能的完整视角。
