插入排序法（Insertion Sort）的概念有點像我們一張一張地整理撲克牌，拿出尚未排序的一張，放進已經排序好的排堆裡面。
首先來看 input 和 output：
Input：n 個元素的序列 \(\{a_1, a_2,\dots ,a_n\}\)
Output：一個已經排序好的序列 \(\{a_1′, a_2′,\dots ,a_n’\}\)，其中 \(a_1′ \leq a_2′ \leq \dots \leq a_n’\)。
嗯，好像在講廢話，沒什麼特別的。
流程說明
首先，我們想排序的是這六位數字：2、5、3、6、1、4。
過程差不多是這樣：
一直重複以下動作，從第二個位置（index=1）開始一直到陣列結束（從 2 到 A 的長度）。先設定 key 是第 j 個位置（index=j-1），並且設定檢查項為第 j 個位置的前面，每次檢查完就往前一個位置，一直到第 1 個位置檢查結束（index 從 i -1 到 1）。
好的，前提如果清楚了，就可以開始排序流程了。每次都拿 key 往前對照已排序的部分，如果檢查項大於 key，檢查項則須往後移一格。若沒有大於 key，就不用動（也就是 i+1 的位置就是 key）。
用文字說明比較不好懂，不如直接看圖片或許會比較好想像。
圖片說明
※ 橘色底為目前的檢查項、藍色為 key、綠色打勾為已排序的部分。
首先，5 是 key（從 index=2 的位置開始），2是檢查項。因為 key 沒有比2還要大，所以可以直接放進去檢查項後面一格位置。
再來 key 是第三個位置的 3，檢查項是第三個位置的前一格（第二格，index=1），也就是5。因為檢查項5 大於 key，因此 5 需要往後移一格。
動作完成後，將檢查項的位置往前一格（第一格，index=0），也就是 2。2 沒有大於 key，因此不需要移動，key 就放入檢查項後面一格的位置。
再來 key 是第四個位置的 6，檢查項是第四個位置的前一格（第三格，index=2），也就是 5。5 沒有大於 key，因此不需要移動，6 就放入檢查項後面一格的位置。
再來 key 是第五個位置的 1，噢這項相當小，應該要移動相當多格了XD
- 檢查項是第五個位置的前一格（第四格，index=3），也就是 6。檢查項 6 大於key，因此6需要往後移一格。
- 檢查項的位置往前一格（第三格，index=2），也就是 5。檢查項 5 大於 key，因此 5 需要往後移一格。
- 檢查項的位置往前一格（第二格，index=1），也就是 3。檢查項 3 大於 key 的 1，因此 3 需要往後移一格。
- 檢查項的位置往前一格（第一格，index=0），也就是 2。檢查項 2 大於 key，因此2需要往後移一格。
- 最後也就剩第一格的位置可以放入key了。
key 終於輪到最後一個數字了！最後的 key 是第六個位置的 4。
- 檢查項是第六個位置的前一格（第五格），也就是 6。檢查項 6 大於 key，因此 6 需要往後移一格。
- 再來檢查項是第五個位置的前一格（第四格），也就是 5。檢查項 5 大於key，因此 5 需要往後移一格。
- 再來檢查項是第四個位置的前一格（第三格），也就是 3。檢查項 3 沒有大於key，因此3不需要移動，4可以放在檢查項後面一格的位置。
完成排序了！！！！基本上核心概念就是：指定 key 的值（從第二格開始），並從 key 的位置開始往前檢查，比 key 大就往後移一格，沒有移動就把 key 塞到適當位置。檢查完後 key 的 index 往後一格取值，重複前述步驟往前檢查。
已經有了圖像的概念，再來看虛擬碼應該會容易一些。
for j = 1 to A.length
key = A[j] //設定key
i = j - 1 //開始從key的前一個位置往前檢查
while i >= 0 and A[i] > key //目前檢查項大於key的話
A[i+1] = A[i] //把檢查項往後移一格
i = i - 1 //index往前一格
A[i+1] = key //檢查完之後，在目前跑到的index放入key
分析
分析氣泡排序的時間複雜度。最好的狀況是 \(O(n)\)，也就是順序剛好都排好時（未進行任何 swap）。平均來說是 \(O(n^2)\)，尤其是資料由大到小，完全相反，因此每次執行次數為 n-1 次、n-2 次……一直到 1 次。
\(\displaystyle (n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2} = \frac{n^2-n}{2} \Rightarrow O(n^2)\)
實作
接著照上方 pseudo code 試著實作看看（C++）。
#include <vector>
using namespace std;
vector<int> insertionSort(vector<int> array) {
for (int j = 1; j < array.size(); j++){
int key = array[j];
int i = j - 1;
while (i >= 0 && array[i] > key){
array[i+1] = array[i];
i = i - 1;
}
array[i+1] = key;
}
return array;
}
