插入排序(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

insertion-sort

插入排序法的程式實作

插入排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目 備註
最差時間複雜度 #{{O(n^2)}}# 排序已經反向排序過的序列。
最佳時間複雜度 #{{O(n)}}# 排序已經正向排序過的序列。
平均時間複雜度 #{{O(n^2)}}#
最差空間複雜度 #{{O(1)}}#
是否穩定