其實插入排序法就很像平時我們在玩撲克牌時整理牌組的行為，將撲克牌依照大小插入對應的位置，插入排序法的流程是從第2個位置開始與左邊的數字(位置1)比較，然後就依循著以下的規則，與左邊的元素比大小，並且插入到正確的位置，直到全部的元素的由小排到大。

假設有個陣列為 [40 , 13 , 20 , 8]

1. 從第二個位置開始，13與40相比13比較小，因此把13插入到40之前
   
   此時陣列為[13 , 40, 20 , 8]

2. 再來輪到20，20大於13且小於40 ，所以就將20插入到13和40之間
   
   此時陣列為[13 , 20, 40 , 8]

3. 最後輪到8 ，與前面三個元素相比為最小值 ，所以就插入到最前面
   
   此時陣列為[8, 13 , 20, 40]

連續的步驟會如下圖所示

圖檔來源:https://visualgo.net/zh/

用js實作插入排序法:

const insertionSort = (arr) => {
    //因為要跟左邊數字比大小所以迴圈的從1開始 (i=0的話沒有左邊的數字)
    for (let i = 1; i < arr.length; i++) {
        let current = arr[i];
        //左邊的數字index - 1
        let point = i - 1;
        //檢查左邊數字是否大於現在的數字
        while (point >= 0 && arr[point] > current) {
            arr[point + 1] = arr[point];
            point--;
        }
        arr[point + 1] = current;
    }
    return arr;
};

insertionSort([40, 13, 20, 8]);

時間複雜度

• 在最差的情況下，時間複雜度是O(n²)
• 在最佳的情況下，時間複雜度是O(n)
• 在平均情況下，時間複雜度為 O(n²)