插入排序法是将阵列中未排序的元素，逐一与排序好的资料作比较。它的时间复杂度是 (O(n^2))。

一、步骤观察

• 标记第一个元素作为已排序的部分
• 遍历未排序的部分，作以下动作
  • 取第一个未排序的元素
  • 与已排序的元素作比较
    • 移动出正确位置，然後插入未排序的元素
  • 向右移动标记

二、实际操作

使用哪种资料结构：Array

• 将第一个元素标记为已排序
• 遍历未排序的元素
  • 取第一个未排序元素
  • 遍历已排序的元素 (从後到前)
    • 如果已排序元素 > 未排序元素
      • 已排序元素向右移
    • 否则插入未排序的元素 (原位置或空格)

逻辑：

  arr <- an unsorted array of integers
  let len be the length of arr
  
  for i (1 t0 len-1) do
    key = arr[i]
    j = i-1
    while j>=0 && key<arr[j]
      arr[j+1] = arr[j]
      j--
    end while
    arr[j+1] = key
  end for

程序码实作：

debugger
function insertionSort(arr) {

  for (let i = 1; i < arr.length; i++) {
    let key = arr[i] // 第一个未排序的元素
    let j = i-1 // 已排序元素的控制器
    console.log(key)

    while (j>=0 && key<arr[j]) { // 移动出正确位置
      arr[j+1] = arr[j]
      console.log(arr)
      j--
    }
    arr[j+1] = key // 插入未排序元素
    console.log(arr)
  }
}

insertionSort([8, 9, 2, 5, 1])

三、时间复杂度 Big O

• 总共比较了 1+2+3+…+(n-1)
• 也就是 n*(n-1)/2
• 时间复杂度会忽略系数，所以为 O(n^2)