插入排序：像整理图书一样把新书插到合适位置

你整理过书架吗？假设书架上的书已经按字母顺序排好了，现在你要把一本新书放进去。你会从右边开始，一本一本比较，找到合适的位置，把新书插进去，后面的书往后移动一个位置。插入排序就是这种思想——它把数组看成两部分：左边是已经排好的序列（一开始只有第一个元素），右边是未排序的序列。然后逐个取出未排序的元素，在已排序部分中从右向左比较，找到适当的位置插入。

生活中的插入排序——整理扑克牌

想象一下你正在玩扑克牌，手里已经抓了几张牌，你习惯把它们按从小到大的顺序排好。每摸到一张新牌，你会怎么做？你会看一眼手里的牌，然后从右边（最大的牌）开始往左看，找到比新牌小（或相等）的那张，再把新牌插到它后面。这就是插入排序！

例如你手里的牌是 5, 7, 9，现在摸到一张 8：

• 一看最右边的 9，8 比 9 小，所以 9 要往右挪一步；
• 再看 7，8 比 7 大，好了，位置找到了，就把 8 插在 7 和 9 之间。
• 最后手牌变成 5, 7, 8, 9。

你看，整个过程跟插入排序一模一样！

算法核心：把数组分成“已排序”和“未排序”两部分

插入排序的思路很简单：

1. 一开始，把第一个元素看作 已排序区（因为只有一个元素，它自己就是排好的）。
2. 剩下的元素都是 未排序区。
3. 每次从 未排序区 取出第一个元素（叫做“当前元素”），把它插入到 已排序区 的正确位置。
4. 插入时，从已排序区的 最右边 开始，一一比较，如果已排序区的元素比当前元素大，就把它往右挪一个位置；如果比当前元素小，就停在这里，把当前元素插到它后面。
5. 重复第3、4步，直到所有元素都进入已排序区。

详细演示：一步一步看过程

我们用数组 [12, 11, 13, 5, 6] 来走一遍：

初始状态：已排序区 = [12]，未排序区 = [11,13,5,6]

第一轮（i=1，处理11）：

• 当前元素 = 11
• 已排序区最右边是 12，11 < 12，所以把 12 往右移一位（原来位置变成空）
• 继续往左，已经没有元素了（j = -1），停止
• 把 11 插入到位置0 → 数组变成 [11, 12, 13, 5, 6]

第二轮（i=2，处理13）：

• 当前元素 = 13
• 已排序区最右边是 12，13 > 12，所以不需要移动，直接插在末尾 → [11, 12, 13, 5, 6]

第三轮（i=3，处理5）：

• 当前元素 = 5
• 已排序区 = [11,12,13]，从右向左：
  • 5 < 13 → 13 右移 → [11,12,__,13]
  • 5 < 12 → 12 右移 → [11,__,12,13]
  • 5 < 11 → 11 右移 → [__,11,12,13]
  • 没有更多元素了，停止
• 把 5 插入到位置0 → [5,11,12,13,6]

第四轮（i=4，处理6）：

• 当前元素 = 6
• 已排序区 = [5,11,12,13]，从右向左：
  • 6 < 13 → 13 右移 → [5,11,12,__,13]
  • 6 < 12 → 12 右移 → [5,11,__,12,13]
  • 6 < 11 → 11 右移 → [5,__,11,12,13]
  • 6 > 5 → 停止
• 把 6 插入到位置1（5的后面）→ [5,6,11,12,13]

排序完成！

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

我们来看 Python 代码。注意每一行都写了中文注释，帮助你理解每一步在做什么。

def insertion_sort(arr):
    # 获取数组长度
    n = len(arr)
    # 从第二个元素（下标1）开始，因为第一个默认已排序
    for i in range(1, n):
        key = arr[i]          # 当前要插入的元素
        j = i - 1             # 已排序部分的最后一个下标
        # 从右向左比较，如果比key大就右移
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 把大的元素往后挪
            j -= 1               # 继续往左看
        arr[j + 1] = key      # 插入到正确位置
    return arr

代码执行过程动画（文字版）

假设数组是 [9, 3, 7, 4, 6, 2, 8]：

新手容易犯的 3 个错误

错误1：循环条件写反了

有的同学在 while 循环里写成 arr[j] < key，结果把小的元素往右移，这样永远插不对位置。记住：只有大于 key 的元素才需要右移。

# 错误写法
while j >= 0 and arr[j] < key:   # 这样会把小的元素也移走
    arr[j + 1] = arr[j]
    j -= 1

错误2：忘记更新 j 的值

有的同学只写了移动语句，忘记 j -= 1，导致循环一直比较同一个元素，陷入死循环。

while j >= 0 and arr[j] > key:
    arr[j + 1] = arr[j]
    # 漏写 j -= 1

错误3：插回 key 的时候写错下标

有人写成 arr[j] = key 而不是 arr[j+1] = key。因为 while 循环结束后 j 已经指向了第一个小于等于 key 的元素位置（或者 j=-1），我们需要把 key 放在它的右边，也就是 j+1 的位置。

# 错误
arr[j] = key   # 会覆盖掉原本应该保留的元素

# 正确
arr[j + 1] = key

完整可运行示例（带输入输出）

下面是一个可以直接运行的程序，它先让用户输入几个数字，然后用插入排序排好并打印结果。

def insertion_sort(arr):
    """插入排序，直接修改原数组"""
    n = len(arr)                  # 数组长度
    for i in range(1, n):         # 从第二个元素开始
        key = arr[i]              # 当前要插入的元素
        j = i - 1                 # 已排序部分的最后一个下标
        while j >= 0 and arr[j] > key:  # 如果已排序部分还有元素且比key大
            arr[j + 1] = arr[j]   # 把大的元素往后移
            j -= 1                # 继续向左检查
        arr[j + 1] = key          # 把key放到正确的位置

# ---------- 主程序 ----------
# 让用户输入一串数字，用空格分隔
user_input = input("请输入一些整数（用空格隔开）：")
# 把输入的字符串转换成整数列表
data = [int(x) for x in user_input.split()]

print("排序前：", data)
insertion_sort(data)
print("排序后：", data)

运行示例：

请输入一些整数（用空格隔开）：9 3 7 4 6 2 8
排序前： [9, 3, 7, 4, 6, 2, 8]
排序后： [2, 3, 4, 6, 7, 8, 9]

插入排序的特点与性能

• 时间复杂度：最坏情况（数组完全逆序）和平均情况都是 O(n²)，因为每个元素都要和前面多数元素比较。最好情况（数组已经有序）只需要 O(n)，只遍历一遍，不用移动。
• 空间复杂度：O(1)，只需要一个临时变量 key，是原地排序。
• 稳定性：稳定的，因为如果遇到相等的元素，我们不会把它移到前面去（条件是 arr[j] > key，等于时不移动），所以相等元素的相对顺序保持不变。
• 适用场景：数据量较小（比如几十个元素），或者数据基本有序时，插入排序非常快。比如学生按学号排好了，只差一两个人没排好，用插入排序效率很高。

相关知识点指引

• 选择排序：也是每次选一个元素放到合适位置，但它是找最小值放到前面，数组的已排序区在左边，未排序区在右边。
• 冒泡排序：通过相邻元素两两比较，把大的“冒”到最后。
• 希尔排序：插入排序的升级版，先把数组分组进行插入排序，让数组大致有序，最后再整体插入排序，效率更高。
• 二分插入排序：用二分查找找到插入位置，可以减少比较次数，但移动次数不变。

如果你刚学完插入排序，可以试着用扑克牌或书本来模拟算法过程，然后动手多写几遍代码。记住：从第二个元素开始，把每个元素往左边已排序的序列里插，你就掌握了插入排序的核心思想！