插入排序

#插入排序

• 什么是插入排序
• 操作步骤
• 时间复杂度
• 特点

#什么是插入排序

插入排序就像整理手中的扑克牌：左手的牌已经排好序，每次从右手拿出一张牌，插入到左手正确的位置。

左侧是已排序区域，右侧是未排序区域，每次从右侧取出一个数据，插入到左侧合适的位置。

#操作步骤

以 5 3 4 7 2 8 6 9 1 为例（| 左边是已排序区域）：

初始:  [5 | 3  4  7  2  8  6  9  1]   假设 5 已排序

第1轮: 取出 3，与左边比较
  5 > 3 → 交换
  [3  5 | 4  7  2  8  6  9  1]   ← 3 插入到正确位置

第2轮: 取出 4，与左边比较
  5 > 4 → 交换
  3 < 4 → 停止
  [3  4  5 | 7  2  8  6  9  1]   ← 4 插入

第3轮: 取出 7
  5 < 7 → 不需要移动
  [3  4  5  7 | 2  8  6  9  1]   ← 7 本来就在正确位置

第4轮: 取出 2
  7 > 2 → 交换；5 > 2 → 交换；4 > 2 → 交换；3 > 2 → 交换
  [2  3  4  5  7 | 8  6  9  1]   ← 2 一路插到最前面

  ...（继续直到所有数据归位）

排序完成: 1  2  3  4  5  6  7  8  9

#时间复杂度

第 k 轮最多需要比较 k-1 次，总共 1+2+…+(n-1) ≈ n²/2 次。

#特点

• 对近乎有序的数据非常高效：如果数据基本有序，接近 O(n)
• 稳定排序：相等元素的相对顺序不变
• 原地排序：不需要额外空间
• 在线排序：可以边接收数据边排序
• 适合小数据量或近乎有序的数据

#小结

• 插入排序把每个元素插入到已排序区域的正确位置
• 最坏 O(n²)，但对近乎有序的数据接近 O(n)
• 稳定排序，适合小数据量或数据基本有序的场景