這篇來介紹的演算法是和前面介紹的泡沫排序、選擇排序同時間複雜度的排序法O(n^2)- Insertion sort，又叫插入排序。以下的gif就是其運作方式：
老慣例，依舊從說文解字開始，插入排序基本上就是從排好的數列中，把值給插進去，類似你打牌時候會排牌一樣，所以標題才說「超日常」，假設你手上的牌是：
（暫且不考慮花色）
1 6 9 J Q K
當你拿到 8 時，你會找到6跟9中間可以插，然後把牌插進去，變成：
1 6 8 9 J Q K
換成程式的話主要有兩個動作，插入、後移，後移什麼？插入前要先把整體後移，然後才能把值插進去。所以想實作的可以先看到這邊就停下來，往這兩個方向去想並實作了。下面是例子：
如果我們要把值從小排到大
假設我們有一個長度為6的陣列
arr[6] = {6,5,8,12,9,11}
第一輪
從第二個開始掃先宣告一個整數 temp然後把第二個值存到temp裡面
5 < 6，所以開始往前看只要比5大的通通都往後移找到適合的位置後(也就是arr[0])，把temp插到arr[0]裡面此輪結果
5 6 8 12 9 11
第二輪
從第三個開始掃把第三個值存到temp裡面6 < 8所以就不變此輪結果
5 6 8 12 9 11
第三輪
從第四個開始掃把第四個值存到temp裡面8 < 12所以就不變此輪結果
5 6 8 12 9 11
第四輪
從第五個開始掃把第五個值存到temp裡面9 < 12所以就不變此輪結果
5 6 8 9 12 11
第五輪
從第六個開始掃把第六個值存到temp裡面12 > 11，所以開始往前看只要比11大的都往後移找到適合的位置後(也就是arr[4])，把temp插到arr[4]裡面此輪結果
5 6 8 9 11 12
這樣就完成了！很簡單吧！
一般來說，插入排序在小型的陣列中，運作效率會是最好的，或者更精確地說，插入排序在幾乎要排列好的數據中效率是最好的，接近O(n)。所以在Python的排序法TimSort中，其實也混用了插入排序，讓它在某些情況下可以優化整體，至於細節我就不清楚了，想了解的可以去維基看看。
以下是我用java寫的程式碼
純迴圈版:
public static void insertionSort(int[] arr, int beginI, int endI){ if(beginI == endI){ return; } int temp; int j; for (int i = beginI+1; i < endI+1; i++) { temp = arr[i]; j = i-1; while(j>=0 && temp < arr[j] ){ arr[j+1] = arr[j]; j--; } arr[j+1] = temp; } } |
遞迴版:
public static void insertionSort(int[] arr, int beginI, int endI){ if(beginI == endI){ return; } insertionSort(arr, beginI, endI-1); int temp; int j = endI; temp = arr[endI]; while(j-1 >= beginI && temp < arr[j-1] ){ j--; arr[j+1] = arr[j]; } arr[j] = temp; } |
達人
