思想

插入排序的代碼實(shí)現(xiàn)雖然沒有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

1. 將待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。
2. 從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）

img

實(shí)現(xiàn)

/*
  插入排序:
  平均時(shí)間復(fù)雜度:O(n2), 最差時(shí)間復(fù)雜度:O(n2), 是穩(wěn)定排序, 需要額外空間O(1) 
 */
function insert1(array) {
  for (let i = 1; i < array.length; i++) {
    let compareIndex = i - 1 //要比較的值的下標(biāo)
    let insertValue = array[i]
    while (compareIndex >= 0 && insertValue < array[compareIndex]) {
      array[compareIndex + 1] = array[compareIndex]
      compareIndex--
    }
    array[compareIndex + 1] = insertValue
  }
}
let array = [101, 34, 119, 1]
insert(array)
console.log(array);