前言

Insertion Sort 是基本的排序法，時間複雜度是 $O(n^2)$, 屬於 stable sorting

概念

之前一直容易把 Selection Sort 與 Insertion Sort 搞混，現在要來還債了

Insertion Sort 把左邊的當作已經排序完，每次都取右邊的數值跟左邊的比，比贏了就插入，比輸了就不動

從右邊數列選來的數字要與左邊數列中的所有數字進行比較(以下稱右邊抓來的數字為A)，如果A在左邊數列中找到比自己大的數字B，這時候B與A做交換，在下一次的迴圈中A位置的值就變成B，這時候B變成右邊的數字，繼續與左邊數列做比較

其實插入排序法的code比起氣泡排序還有選擇排序是最簡潔的，但總是容易搞混

流程大致如下：

  1. 先設定左邊數列為1個
  2. 每次抓右邊數列的第一個值插入
  3. 右邊數列的值與目前左邊數列的所有數字進行比較，找到比贏的數就 swap

pseudo code

1
2
3
4
5
InsertionSort(A[1..n])
    for i from 2 to n:
        for j from 1 to i:
            if A[i] < A[j]
                swap(A[i], A[j])

複雜度比較

時間複雜度

Sequence Complexity Case
Random $O(N^2)$ Average
Nearly Sorted $O(N)$ Best
Reversed $O(N^2)$ Worst
Few Unique $O(N^2)$ Average

因為 Insertion sort 是假設左邊已經排好的情況下去取右邊的數字，所以對排序過的 array 來說，只要做完一次內層迴圈，沒有發生任何 swap，就可以知道已經排序過了，此時就可以直接 break loop，時間複雜度就是 $O(N)$

空間複雜度

沒有用到額外的 array，$O(1)$ space

可以到 Toptal 的這個網頁觀看不同 case 的視覺化排序過程