时间复杂度：O(n^2)
稳定性：稳定
思路：
插入排序我们可以分成两个部分“插入”和“排序”，也许他们两个是同时进行的，先来看这个“插入”是怎么工作的。
给定一个数组nums ：[ 2,3,4,7,9,5]，这个数组并不是完全有序，但是前面的 [2,3,4,7,9]是有序的 , 要让这个数组变成完全有序（非降序），这个就是对这个nums数组进行一次遍历（从后往前遍历），找到第一个比5小的，然后，把这个5插入到这个数的后面，退出循环。来看代码实现：
function insert(nums) {
let len = nums.length
// 取出最后一个数，进行插入
// 最后的数被取出来后，数组的最后一个位置就相当于空出来了
let p = nums[len-1]
for (let i = len - 2; i>=0 ; i--) {
if(nums[i] <= p){
// 找到第一个小于等于p的，把p插入到nums[i]后面，这里的nums[i+1]是空出来的
nums[i+1] = p
return nums
}else{
// 把nums[i]空出来
nums[i+1] = nums[i]
}
}
// 处理边界情况：p是最小的情况，那p就放第一个位置
nums[0] = p
return nums
}
console.log(insert([2,3,4,7,9,5]))
这就是一次"插入"的过程，但是这个插入有个严格的要求，就是前面nums[0]~nums[i-1]必须是有序的，这样我们才能把nums[ i ]放到一个合适的位置，但是如果给我们一个完全无序的数组，又该怎么办呢？
没有条件，我们可以创造条件，当数组只有一个元素的时候，这个数组肯定是有序的，当数组的长度是2时候，比如：[ 2 , 1 ]，就出现了条件，除最后一个外前面的数都有序，我们就可以用上面的方法进行插入，然后这个数组就有序了,[ 1, 2 ]。
这是一个类似递推的过程，我们可以通过一次次插入，使得无序数组的有序部分越来越多，知道整个数组有序。来看代码实现：
function insertSort(nums) {
// 两层for是跑不了的了
for (let i = 1; i < nums.length; i++) {
const p = nums[i];
// nums[0]~nums[i-1]是有序的
for(var j=i-1;j>=0;j--){
if(nums[j]<=p){
nums[j+1] = p
break
}else{
nums[j+1] = nums[j]
}
}
// 处理边界
if(j == -1){
nums[0] = p
}
}
return nums
}
这里要注意的还是和边界情况的处理，也就是我们要插入的数是已有序数组里最小的。两个for的嵌套也就说明了他的时间复杂度为O(n^2)。
来分析一下插入排序的优缺点插入排序的在数组部分有序的情况下下是很快的，比如数组[ 2,3,4,7,9,5]，对于这个数组，内层for循环基本都是进去一下就break出来，只有到最后一个数字5的时候，才会在内层for循环里待上几轮，涉及到的数据交换也都在数字5的时候才发生。
插入排序对于[5,4,3,2,1,0]这种情况，就会很慢，最后的0要从最后一路移动到最前面。最前面的5要从前面一路移动到最后面。所以我们要把小的数尽量排到前面去，大的数尽量放到后面去。这就是希尔排序解决。
希尔排序下次再说
