老规矩，还是先回顾下排序算法的种类

本篇文章准备聊聊其中的 插入排序，废话不多说，开搞！

ppx2.jpg

插入排序的简述

插入排序是一种简单直观的排序算法，性能上并不是很好，平均时间复杂度为 **O(n^2)**，但是空间复杂度只有 **O(1)**，且是一种 稳定的 算法

算法的稳定性指的是如果在某一无序集合中a=b，且a在b前面，经过排序后，如果a依旧在b前面，那么可以认为使用的排序算法是稳定的，反之，就是不稳定的

由于时间复杂度较高，所以不建议在实际开发中使用，但用来作为算法入门很合适

插入排序的实现过程

其实现的过程可以类比为打扑克时，对手里的牌进行整理的过程，以升序为例，实现过程如下

  1. 以第一张拿到的牌作为 已排序的 牌组
  2. 每拿到新的一张牌，就 从后向前 扫描已排序的牌组
  3. 如果发现新的牌比当前扫描到的牌小，那么就把当前扫描到的牌 向后移一位
  4. 重复3步骤，直到扫描到的牌 小于或等于 新的牌，此时就将新的牌插入到扫描到的牌 后面
  5. 重复2～4步骤，直到排序完所有拿到的牌

下面给出代码示例

1
2
3
4
5
6
7
8
9
10
11
12
function insertSort(arr){
    for(let i = 1;i<arr.length;i++){
        let current = arr[i]
        let j = i - 1
        while(j >= 0 && arr[j] > current){
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = current
    }
    return arr
}

通过代码示例，我们可以知道该算法实现的关键点有如下几点

  1. 确定外循环轮数，轮数为 集合长度-1
  2. 以外循环遍历到的元素为基准，然后从后向前遍历已排序的集合
  3. 如果遍历到的已排序序列的元素 大于 基准元素，那么就将遍历到的元素 向后 移动一位
  4. 重复3步骤，直到遍历完第一个元素或小于等于基准元素，然后将基准元素插入到对应元素 后面
  5. 重复2～4，直至整个集合有序

结语

插入排序的理解与掌握是十分容易的，只要会打扑克，就可以很自然地理解其中的精髓，好啦，就写到这里啦，over！