[排序演算法]Insertion Sort — 插入排序法

其實插入排序法就很像平時我們在玩撲克牌時整理牌組的行為，將撲克牌依照大小插入對應的位置，插入排序法的流程是從第 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]

連續的步驟會如下圖所示

用 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²)