排序演算法筆記 3 – Insertion Sort (插入排序法)

Insertion Sort (插入排序法) 的原理也很直觀，將要排序的元素插入已經排列好的左側陣列：

1. Insertion Sort 原理解釋

▲ 將第一個元素視為已經排列好的陣列，因此第一輪從 i = 1 開始跑

▲ 如果待排序的元素比排列好陣列中的最後一個元素還小，代表需要將待排序元素插入已經排序好的陣列中

接著要判斷要插入到排列好陣列中的哪個位置：

第二輪 (i = 2)：

第三輪 (i = 3)

2. JavaScript 實作

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    // 尚未排列的第一個元素
    const currElement = arr[i];
    // 已經排列好的陣列中最後元素的 index
    let j = i - 1;
    // 目標元素要小於已經排列好的陣列中最後的元素，才會進到此迴圈
    while (j >= 0 && currElement < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = currElement;
  }
  return arr;
}

概念圖：

3. Time Complexity

最佳：O(n)
最差：O(n²)
平均：O(n²)

4. 參考資料

大話資料結構(全新彩色版)
資料結構與演算法 (JavaScript)