目录

插入排序

原理解析

实现方式

插入法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
      }
    }
  }
}
​
let 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
  }
}
​
​
let 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
      }
    }
  }
}

经浏览器测试,对于长度为10000的数组,排序约需要76ms(一次样本), 对于长度为100000的数组,排序约需要 8314ms(一次样本)。可以看出,数组长度增加10倍,排序时间约增加100倍。

复杂度分析

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