一、原理解析

1. 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 把取出的元素放到已排序的元素中間的合適位置
4. 重復(fù)步驟2~3

就像排隊(duì)一樣，依次每次挑一個(gè)同學(xué)，把該同學(xué)“插入”到已經(jīng)排好的部分隊(duì)伍里。

二、范例演示

以下表格里，紅色表示選中的待排序的數(shù)字，藍(lán)色表示最終排好的數(shù)字。

第一輪：對(duì)于第一個(gè)元素(紅色)，變成已排序元素(藍(lán)色)

第二輪：對(duì)于第二個(gè)元素，和已排序元素(藍(lán)色數(shù)字)比較，插入到已排序元素中合適的位置（8放到10前面，之后都變成已排序元素）

第三輪：對(duì)于第三個(gè)元素，和已排序元素(藍(lán)色數(shù)字)比較，插入到已排序元素中合適的位置（9放到8和10中間，之后變成已排序元素）

...

三、實(shí)現(xiàn)方式

插入法JS 版

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    for(let j = 0; j < i; j++) {
      if(arr[i] < arr[j]) {
        arr.splice(j, 0, arr[i])
        arr.splice(i+1, 1)
        break
      }
      console.log(arr)
    }
  }
}

var arr = [10, 34, 21, 47, 3, 28]
insertionSort(arr)
console.log(arr)

插入法普通版

function insertionSort(arr) {
  for(var i = 1; i < arr.length; i++) {
    var temp = arr[i]
    for(var j = i; j > 0 && arr[j-1] > temp; j--) {
      arr[j] = arr[j-1]
    }
    arr[j] = temp
  }
}

var arr = [10, 34, 21, 47, 3, 28]
insertionSort(arr)
console.log(arr)

復(fù)雜度分析

時(shí)間復(fù)雜度為 O(n^2)。