插入排序

之前我们学习了冒泡排序，选择排序，今天我们再来讲一个时间复杂度同样为O(n^2)的排序算法，准确的说它的平均复杂度是O(n^2/4),理论上是要优于前面所说的两种排序的（在指数变化面向，系数的变化显得很渺小😂），但是由于插入排序的这种思路是非常重要的，是三个O(n^2)里面必学的一个，就连希尔排序(第一个突破n^2的排序)，也是插入排序的一种变形。

思路

我们上学那会最烦的就是去操场排队做操，由于第一次去操场，大家是按自己喜好排在一起的，高的高，矮的矮，这个时候老师会以第一个同学为基准往后面挑矮个的同学往第一个同学前面插，直到所有人从低到高排好，仔细想想这个插入的过程，这个是插入排序的核心，很多人学了插入排序和选择排序会傻傻分不清楚，就是没有彻底理解这个插入的过程，看下面这个动图，再联想一下操场排队被老师揪出来放到最前面😂。

我们把数组分为了有序区和无序区，默认第一个数就是有序区，第一次插入的时候会选择第二个数，也就是紧挨着有序区的第一个数，这个时候我们做判断比较这个数是否小于有序区的最后一个数，如果小于就把有序区最后一个数往后面挪，然后比较倒数第二个数，如果还是小于就继续往后挪，如果大于就把这个数放置到倒数第二个数的下一个位置，也就是倒数第一个数原本的位置，这个时候有序区就扩大了，之后重复上面的操作直到整个数组都是有序区，排序结束。这个插入的过程一定要理解透，不然代码无从下手，多看几次上面的动图。

代码

/**
 * 插入排序
 * @param {number[]} arr -需要排序的数组
 */
function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const currentElement = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > currentElement) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = currentElement;
  }
}

使用了两个循环，第一个循环为一个for循环，从第二个元素开始遍历所有的元素，每次都会选择arr[i]作为要插入的元素把它保存起来，内部使用一个while循环，一直找到有序区的某个元素比待插入元素小的元素，之后退出循环把待插入元素赋值给这个元素的后面一个位置，由于后面一个位置原本的数已经往后面移动了，这个位置的数是多余的，直接赋值即可。

总结

插入排序理解起来没有冒泡和选择那么容易，这里面有一个插入的过程，重点就是这个插入过程，如果没有理解根本就无从下手，插入排序是希尔排序的基础，理解插入排序之后学习希尔排序会轻松很多，插入排序是这三个O(n^2)里面最重要的一个排序，一定要学会。