一、从整理扑克牌说起¶
想象一下，你刚拿到一副打乱的扑克牌，比如：5, 3, 8, 4, 2。现在你想把它们从小到大排好序，应该怎么做？
最直观的方法可能是这样的：先挑出一张牌（比如第一张5）作为“已排好序的牌堆”，然后依次拿起剩下的牌，每张牌都插入到已排好序的牌堆中合适的位置。
- 第一步：先理出第一张牌5，已排序牌堆：
[5] - 第二步：拿起第二张牌3，发现3比5小，所以插入到5前面，已排序牌堆变成：
[3, 5] - 第三步：拿起第三张牌8，8比5大，直接放到已排序牌堆末尾，变成：
[3, 5, 8] - 第四步：拿起第四张牌4，需要和已排序牌堆的最后一张牌8比较，4 < 8，所以继续往前比较5，4 < 5，再比较3，4 > 3，所以插入到3和5之间，已排序牌堆变成：
[3, 4, 5, 8] - 第五步：拿起第五张牌2，依次和8、5、4、3比较，2比所有牌都小，所以插入到最前面，最终排好序的牌堆：
[2, 3, 4, 5, 8]
这个过程是不是很熟悉？其实，这就是插入排序的核心思想——把待排序的元素逐个插入到已排序的序列中。
二、插入排序的原理¶
插入排序的逻辑可以用“逐步构建有序序列”来理解：
- 默认有序：假设第一个元素已经是“有序序列”的一部分（只有一个元素，自然有序）。
- 逐个插入：从第二个元素开始，把每个元素当作“新牌”，插入到前面已经排好序的序列中的正确位置。
- 移动元素，腾出位置：如果新牌比已排序序列中的某些牌小，需要把那些较大的牌“后移”一位，给新牌腾出位置。
三、实例演示：以数组[5, 3, 8, 4, 2]为例¶
我们用上面的扑克牌例子，把每个步骤用数组操作来模拟：
| 步骤 | 已排序序列 | 待插入元素 | 比较过程 | 插入后序列 |
|---|---|---|---|---|
| 1 | [5] |
3（第二个元素） | 3 < 5 → 后移5 | [3, 5] |
| 2 | [3, 5] |
8（第三个元素） | 8 > 5 → 直接插入末尾 | [3, 5, 8] |
| 3 | [3, 5, 8] |
4（第四个元素） | 4 < 8 → 后移8；4 < 5 → 后移5；4 > 3 → 插入中间 | [3, 4, 5, 8] |
| 4 | [3, 4, 5, 8] |
2（第五个元素） | 2 < 8 → 后移8；2 < 5 → 后移5；2 < 4 → 后移4；2 < 3 → 后移3 | [2, 3, 4, 5, 8] |
关键观察：每次插入时，待插入元素会与已排序序列中的元素从后往前比较，直到找到合适的位置。
四、算法步骤与伪代码¶
算法步骤：¶
- 遍历数组，从第二个元素（索引1）开始处理（记为
i）。 - 把当前元素
arr[i]暂存为key（待插入元素）。 - 从已排序序列的末尾开始（即
i-1），用j指向已排序元素：
- 如果arr[j] > key，则把arr[j]后移一位（arr[j+1] = arr[j]）。
- 如果arr[j] <= key，则停止移动，此时j+1就是key的插入位置。 - 将
key插入到arr[j+1]的位置。 - 继续处理下一个元素（
i += 1），直到所有元素处理完毕。
伪代码：¶
插入排序(arr)
对于 i 从 1 到 数组长度 - 1:
key = arr[i] // 取出待插入元素
j = i - 1 // 已排序序列的末尾索引
// 移动已排序元素，腾出位置
while j >= 0 且 arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key // 插入待插入元素
返回 arr
五、Python代码实现¶
def insertion_sort(arr):
# 从第二个元素开始遍历（索引1）
for i in range(1, len(arr)):
key = arr[i] # 待插入元素
j = i - 1 # 已排序序列的末尾索引
# 移动已排序元素，直到找到插入位置
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j] # 已排序元素后移
j -= 1 # 继续向前比较
arr[j + 1] = key # 插入待插入元素
return arr
# 测试代码
test_arr = [5, 3, 8, 4, 2]
sorted_arr = insertion_sort(test_arr)
print("排序前：", test_arr)
print("排序后：", sorted_arr)
六、插入排序的特点¶
优点：¶
- 简单直观：逻辑清晰，容易理解和实现。
- 原地排序：只需要一个临时变量（
key），空间复杂度为 O(1)。 - 适应性强：适合“几乎有序”的数据（比如已排好序的数组，时间复杂度接近 O(n)）。
- 稳定排序：相等元素的相对顺序不会改变（如扑克牌中相同点数的牌，原顺序保持不变）。
缺点：¶
- 时间复杂度高：最坏情况下（完全逆序）为 O(n²)，不适合大规模数据。
- 移动操作多：对于每个待插入元素，可能需要多次移动已排序元素。
七、总结¶
插入排序的核心思想就像我们整理扑克牌：先把小范围的牌排好序，再逐步扩展到整个序列。它的实现逻辑简单，适合初学者理解排序算法的基本思路，也常用于实际开发中对小规模数据或几乎有序数据的排序。
如果你觉得插入排序的逻辑还不够清晰，可以试着用不同的数组（比如 [9, 7, 6, 15, 16, 5]）手动模拟排序过程，加深对“移动已排序元素”和“找到插入位置”的理解。排序算法的基础就是从这些简单的生活类比开始的~