在说插入排序之前我想和大家说一下，算法的一些基本概念，
如下：
- 时间复杂度指的是一个算法执行所耗费的时间
- 空间复杂度指运行完一个程序所需内存的大小
- 稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
- 不稳定指，如果a=b，a在b的前面，排序后可能会交换位置
插入排序基本思想
从数组的第二项开始考察，把数组的第二项和第一项做比较如果第二项比第一项大就不管，如果比第一项小就交换位置，接着考察第三项，先将第三和第二比较，如果第三比第二大退出循环，如果第三比第二小交换位置继续和第一项比较，大则退出当前循环，小则交换位置。依次类推。。
可以将其想象为打扑克时的理牌方式。
代码如下：
/**
* 插入排序方法
* @param {* 需要排序的数组} arr
* @param {* 数组的长度} n
*/
insertionSort = (arr, n) => {
for (let i = 1; i < n; i++) {
//寻找arr[i]合适的插入位置,所以需要遍历之前比较过的数据
for (let j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
//变量结构赋值 测试10000数据的时候预计多消耗.3s的性能
// [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
var temp = arr[j - 1]
arr[j - 1] = arr[j]
arr[j] = temp
} else {
break
}
}
}
}
代码上没有什么难点，就是给考察对象选择合适的位置，一遍一遍去交换位置，找到合适的位置以后退出当前循环，按照我们的想法能退出循环应该比选择排序要快吧，根据实际测试，比选择排序要慢一点，应该是交换操作过多造成的。
根据想法优化，代码如下：
//插入排序优化写法,将比较后互换位置 变成寻找位置并赋值
//对于插入排序在排序一个近乎有序的数组时效率可以达到O(n)级
this.insertionSort1 = (arr, n) => {
for (let i = 1; i < n; i++) {
//寻找arr[i]合适的插入位置,所以需要遍历之前比较过的数据
let e = arr[i];
let j
for (j = i; j > 0 && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1]
}
arr[j] = e
}
}
以上代码实际测试比选择排序要稍微快一点，插入排序是一个可以达到O(n)级别的算法，应用比较广泛。基本大多数的高级算法，底层优化都可以用插入排序。
以上都是个人理解如有不对之处还望指正交流！
