插入排序：像整理扑克牌一样给数据排队

你有没有整理过扑克牌？手里抓着一把乱序的牌，你会一张一张地抽出来，找到它应该在的位置插进去。插入排序就是这样一种算法——它每次从待排序的数据中取出一个元素，插入到已经排好序的部分中，直到所有元素都排好。它适合处理数据量不大、或者数据本身已经接近有序的情况，比如考试后老师手动排几张成绩单。

生活中的插入排序

除了扑克牌，你还可以想象这些场景：

整理书架：你有一排已经按字母排好的书，新来一本书，你从最右边开始比较，遇到比它大的就往后挪，直到找到它该放的位置。
排队做操：体育委员让同学们按身高排好。新来的同学从队伍末尾开始，跟前面的人一个个比身高，他比前面的人矮就让前面的人往后站，直到找到自己的位置。
整理零花钱账单：你记录每周零花钱的花费，比如 [15, 8, 20, 12]。第一次记下15元，第二次得到8元，你把8插到15前面；第三次20比15大，直接放在最后；第四次12，从后往前比，20>12→20后移，15>12→15后移，最后放在8后面。最终有序：[8, 12, 15, 20]。

这些过程都体现了插入排序的核心：每次把新元素插入到已排序序列的正确位置。

算法步骤详解

假设我们有一个数组 [5, 2, 4, 6, 1]，从小到大排序。

第一轮：把第一个元素 5 看作已经排好序的“手牌”。手里只有一张牌 [5]。
第二轮：拿起第二个元素 2（新牌）。从手牌的最后一张 5 开始往前比较：
- 5 > 2，所以把 5 往后挪一位（腾出位置）。
- 此时手牌位置为 [ _, 5]，比较到头了，把 2 插入到空位。手牌变成 [2, 5]。
第三轮：拿起第三个元素 4。从手牌最后 5 往前比较：
- 5 > 4，把 5 后移 → [2, _, 5]。
- 再比较 2，2 < 4，停！把 4 插入到 2 后面 → [2, 4, 5]。
第四轮：拿起 6。从 5 开始比，5 < 6，不用移动，直接放到最后 → [2, 4, 5, 6]。
第五轮：拿起 1。从 6 往前比：
- 6 > 1 → 后移，变成 [2, 4, 5, _, 6]
- 5 > 1 → 后移，变成 [2, 4, _, 5, 6]
- 4 > 1 → 后移，变成 [2, _, 4, 5, 6]
- 2 > 1 → 后移，变成 [ _, 2, 4, 5, 6]
- 没有更前面的元素了，把 1 插入到首位 → [1, 2, 4, 5, 6]。

关键点：每一轮我们只关心“新牌”和它前面的元素，前面的元素如果比它大就依次后移，直到找到合适的空位。

Python代码实现（带详细注释）

下面代码用 arr 表示数组，i 表示当前要插入的位置（从1开始），key 是当前要插入的元素，j 是用于比较的前一个位置。

def insertion_sort(arr):
    # 从第二个元素开始（下标为1）
    for i in range(1, len(arr)):
        key = arr[i]          # key 是当前要插入的“新牌”
        j = i - 1             # j 指向左边已经排好序的部分的最后一个位置

        # 循环条件：j 不越界 且 左边的元素比 key 大
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 把大元素往右挪一格
            j -= 1               # 继续向左移动比较

        # 循环结束时，j+1 就是 key 该放的位置
        arr[j + 1] = key

    return arr

新手常见错误

忘记移动多个元素
有的同学只把相邻的一个元素后移就停了，导致丢失数据。必须用循环把所有比 key 大的元素都后移。
索引越界
while j >= 0 这个条件很容易漏掉。如果没有 j >= 0，当比较到数组最前面时，arr[j] 会访问负数下标导致报错。
循环顺序写反
比如写成 while j >= 0 and key > arr[j]，这样会把小的元素往右移，结果变成从大到小排序。
忘记给 key 赋值
直接把 arr[i] 当作 key 来用，但在移动过程中 arr[i] 会被覆盖，所以必须先保存到 key 变量里。
用 j+1 判断时搞错位置
插入时写 arr[j] = key 还是 arr[j+1] = key？因为后移后 j 减了1，正确位置是 j+1。牢记：最后空出来的位置在 j+1 处。

完整可运行的代码示例

def insertion_sort(arr):
    """
    插入排序函数
    参数 arr: 待排序的列表（会直接修改原列表）
    返回：排好序的列表
    """
    # 从第二个元素开始（下标1）
    for i in range(1, len(arr)):
        key = arr[i]          # 当前要插入的牌
        j = i - 1             # 左边已排序部分的最后一个位置

        # 把比 key 大的元素往后移
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # 把 key 插到正确位置
        arr[j + 1] = key

    return arr


# 测试不同的数据
print("=== 测试1：日常零花钱 ===")
money = [15, 8, 20, 12, 5]
print("排序前:", money)
insertion_sort(money)
print("排序后:", money)

print("\n=== 测试2：考试座位号 ===")
seats = [33, 7, 21, 9, 45, 12]
print("排序前:", seats)
insertion_sort(seats)
print("排序后:", seats)

print("\n=== 测试3：已有部分有序 ===")
almost_sorted = [2, 3, 5, 1, 4]   # 前三个已有序
print("排序前:", almost_sorted)
insertion_sort(almost_sorted)
print("排序后:", almost_sorted)

运行结果：

=== 测试1：日常零花钱 ===
排序前: [15, 8, 20, 12, 5]
排序后: [5, 8, 12, 15, 20]

=== 测试2：考试座位号 ===
排序前: [33, 7, 21, 9, 45, 12]
排序后: [7, 9, 12, 21, 33, 45]

=== 测试3：已有部分有序 ===
排序前: [2, 3, 5, 1, 4]
排序后: [1, 2, 3, 4, 5]

插入排序的特点

时间复杂度：最坏情况下（完全逆序）需要比较大约 n²/2 次，时间复杂度为 O(n²)；最好情况下（已经有序）只需比较 n-1 次，时间为 O(n)。平均也是 O(n²)。
空间复杂度：只使用了几个额外变量，是 原地排序（不需要额外数组），空间复杂度 O(1)。
稳定性：相等元素不会交换位置，所以是稳定排序。比如两个同学考了相同分数，原本排名靠前的同学排序后依然靠前。
适用场景：数据量小（几十个以内）或者数据基本有序时效率很高。比如整理一个班级十几人的身高数据、对每周记录的小额账单排序。

插入排序