学号：20021211189 姓名：赵治伟
【嵌牛导读】插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
【嵌牛鼻子】插入排序算法
【嵌牛正文】
1.算法原理
这是一个无序数列：1、5、4、2、6、3，我们要将它按从小到大排序。按照插入排序的思想，我们先指定有序序列，再将无序序列插入有序序列的相应位置
将第一个元素1作为有序数据，此时有序区只有一个元素
第一轮，让元素5和有序区依次比较，1<5，无需交换
此时有序区有1、5两个元素
第二轮，让元素4和有序区依次比较，5>4，需要交换
1<4，1与4不需要交换
此时有序区有1、4、5三个元素
第三轮结束后，如下所示
第四轮结束后，如下所示
第五轮结束后，如下所示
至此所有的元素都是有序的
2.算法优化
在第三轮中，2先跟5交换，再跟4交换，进行了多次交换，在数组数量大的时候，交换的次数会更多
实际上，我们可以先将2暂存起来，把有序区的元素从左向右复制，优化如下：
第一步，将2暂存起来
第二步，2和5比较，2<5，5移到下一个位置
第三步，2和4比较，2<4，4移到下一个位置
第四步，2和1比较，2>1，1不需要移动，将暂存的2复制到1的下一个位置
3.算法实现
function sort(arr) {
let length = arr.length;
for (let i = 1; i < length; i++) {
let insertValue = arr[i];
let j = i - 1;
for (; j >= 0 & insertValue < arr[j]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = insertValue;
}
}
let arr = [1, 5, 4, 2, 6, 3];
sort(arr);
console.log(arr);
插入排序算法要进行n-1轮，每一轮对比的元素最坏的情况依次是1, 2, 3 … n-1，所以时间复杂度是O(N^2)
插入排序算法排序过程中需要一个临时变量存储插入元素，所需要的额外空间为1，因此空间复杂度为O(1)
插入排序算法在排序过程中，无序数列插入到有序区的过程中，不会改变相同元素的前后顺序，是一种稳定排序算法
