插入排序法（Insertion-sort）

很日常的演算法，但寫成 Code 卻格外抽象。

概念

跟玩撲克牌一樣，先把一張牌抽出來，接著跟前面排好的牌比大小，最後插到正確的位置。

流程圖：

實作

function insertionSort(arr) {
  // 把第一個數字放到排序好的數列
  let sortedNumbers = [arr[0]]
  // 遍歷所有數字（從第二個數字開始）
  for (let i=1; i<arr.length; i++) {
    // 抽出來的數字
    const extractNumber = arr[i]
    // 要插入的位置（初始值為最後面）
    let insertIndex = sortedNumbers.length
    // 遍歷已排序好的數列（由後到前）
    for (let j=sortedNumbers.length-1; j>=0; j--) {
      // 如果抽出來的數字 < 排序好的數字，
      if (extractNumber < arr[j]) {
        // 把要插入的位置往前移一位
        insertIndex -= 1
      }
    }
    // 把抽出來的數字插入到正確位置
    sortedNumbers.splice(insertIndex, 0, extractNumber)
  }
  // 回傳結果
  return sortedNumbers
}
const numbers = [5, 44, 23, 21, 64, 15]
console.log(insertionSort(numbers)) // [ 5, 15, 21, 23, 44, 64 ]

詳細步驟：

extractNumber: 44
compare: 5
insertIndex: 1
sortedNumbers: [ 5, 44 ]

extractNumber: 23
compare: 44
compare: 5
insertIndex: 1
sortedNumbers: [ 5, 23, 44 ]

extractNumber: 21
compare: 44
compare: 23
compare: 5
insertIndex: 1
sortedNumbers: [ 5, 21, 23, 44 ]

extractNumber: 64
compare: 44
compare: 23
compare: 21
compare: 5
insertIndex: 4
sortedNumbers: [ 5, 21, 23, 44, 64 ]

extractNumber: 15
compare: 64
compare: 44
compare: 23
compare: 21
compare: 5
insertIndex: 1
sortedNumbers: [ 5, 15, 21, 23, 44, 64 ]