插入排序(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)}}#
是否稳定 是