原理
直接插入排序的基本思想：每次将一个待排序的记录，按其keyword的大小插入到前面已经排好的子序列中的适当位置，直到所有记录插入完毕为止。
实现
假设数组为A[0...n-1]，
1.初始时，A[0]自成1个有序区,无序区为A[1....n-1]。令i = 1；
2.将A[i]并入当前的有序区A[0...i-1]中形成A[0...i]的有序区间；
3.i++并反复第二步直到i == n-1，至此排序完毕。
效率分析
稳定
空间复杂度O(1)
时间复杂度O(n2)
最差情况：反序。须要移动n*(n-1)/2个元素
最好情况：正序，不须要移动元素
数组已是排序或者接近顺序。插入排序的效率最好的情况是O(n)，最坏的情况执行时间和平均情况执行时间均为O(n2)
通常插入排序呈现出二次排序算法中的最佳性能。
JavaScript
let arr1 = [2, 8, 3, 89, 67, 45]
function insertSort(arr){
let newArr = []
if(Array.isArray(arr) && arr.length>0){
newArr = newArr.concat(arr)
for(let i=0; i < arr.length; i++){
let j = i
let current = arr[i]
while(j>0 && current < newArr[j-1]){
newArr[j] = newArr[j-1]
j--
}
newArr[j] = current
}
}
return newArr
}
console.log('reArr===>', insertSort(arr1))
