插入排序在最坏情况下的时间复杂度是多少？

Question

在插入排序中，当输入数组为完全逆序时，每个元素都需要与已排序部分的所有元素进行比较和移动，导致执行次数达到最大。此时，第 i 个元素需要最多 i−1 次比较和赋值操作，总的操作次数接近 ∑(i=1 到 n−1) i = n(n−1)/2，因此时间复杂度为 O(n²)。这是插入排序的最坏情况。常见问题是：**为什么插入排序在最坏情况下时间复杂度是 O(n²)，具体是如何推导出来的？** 该问题常出现在算法分析面试或课程作业中，考察对基本排序算法执行过程与渐进复杂度理解的深度。

Answer 1

1. 插入排序基础与执行过程解析

插入排序是一种简单直观的排序算法，其核心思想是将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。对于长度为 n 的数组，算法从索引 1 开始遍历每个元素，将其与前面已排序部分从右向左比较，直到找到合适位置并插入。

考虑一个完全逆序的数组，例如：[5, 4, 3, 2, 1]。在这种情况下，每一个新元素都小于其前面所有已排序元素，因此必须移动所有已排序元素才能完成插入。

插入轮次 i	待插入元素	已排序部分长度	比较次数	移动（赋值）次数
1	4	1	1	1
2	3	2	2	2
3	2	3	3	3
4	1	4	4	4

2. 最坏情况下的操作次数分析

在完全逆序输入中，第 i 轮插入操作（i 从 1 到 n−1）需要与前面 i 个元素逐一比较，并执行 i 次数据移动（即赋值操作）。因此，每轮最多产生 i 次比较和 i 次移动。

总的比较次数为：

∑(i=1 到 n−1) i = 1 + 2 + 3 + ... + (n−1) = n(n−1)/2

同样，总的数据移动次数也为 n(n−1)/2。由于每次比较和移动均为常数时间操作，整体时间复杂度由该二次项主导。

• 当 n = 5 时，总操作数 ≈ 5×4/2 = 10 次
• 当 n = 10 时，总操作数 ≈ 10×9/2 = 45 次
• 当 n = 100 时，总操作数 ≈ 4950 次

3. 时间复杂度的数学推导与渐进分析

设 T(n) 表示插入排序在最坏情况下的总操作次数。根据上述分析：

T(n) = ∑_{i=1}^{n-1} i = \frac{n(n-1)}{2}

展开后得：

T(n) = \frac{1}{2}n^2 - \frac{1}{2}n

根据大 O 表示法的定义，我们只保留最高阶项并忽略常数系数，因此：

T(n) ∈ O(n²)

这表明插入排序在最坏情况下的时间增长速率与输入规模的平方成正比。下表对比不同规模下的实际操作数与理论值：

n（数组长度）	比较次数	移动次数	总操作数	O(n²) 近似值
10	45	45	90	100
50	1225	1225	2450	2500
100	4950	4950	9900	10000
500	124750	124750	249500	250000

4. 算法行为可视化：Mermaid 流程图展示执行逻辑

以下 Mermaid 流程图展示了插入排序在处理逆序数组时的核心控制流程：

```mermaid
graph TD
    A[开始] --> B{i = 1}
    B --> C{i < n?}
    C -- 否 --> D[结束]
    C -- 是 --> E[key = arr[i]]
    E --> F{j = i - 1}
    F --> G{j >= 0 且 arr[j] > key?}
    G -- 是 --> H[arr[j+1] = arr[j]]
    H --> I{j = j - 1}
    I --> G
    G -- 否 --> J[arr[j+1] = key]
    J --> K{i = i + 1}
    K --> B
```

5. 实际代码实现与性能验证

以下是插入排序的典型实现，可用于验证最坏情况下的行为：

def insertion_sort(arr):
    n = len(arr)
    comparisons = 0
    movements = 0
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            comparisons += 1
            arr[j + 1] = arr[j]
            movements += 1
            j -= 1
        arr[j + 1] = key
    return comparisons, movements

测试完全逆序数组：

arr = [5, 4, 3, 2, 1]
comp, move = insertion_sort(arr.copy())
print(f"比较次数: {comp}, 移动次数: {move}")  # 输出: 比较次数: 10, 移动次数: 10