插入排序(Insertion Sort)算法,是基本的排序算法,是学习编程语言最先需要学会的排序算法之一。插入排序法的用途广泛,除了可以用来将新元素添加到已存在且已排序好的串行并维持其排序外,还可以用来排序尚未排序的串行。而且其排序结果是稳定的。
插入排序法(Insertion Sort)
插入排序法的概念
当我们想把一个元素加进一个已排序好的串行,且想保持串行是已排序的状态时,插入排序法会从串行最尾端开始往前判断要插入的元素是否大于等于目前判断位置的元素,若是,则将元素放置于目前判断位置的后一个的位置;若不是,则将目前判断位置的元素往后移一个位置,腾出空位以便让其他元素使用,接着再继续往前判断。
运用以上这个方法,当我们想排序尚未排序的串行时,可以在这个串行中的前端设想出一个虚拟的子串行,当作是已排序的串行,而这个已排序好的子串行之后的元素,就是我们要依次插入进这个子串行的元素。
插入排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
一开始,从数组前端开始,已排序好的子数组的长度为 0,因此我们可以直接将数组中索引 0 的元素作为进入已排序的子数组的第一个元素。
○ 索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
接着就是要把已排序的子数组的下一个元素插入子数组中。
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
由于要插入的元素 81 大于或等于子数组中的元素 69,因此直接把要插入的元素 81,加进子数组中的元素 69 的下一个位置。
○ ○ 索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
此时前端已排序好的子数组长度为 2 了。接着,同样地要把已排序的子数组的下一个元素插入子数组中。
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
81 > 30
由于要插入的元素 30 小于子数组中的元素 81,因此直接把子数组中的元素 81 往后移动一个位置。
○ 30 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 81 38 9 2 47 61 32 79
└→┘
要插入的元素 30 则会继续尝试插入至比较前面的索引位置中。
○ 30 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 81 38 9 2 47 61 32 79
└┬┘
69 > 30
由于要插入的元素 30 小于子数组中的元素 69,因此直接把子数组中的元素 69 往后移动一个位置。
30 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 69 81 38 9 2 47 61 32 79
└→┘
因为要插入的元素 30 已经找到子数组的最前端了,所以就直接把插入的元素 30 放入子数组的最前端的位置。
30 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 38 9 2 47 61 32 79
│
○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 38 9 2 47 61 32 79
接下来也是使用一样的方式,将已排序的子数组后剩余的元素通通插进这个子数组中。完整过程如下:
○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
69 < 81
○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 30 38 9 2 47 61 32 79
└┬┘
81 > 30
○ 30 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 81 38 9 2 47 61 32 79
└→┘
○ 30 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 81 81 38 9 2 47 61 32 79
└┬┘
69 > 30
30 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 69 69 81 38 9 2 47 61 32 79
└→┘
30 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 38 9 2 47 61 32 79
│
○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 38 9 2 47 61 32 79
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 38 9 2 47 61 32 79
○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 38 9 2 47 61 32 79
└┬┘
81 > 38
○ ○ 38 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 81 9 2 47 61 32 79
└→┘
○ ○ 38 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 81 81 9 2 47 61 32 79
└┬┘
69 > 38
○ 38 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 69 81 9 2 47 61 32 79
└→┘
○ 38 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 69 69 81 9 2 47 61 32 79
└┬┘
30 < 38
○ 38 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 81 9 2 47 61 32 79
│
○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 81 9 2 47 61 32 79
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 81 9 2 47 61 32 79
○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 81 9 2 47 61 32 79
└┬┘
81 > 9
○ ○ ○ 9 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 81 81 2 47 61 32 79
└→┘
○ ○ ○ 9 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 81 81 2 47 61 32 79
└┬┘
69 > 9
○ ○ 9 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 69 81 2 47 61 32 79
└→┘
○ ○ 9 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 69 69 81 2 47 61 32 79
└┬┘
38 > 9
○ 9 ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 38 69 81 2 47 61 32 79
└→┘
○ 9 ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 38 38 69 81 2 47 61 32 79
└┬┘
30 > 9
9 ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 30 30 38 69 81 2 47 61 32 79
└→┘
9 ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 81 2 47 61 32 79
│
○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 81 2 47 61 32 79
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 81 2 47 61 32 79
○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 81 2 47 61 32 79
└┬┘
81 > 2
○ ○ ○ ○ 2 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 81 81 47 61 32 79
└→┘
○ ○ ○ ○ 2 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 81 81 47 61 32 79
└┬┘
69 > 2
○ ○ ○ 2 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 69 81 47 61 32 79
└→┘
○ ○ ○ 2 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 69 69 81 47 61 32 79
└┬┘
38 > 2
○ ○ 2 ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 38 69 81 47 61 32 79
└→┘
○ ○ 2 ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 38 38 69 81 47 61 32 79
└┬┘
30 > 2
○ 2 ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 30 38 69 81 47 61 32 79
└→┘
○ 2 ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 30 30 38 69 81 47 61 32 79
└┬┘
9 > 2
2 ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 9 9 30 38 69 81 47 61 32 79
└→┘
2 ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 81 47 61 32 79
│
○ ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 81 47 61 32 79
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 81 47 61 32 79
○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 81 47 61 32 79
└┬┘
81 > 47
○ ○ ○ ○ ○ 47 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 81 81 61 32 79
└→┘
○ ○ ○ ○ ○ 47 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 81 81 61 32 79
└┬┘
69 > 47
○ ○ ○ ○ 47 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 69 81 61 32 79
└→┘
○ ○ ○ ○ 47 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 69 69 81 61 32 79
└┬┘
38 < 47
○ ○ ○ ○ 47 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 81 61 32 79
│
○ ○ ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 81 61 32 79
○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 81 61 32 79
○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 81 61 32 79
└┬┘
81 > 61
○ ○ ○ ○ ○ ○ 61 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 81 81 32 79
└→┘
○ ○ ○ ○ ○ ○ 61 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 81 81 32 79
└┬┘
69 > 61
○ ○ ○ ○ ○ 61 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 69 81 32 79
└→┘
○ ○ ○ ○ ○ 61 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 69 69 81 32 79
└┬┘
47 < 61
○ ○ ○ ○ ○ 61 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 81 32 79
│
○ ○ ○ ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 81 32 79
○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 81 32 79
○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 81 32 79
└┬┘
81 > 32
○ ○ ○ ○ ○ ○ ○ 32 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 81 81 79
└→┘
○ ○ ○ ○ ○ ○ ○ 32 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 81 81 79
└┬┘
69 > 32
○ ○ ○ ○ ○ ○ 32 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 69 81 79
└→┘
○ ○ ○ ○ ○ ○ 32 ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 69 69 81 79
└┬┘
61 > 32
○ ○ ○ ○ ○ 32 ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 61 69 81 79
└→┘
○ ○ ○ ○ ○ 32 ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 61 61 69 81 79
└┬┘
47 > 32
○ ○ ○ ○ 32 ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 47 61 69 81 79
└→┘
○ ○ ○ ○ 32 ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 47 47 61 69 81 79
└┬┘
38 > 32
○ ○ ○ 32 ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 38 47 61 69 81 79
└→┘
○ ○ ○ 32 ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 38 38 47 61 69 81 79
└┬┘
30 < 32
○ ○ ○ 32 ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
│
○ ○ ○ ○ ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
○ ○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
○ ○ ○ ○ ○ ○ ○ ○ ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 79
└┬┘
81 > 79
○ ○ ○ ○ ○ ○ ○ ○ 79 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 81
└→┘
○ ○ ○ ○ ○ ○ ○ ○ 79 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 81 81
└┬┘
69 < 79
○ ○ ○ ○ ○ ○ ○ ○ 79 ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
│
○ ○ ○ ○ ○ ○ ○ ○ ○ ○
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
插入排序法的程序实作
插入排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n^2)}}# | 排序已经反向排序过的串行。 |
| 最佳时间复杂度 | #{{O(n)}}# | 排序已经正向排序过的串行。 |
| 平均时间复杂度 | #{{O(n^2)}}# | |
| 最差空间复杂度 | #{{O(1)}}# | |
| 是否稳定 | 是 |

