[Easy] 插入排序法 Insertion Sort

插入排序法 Insertion Sort 是程式面試中很常出現的入門考題。以下我們要介紹 Insertion Sort。

如果我們有個 [3, 2, 1, 4] 陣列，我們要把他排成 [1, 2, 3, 4]，用插入排序法可以這麼做：

• 用迴圈迭代過要排序的陣列
• 在迭代時，檢視每個元素，
• 把該元素跟左邊的元素比，
• 如果比左邊的小，就跟左邊的換順序
• 然後繼續一路往左比，直到左邊的比自己小為止，就不用繼續換
• 這時元素就會被插入到應該在的位置

以[3, 2, 1, 4] 陣列具體來說，會是這樣的過程：

[3, 2, 1, 4] // 3 沒有左邊的，不用換
 ^
[3, 2, 1, 4] // 接著到 2
    ^
[2, 3, 1, 4] // 2 比左邊的 3 還小，所以交換

[2, 3, 1, 4] // 接著 到 1
       ^
[2, 1, 3, 4] // 1 比左邊的 3 還小，所以交換

[1, 2, 3, 4] // 1 比左邊的 2 還小，所以交換

[1, 2, 3, 4] // 接著到 4，沒有左邊的比它小，不用換，這時就完成排序
          ^

Insertion Sort 程式碼

function insertionSort(arr) {
  // 用迴圈迭代過要排序的陣列 (i 是已排序區域邊界的索引)
  for (let i = 0; i < arr.length; i++) {
    // 在迭代時，檢視每個元素 (當前元素是在索引 j，也就是邊界 i 的下一個)
    let j = i + 1;
    // 如果比左邊的小
    while (j > 0 && arr[j] < arr[j - 1]) {
      // 就跟左邊的換順序
      [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      // 然後繼續一路往左比，直到左邊的元素，比自己小為止，就不用換
      j -= 1;
    }
  }
  return arr; // 最後回傳排序好的陣列
}