写在前面
上一次我们学习了排序算法中的选择排序，接下来我们来看一下插入排序。

插入排序是一种原理非常直观的排序算法，具体来讲，插入排序会构造一个有序序列，在这个已排序的有序序列中从后往前扫描，找到未排序元素的相应位置并将其插入有序序列。

落实到具体做法上，给定一个数组arr = [1, 4, 3, 5, 2] ，我们把第一个元素看作已排序的序列，其余的元素看作未排序序列，从头到尾依次扫描，将扫描到的每个元素从后到前与已排序序列的元素进行比对，随后将其插入到有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

如果上面的文字依旧让你迷惑，那我们来看一个例子，这样能更好地解释插入排序地原理。

设数组 arr = [1, 4, 3, 5, 2] ，我们需要将数组中的数字按照从小到大的顺序重新排序。

第一轮排序：

arr[0] = 1为已排序数列，其余元素为未排序数列，我们依次扫描未排序数列。

arr[1] = 4与arr[0] = 1比对，4 > 1，因此放到1之后，此时：

已排序的有序数列变为：arr[0] = 1，arr[1] = 4

未排序数列变为： arr[2] =3，arr[3] = 5， arr[4] =2

第二轮排序：

arr[2] = 3与arr[1] = 4比对（此时即为从后到前与已排序数列比对，因为已排序数列是从小到大的，我们从后到前比对更节约时间），3 < 4，此时再与arr[0]进行比对，3 > 1，因此将3插入到1之后，4之前，此时：

已排序的有序数列变为：arr[0] = 1，arr[1] = 3，arr[2] = 4

未排序数列变为：arr[3] = 5，arr[4] = 2

第三轮排序：

arr[3] = 5 与arr[2] = 4比对， 5 > 4，将5插入到4之后，此时：

已排序的有序数列变为：arr[0] = 1，arr[1] = 3，arr[2] = 4，arr[3] = 5

未排序数列变为：arr[4] = 2

第四轮排序：

arr[4] = 2 与arr[3] = 5比对，2 < 5，因此2要再次与前面的元素arr[2] = 4比对，2 < 4，因此2要再次与前面的元素arr[1] = 3比对，2 < 3，因此2要再次与前面的元素arr[0] = 1比对，2 > 1，因此将2插入到1之后，3之前，此时：

已排序的有序数列变为：arr[0] = 1，arr[1] = 2，arr[2] = 3，arr[3] = 4，arr[4] = 5

未排序数列变为：none

排序算法结束。

插入排序是普通排序中最快的排序，但当数据量较为庞大时，插入排序的效率就变得低下（当然，冒泡、选择排序同样存在这样的缺点），我们看一看插入排序的代码实现：

代码实现：

var insertSort = function(arr){
    const len = arr.length;
    for(let i = 0; i < len; i++){
        let temp = arr[i];
        let j = i - 1;//默认已经排序的元素
        while(j >= 0 && arr[j] > temp){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return arr;
}

在代码中我们让 j = i - 1，保证 j 进入循环时的值为 0 ，即 arr[0] 为假定已排序的有序数列，此时 i = 1 ，arr[0]就可以与arr[1]进行比对。

代码非常简单，如果大家实在不理解，可以套一组数据进去走一遍，相信这样大家就能明白代码的运行逻辑了。

时间复杂度与空间复杂度：

时间复杂度：O(n²)
空间复杂度：O(1)

总结

• 特点
  （1）特点一：稳定
  （2）特点二：最坏情况下比较n*(n-1)/2次，最好情况下比较n-1次;
  （3）特点三：第k次排序后，前k个元素已经是从小到大排好序的

• 时间复杂度与空间复杂度
  时间复杂度：O(n²)
  空间复杂度：O(1)

OK，插入排序就讲到这里，如果有补充，欢迎大家评论区留言，希望你学得开心，see you soon~

这个系列的其他文章：
前端算法之排序（一）---- 冒泡排序
前端算法之排序（二）---- 选择排序