插入排序(Insertion Sort)演算法，一邊將元素加進序列、一邊進行排序的演算法

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

插入排序法的程式實作

/// 插入排序法(遞增)。
pub fn insertion_sort(array: &mut [i32]) {
    'outer: for i in 1..array.len() {
        let temp = array[i];

        let mut j = i - 1;

        while temp < array[j] {
            array[j + 1] = array[j];

            if j == 0 {
                array[j] = temp;
                continue 'outer;
            }

            j -= 1;
        }

        array[j + 1] = temp;
    }
}

/// 插入排序法(遞減)。
pub fn insertion_sort_desc(array: &mut [i32]) {
    'outer: for i in 1..array.len() {
        let temp = array[i];

        let mut j = i - 1;

        while temp > array[j] {
            array[j + 1] = array[j];

            if j == 0 {
                array[j] = temp;
                continue 'outer;
            }

            j -= 1;
        }

        array[j + 1] = temp;
    }
}

/**
 * 插入排序法(遞增)。
 */
public static void insertionSort(final int[] array) {
    for (int i = 1; i < array.length; ++i) {
        final int temp = array[i];

        int j = i - 1;

        while (j >= 0 && temp < array[j]) {
            array[j + 1] = array[j--];
        }

        array[j + 1] = temp;
    }
}

/**
 * 插入排序法(遞減)。
 */
public static void insertionSortDesc(final int[] array) {
    for (int i = 1; i < array.length; ++i) {
        final int temp = array[i];

        int j = i - 1;

        while (j >= 0 && temp > array[j]) {
            array[j + 1] = array[j--];
        }

        array[j + 1] = temp;
    }
}

/**
 * 插入排序法(遞增)。
 */
function insertionSort(array: number[]) {
    for (let i = 1;i < array.length;i++) {
        const temp = array[i];
 
        let j = i - 1;
 
        while (j >= 0 && temp < array[j]) {
            array[j + 1] = array[j];

            j -= 1;
        }
 
        array[j + 1] = temp;
    }
}
 
/**
 * 插入排序法(遞減)。
 */
function insertionSortDesc(array: number[]) {
    for (let i = 1;i < array.length;i++) {
        const temp = array[i];
 
        let j = i - 1;
 
        while (j >= 0 && temp > array[j]) {
            array[j + 1] = array[j];

            j -= 1;
        }
 
        array[j + 1] = temp;
    }
}

// 插入排序法(遞增)。
func InsertionSort(array []int) {
	length := len(array)

	for i := 1; i < length; i += 1 {
		temp := array[i]

		j := i - 1

		for j >= 0 && temp < array[j] {
			array[j+1] = array[j]
			j -= 1
		}

		array[j+1] = temp
	}
}

// 插入排序法(遞減)。
func InsertionSortDesc(array []int) {
	length := len(array)

	for i := 1; i < length; i += 1 {
		temp := array[i]

		j := i - 1

		for j >= 0 && temp > array[j] {
			array[j+1] = array[j]
			j -= 1
		}

		array[j+1] = temp
	}
}

插入排序法的複雜度