文章目录

• • 插入排序
  • • 1 动画
    • 2 思想
    • 3 解法
    • 4 分析
    • • • 时间复杂度
        • 空间复杂度
        • 稳定性
    • 参考资料：

插入排序

1 动画

2 思想

一般人打扑克牌，整理牌的时候，都是按牌的大小（从小到大或者从大到小）整理牌的，那每摸一张新牌，就扫描自己的牌，把新牌插入到相应的位置。

插入排序的工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3 解法

var insertionSort = function(array) {
    var len = array.length;
    if(len <= 1) return;
    var preIndex, current;

    for (var i = 1; i < len; i++) {
        preIndex = i - 1; // 前一个元素的下标
        current = array[i]; // 当前元素

        while (preIndex >= 0 && current < array[preIndex]) {
            array[preIndex+1] = array[preIndex]; // 将元素往后挪一位
            preIndex--; // 下标前移
        }

        if (preIndex+1 != i) { // 如果相等，证明该数比已排序的序列都大，就不需要进行赋值操作了
            array[preIndex+1] = current; // 将当前元素插入到已排序序列中
        }
    }

    return array;
}

4 分析

时间复杂度

• 最佳情况：O(n)

• 最差情况：O(n²)

• 平均情况：O(n²)

空间复杂度

O(1)

稳定性

稳定。

参考资料：

• JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

• awesome-coding-js