插入排序

一、原理解析

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 把取出的元素放到已排序的元素中间的合适位置
4. 重复步骤2\~3

就像排队一样，依次每次挑一个同学，把该同学“插入”到已经排好的部分队伍里。

二、范例演示

以下表格里，红色表示选中的待排序的数字，蓝色表示最终排好的数字。

第一轮：对于第一个元素(红色)，变成已排序元素(蓝色)

第二轮：对于第二个元素，和已排序元素(蓝色数字)比较，插入到已排序元素中合适的位置（8放到10前面，之后都变成已排序元素）

第三轮：对于第三个元素，和已排序元素(蓝色数字)比较，插入到已排序元素中合适的位置（9放到8和10中间，之后变成已排序元素）

...

三、实现方式

插入法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)

四、效率测试

下面我们测试排序性能

let arr = randomArr(10000, 100) 
console.time('sectionSort')
insertionSort(arr)
console.timeEnd('sectionSort')
 
 
function randomArr( arrLen = 100, maxValue = 1000 ) {
  let arr = []
  for(let i = 0; i < arrLen; i++) {
    arr[i] = Math.floor((maxValue+1)*Math.random())
  }
  return arr
}
 
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
      }
    }
  }
}

经浏览器测试，数组长度增加10倍，排序时间约增加100倍。

五、复杂度分析

时间复杂度为 O(n\^2) ，和上面的测试基本一致。

饥人谷一直致力于培养有灵魂的编程者，打造专业有爱的国内前端技术圈子。如造梦师一般帮助近千名不甘寂寞的追梦人把编程梦变为现实，他们以饥人谷为起点，足迹遍布包括facebook、阿里巴巴、百度、网易、京东、今日头条、大众美团、饿了么、ofo在内的国内外大小企业。 了解培训课程：加微信 xiedaimala03，官网:https://jirengu.com

本文作者：饥人谷若愚老师