第 13 课 - 插入排序

学习目标

完成本课学习后，你将能够：

理解插入排序的基本思想及其“逐步构建有序序列”的工作过程。
掌握插入排序的代码实现，并能够解释核心的“移位”操作。
分析插入排序的时间复杂度和空间复杂度。
理解插入排序是稳定排序算法的原因。
能够区分插入排序与上一课所学的选择排序在逻辑和操作上的不同。

核心概念

想象一下你在玩扑克牌，当你一张一张从牌堆里摸牌时，你会将新摸到的牌插入到手中已有牌序列的正确位置，从而保持手中牌始终有序。这就是插入排序的精髓。

插入排序的工作方式类似于此：

将数组视为两部分：已排序部分（初始时只有第一个元素）和未排序部分（从第二个元素开始）。
每次从未排序部分取出第一个元素（称为“关键码”或 key）。
在已排序部分中从后向前扫描，找到关键码应该插入的位置。
在寻找位置的过程中，将比关键码大的元素向后移动一位（这就是 shift 操作），为关键码腾出空间。
将关键码插入到正确位置。
重复步骤2-5，直到未排序部分为空。

这个过程可以概括为：从未排序区取一个元素，在已排序区为它找位置，同时进行移位。

为什么它是稳定的？ 因为在移动元素时，我们只将大于 key 的元素后移。如果遇到等于 key 的元素，扫描会停止，key 会被插入到这个相等元素的后面。这保证了原始序列中相等元素的相对顺序不会改变，因此是稳定排序。

代码示例

基础实现

def insertion_sort(arr):
    # 从第二个元素（索引1）开始遍历，因为第一个元素默认已排序
    for i in range(1, len(arr)):
        # 取出当前需要插入的元素
        key = arr[i]
        # j 指向已排序部分的最后一个元素
        j = i - 1

        # 在已排序部分从后向前扫描，寻找 key 的正确位置
        # 条件1: j >= 0 防止索引越界
        # 条件2: arr[j] > key 表示当前元素比 key 大，需要后移
        while j >= 0 and arr[j] > key:
            # 将比 key 大的元素向后移动一位（腾出位置）
            arr[j + 1] = arr[j]
            j -= 1
        
        # 循环结束时，j+1 就是 key 应该插入的位置
        arr[j + 1] = key
    
    return arr

# 测试代码
data = [12, 11, 13, 5, 6]
print("原始数组:", data)
sorted_data = insertion_sort(data)
print("排序后数组:", sorted_data)

# 输出：
# 原始数组: [12, 11, 13, 5, 6]
# 排序后数组: [5, 6, 11, 12, 13]

优化版本（带提前终止）

如果在已排序部分找到了一个比 key 小的元素，就可以停止扫描了，因为这说明 key 已经找到了正确的位置。这可以略微提高在数组近乎有序时的效率。

def insertion_sort_optimized(arr):
    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
        arr[j + 1] = key
    return arr

复杂度分析

时间复杂度：
- 最优情况 (数组已有序): O(n)。每次内层循环只需比较一次就停止。
- 最坏情况 (数组逆序): O(n²)。每个元素都需要和已排序部分的所有元素比较并移位。
- 平均情况: O(n²)。
空间复杂度: O(1)。它是原地排序算法，只需要常数级别的额外空间（用于存储 key 和循环变量）。

实践练习

练习1：手动模拟

给定数组 [8, 4, 3, 7, 1]，请逐步写出插入排序的过程。你需要展示每一轮外层循环后，已排序部分和未排序部分的状态，以及插入的元素是什么。 预期输出示例格式：

初始状态: [8, 4, 3, 7, 1]
第1轮 (i=1, key=4): 已排序[4, 8], 未排序[3, 7, 1]
第2轮 (i=2, key=3): ...
...

练习2：实现链表插入排序

为单链表实现插入排序算法。提示：链表的插入排序同样维护一个已排序的子链表。每次从原链表取一个节点，插入到已排序子链表的正确位置。注意调整节点指针。

# 链表节点定义
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insertion_sort_list(head: ListNode) -> ListNode:
    # 你的代码实现
    pass

# 测试数据: 4->2->1->3
# 预期输出: 1->2->3->4

练习3：计数交换次数

修改插入排序的实现，增加一个功能：计算并返回排序过程中元素后移操作的总次数。这有助于理解算法的运行开销。 预期输出：

def insertion_sort_count_shifts(arr):
    # 在实现中，每执行一次 `arr[j+1] = arr[j]` 就计数一次
    # 返回排序后的数组和总移位次数
    pass

# 测试
data = [5, 2, 4, 6, 1, 3]
sorted_data, shifts = insertion_sort_count_shifts(data)
print(f"数组 {data} 排序需要 {shifts} 次移位操作。")
# 可能的输出：数组 [5, 2, 4, 6, 1, 3] 排序需要 10 次移位操作。

常见错误

循环边界错误：将外层循环写成 for i in range(len(arr))，从索引0开始。这样第一个元素会自己和自己比较一次，虽然结果正确，但逻辑上不清晰，且浪费一次循环。正确应从索引1开始。
移位操作理解错误：初学者可能误以为“移位”是交换两个元素（像冒泡排序）。实际上，移位是覆盖：arr[j+1] = arr[j]，把 arr[j] 的值复制到 arr[j+1]，然后 j 继续向前找。最终 arr[j+1] 的位置才用来放 key。
误以为不稳定：有人可能会因为看到元素被大幅度移动，就认为它不稳定。关键在于理解：只有当 arr[j] > key 时才移位。如果 arr[j] == key，循环条件 arr[j] > key 为假，循环停止，key 被放在相等元素的后面，因此稳定性得以保持。
使用额外数组：错误地创建一个新数组来存放排序结果，导致空间复杂度变成 O(n)。插入排序的优势之一就是原地排序，应直接在原数组上进行修改。

小结

核心思想：将数组分为已排序和未排序两部分，从未排序部分取元素，插入到已排序部分的正确位置。
关键操作：在已排序部分从后向前扫描时进行的移位操作。
效率：时间复杂度为 O(n²)，但在数据规模小或基本有序时表现良好（常数因子小，可提前终止）。
稳定性：是稳定的排序算法，因为相等元素的相对顺序不会被改变。
与选择排序对比：选择排序是从无序区选最小放到有序区末尾；插入排序是从无序区取一个插入到有序区中。两者都是 O(n²)，但插入排序通常在实践中更快，且是稳定的。
应用场景：适用于小规模数据排序，或作为更高级排序算法（如希尔排序）的组成部分。它是很多标准库排序函数中处理小数据块的首选算法。

掌握了插入排序，理解了其“移位”和“构建有序序列”的思想后，下一课我们将学习如何利用这种思想，通过引入“间隔”的概念来改进排序效率，这就是希尔排序。

练习编辑器

rust