插入排序

定义¶

插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。

具体说明与示例¶

以无序数组 A = [5, 2, 4, 6, 1, 3] 为例，演示插入排序如何将元素插入到已排序序列中：

初始状态
- 已排序子数组仅包含第一个元素：[5]，其余元素待插入。
第二轮（$i = 2$）
待插入元素 key = A[2] = 2。
在已排序子数组 [5] 中，从右向左比较：5 > 2，将 5 向右移动。
在正确位置插入 2，结果：
```
[2, 5, 4, 6, 1, 3]
```
第三轮（$i = 3$）
- key = A[3] = 4。
- 比较已排序部分 [2, 5]：5 > 4，移动；2 <= 4，停止。
- 插入 4，结果：
```
[2, 4, 5, 6, 1, 3]
```
第四轮（$i = 4$）
- key = A[4] = 6。
- 已排序部分 [2, 4, 5] 中，5 <= 6，无需移动，保持不变。
- 结果：
```
[2, 4, 5, 6, 1, 3]
```
第五轮（$i = 5$）
- key = A[5] = 1。
- 比较 [2, 4, 5, 6]：依次移动所有大于 1 的元素。
- 插入 1，结果：
```
[1, 2, 4, 5, 6, 3]
```
第六轮（$i = 6$）
- key = A[6] = 3。
- 比较 [1, 2, 4, 5, 6]：移动 6, 5, 4，停止于 2。
- 插入 3，结果：
```
[1, 2, 3, 4, 5, 6]
```

具体实现¶

设待排序数组为 A[1..n]：

外层循环：i 从 2 到 n。
将 A[i] 保存为 key，并在位置 j = i-1 开始向已排序子数组中移动元素：

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

重复上述步骤，直到所有元素插入完成。

伪代码

\[ \begin{array}{ll} 1 & \textbf{for } i\gets 2\textbf{ to }n\\ 2 & \qquad key\gets A[i]\\ 3 & \qquad j\gets i-1\\ 4 & \qquad\textbf{while }j>0\textbf{ and }A[j]>key\\ 5 & \qquad\qquad A[j + 1]\gets A[j]\\ 6 & \qquad\qquad j\gets j - 1\\ 7 & \qquad A[j + 1]\gets key \end{array}\]

性质¶

稳定性¶

插入排序是一种稳定的排序算法。

时间复杂度¶

插入排序的最优时间复杂度为 $O(n)$，在数列几乎有序时效率很高。

插入排序的最坏时间复杂度和平均时间复杂度都为 $O(n^2)$。