排序演算法 | 插入排序

插入排序（英語：Insertion Sort）是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

如果有一個已經有序的資料序列，要求在這個已經排好的資料序列中插入一個數，但要求插入後此資料序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個資料插入到已經排好序的有序資料中，從而得到一個新的、個數加一的有序資料，算法適用於少量資料的排序，時間複雜度為O(n²)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。

插入排序的基本思想是：
每步將一個待排序的記錄，按其關鍵碼值的大小插入到前面已經排序的數組中的適當位置上，直到全部插入完為止。

使用插入排序為一列數字進行排序的過程：

實作範例(Java)

@Test
public void InsertionSort() {
    int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    for (int i = 1; i < arr.length; i++) {
        // 定義待插入的數
        int insertValue = arr[i];
        // 找到待插入數的前一個數的下標
        int insertIndex = i - 1;
        while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertValue;
    }
    System.out.println(Arrays.toString(arr));
}

結果：

1	[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

在這裡，因為數組元素我們並不確定，所以只能將數組的第一個元素看成是一個有序的序列，所以從數組的第二個元素開始才是我們需要去尋找插入位置的元素。所以外層循環從1開始，然後將arr[i]，也就是當前的第二個元素先保存起來，然後找到待插入元素的前一個元素下標，也就是i-1，此時通過一個while循環去比較。

當insertIndex小於0時應該退出循環，因為此時已經與前面的所有元素比較完畢。在比較的過程中，如果待插入元素小於前一個元素，就將前一個元素後移，也就是將前一個元素的值直接賦值給待插入元素位置。因為在最開始已經將待插入元素進行了保存，所以只需將待插入元素的值賦值給它的前一個元素即可。因為在while循環中insertIndex執行了自減操作，所以它的前一個元素下標應為insertIndex + 1。而如果待插入的元素值大於前一個元素，那麼就不會進入while循環，這樣insertIndex + 1之後的位置仍然是自己所在的位置，所以賦值後值不改變，後面的操作以此類推。