插入排序（Insertion Sort）
将元素插入到左侧已排序数组的正确位置，类似打扑克牌时插入新牌，对有序度高的数组效率接近 O(n)。
定义
插入排序是一种简单的排序算法，其核心思想是：维护左侧数组为已排序状态，每次将右侧一个新元素插入到左侧有序数组的正确位置。
类比：打扑克牌时，每抓到一张新牌，将其插入到手中已经排好序的牌中。
核心特性
| 特性 | 说明 |
|---|---|
| 时间复杂度 | O(n²)，有序度高时接近 O(n) |
| 空间复杂度 | O(1)，原地排序 |
| 稳定性 | ✅ 稳定（相同元素相对位置不变） |
| 是否原地 | ✅ 是 |
| 最佳情况 | 已排序数组，O(n) |
| 最坏情况 | 完全逆序，O(n²) |
基本原理
算法过程
- 初始状态：
[0, sortedIndex)为已排序部分，sortedIndex初始为 0（空数组视为有序） - 每次迭代：将
nums[sortedIndex]插入到[0, sortedIndex)的正确位置 - 插入方式：从
sortedIndex向左遍历，通过相邻交换将元素"冒泡"到正确位置 - 终止条件：遇到
nums[i] >= nums[i-1]时 break（已到达正确位置）
void sort(int[] nums) {
int n = nums.length;
int sortedIndex = 0;
while (sortedIndex < n) {
// 将 nums[sortedIndex] 插入到有序数组 [0, sortedIndex) 中
for (int i = sortedIndex; i > 0; i--) {
if (nums[i] < nums[i - 1]) {
// 交换相邻元素，将较小元素向左移动
int tmp = nums[i];
nums[i] = nums[i - 1];
nums[i - 1] = tmp;
} else {
break; // 找到正确位置，提前终止
}
}
sortedIndex++;
}
}
与选择排序的关系
插入排序是对选择排序的优化：
- 选择排序：在右侧未排序部分找最小值，插入左侧
- 插入排序：反过来，在左侧已排序部分找当前元素的插入位置
与类似概念对比
| 维度 | 插入排序 | 选择排序 | 冒泡排序 |
|---|---|---|---|
| 时间复杂度 | O(n²) | O(n²) | O(n²) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 | ✅ 稳定 |
| 提前终止 | ✅ 支持（利用有序性） | ❌ 不支持 | ✅ 支持 |
| 有序度利用 | ✅ 高效（< n²/2 次操作） | ❌ 不利用 | ⚠️ 利用但效率低（≈ n²/2） |
| 遍历方向 | 向左遍历有序部分 | 向右遍历无序部分 | 向右遍历无序部分 |
时间复杂度/性能
| 场景 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况（已排序） | O(n) | 内层循环每次只比较 1 次就 break |
| 最坏情况（逆序） | O(n²) | 每次都要交换左侧所有元素 |
| 平均情况 | O(n²) | 操作次数 ≈ n²/4 ~ n²/2 |
| 部分有序 | O(n·k) | k 是逆序对数量，k 越小越快 |
注意事项
- 提前终止是关键：
if (nums[i] < nums[i-1])才交换，否则 break，这是利用有序性的核心 - 稳定性保证：只有
<才交换，如果是<=就会破坏稳定性 - 操作次数少于冒泡：冒泡每次都要遍历整个右侧部分，插入排序只需遍历部分左侧有序部分
应用场景
- 小数组排序（n ≤ 50 时实际效率很高）
- 近乎有序的数组排序
- 在线排序场景（数据逐步到达）
- 作为高级排序算法的子过程（如 TimSort 对小子数组使用插入排序）
经典算法
- 选择排序：插入排序的优化起点，但不稳定且不利用有序性
- 冒泡排序：同为稳定排序，但插入排序综合性能更高
- 希尔排序：插入排序的改进版，通过分组插入达到 O(n^1.3) 复杂度
- TimSort：Python 内置排序算法，结合插入排序和归并排序