插入排序（Insertion Sort）
插入排序不是一轮轮找最大值，而是维护左边始终有序，然后把当前元素插到它该在的位置。
定义
插入排序是一种简单直观的排序算法，工作原理类似于整理扑克牌：将每张牌插入到已排好序的牌中的正确位置。
核心思路
- 将数组分为已排序和未排序两部分
- 每次从未排序部分取出一个元素
- 在已排序部分找到合适位置并插入
初始: [5, 2, 4, 6, 1, 3]
已排序 | 未排序
第1轮: [5 | 2, 4, 6, 1, 3] → [2, 5 | 4, 6, 1, 3]
第2轮: [2, 5 | 4, 6, 1, 3] → [2, 4, 5 | 6, 1, 3]
第3轮: [2, 4, 5 | 6, 1, 3] → [2, 4, 5, 6 | 1, 3]
第4轮: [2, 4, 5, 6 | 1, 3] → [1, 2, 4, 5, 6 | 3]
第5轮: [1, 2, 4, 5, 6 | 3] → [1, 2, 3, 4, 5, 6]
🎞️ 插入过程动画
（附件 insertion-sort-shift.svg 未随站点发布）
看动画时重点盯住两件事
- 左边有序区始终保持有序。
- 当前
key不是一路交换，而是先把更大的元素整体右移，再落到空位。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n) | 数组已排序，每次只比较一次 |
| 平均时间 | O(n²) | 平均需要移动n²/4个元素 |
| 最坏时间 | O(n²) | 数组逆序，每次都要移动所有已排序元素 |
| 空间复杂度 | O(1) | 原地排序 |
| 稳定性 | ✅ 稳定 | 相等元素不会交换顺序 |
Go 代码
Go 实现
package main
import "fmt"
func insertionSort(arr []int) {
n := len(arr)
for i := 1; i < n; i++ {
key := arr[i]
j := i - 1
// 将大于key的元素后移
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func main() {
arr := []int{12, 11, 13, 5, 6}
fmt.Println("原始数组:", arr)
insertionSort(arr)
fmt.Println("排序后:", arr)
}为什么插入排序在“几乎有序”时很快
如果数组本来就差不多有序，每个元素只需要移动很短距离，内层循环很快就会停下来，所以实际表现会接近 O(n)。
易错点
插入排序最容易错的地方是“先保存 key，再整体右移”这个顺序。
- 不保存
key就右移，会把当前值覆盖掉。 j退出循环后，插入位置是j + 1。- 稳定性来自“只移动严格大于
key的元素”，不是大于等于。
算法优化
经典题目
基础应用
变体题目
应用题
- 部分有序数组排序
- 在线排序（流式数据）
- 小数据集排序
优缺点
优点
- ✅ 实现简单
- ✅ 稳定排序
- ✅ 原地排序（O(1)空间）
- ✅ 对小数据集很高效
- ✅ 自适应：对几乎有序的数据性能好（接近O(n)）
- ✅ 在线算法：可以边接收数据边排序
缺点
- ❌ 大数据集性能差 O(n²)
- ❌ 需要频繁移动元素
- ❌ 不适合逆序数据
应用场景
- 小数据集：数据量少（通常 < 50）时很高效
- 几乎有序：数据基本有序时性能接近O(n)
- 在线排序：数据陆续到达，需要实时排序
- 稳定性要求：需要保持相等元素的相对顺序
- 混合排序：作为快速排序、归并排序的优化（小数组时使用）
插入排序的实际应用
3. 数据库索引维护
实时插入新记录时使用插入排序维护小范围有序性
🔍 插入排序 vs 其他O(n²)排序
| 特性 | 插入排序 | 选择排序 | 冒泡排序 |
|---|---|---|---|
| 最好情况 | O(n) | O(n²) | O(n) |
| 稳定性 | ✅ | ❌ | ✅ |
| 比较次数 | 可变 | 固定 | 可变 |
| 交换次数 | 少 | 最少 | 多 |
| 几乎有序时 | 最快 | 慢 | 较快 |