插入排序

定义与基本思想

插入排序（Insertion Sort）是一种简单直观的排序方法。其基本思想是：每次将一个待排序元素插入到已排好序的序列中，直到全部元素有序。

插入排序演示

524613

下一步

算法描述

1. 从第 2 个元素开始，依次与前面已排序序列比较，找到合适位置插入
2. 重复直到所有元素排序完成

伪代码如下：

for i = 1 to n-1:
    key = A[i]
    j = i-1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j--
    A[j+1] = key

时间复杂度分析

• 最好情况：$O(n)$（原本有序）
• 最坏/平均情况：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定排序

练习题

练习 1

对数组 $A = [5, 2, 4, 6, 1, 3]$ 进行插入排序，写出每一趟排序后的结果。

参考答案

解题思路：每次插入一个元素到前面有序序列。

详细步骤：

1. 初始：[5, 2, 4, 6, 1, 3]
2. 第 1 趟：[2, 5, 4, 6, 1, 3]
3. 第 2 趟：[2, 4, 5, 6, 1, 3]
4. 第 3 趟：[2, 4, 5, 6, 1, 3]
5. 第 4 趟：[1, 2, 4, 5, 6, 3]
6. 第 5 趟：[1, 2, 3, 4, 5, 6]

答案：如上，每一趟插入后序列逐步有序。

练习 2

插入排序的时间复杂度和空间复杂度分别是多少？

参考答案

解题思路：考查复杂度和空间。

详细步骤：

1. 时间复杂度 $O(n^2)$
2. 空间复杂度 $O(1)$

答案：时间 $O(n^2)$，空间 $O(1)$。