插入排序是什么

插入排序（Insertion Sort），一般也被称为直接插入排序。

对于少量元素的排序，它是一个有效、简单的算法。

其主要的实现思想是将数据按照一定的顺序一个一个地插入到有序的表中，最终得到的序列就是已经排序好的数据。

插入排序的工作方式像许多人排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置，该正确位置需要从右到左将它与已在手中的每张牌进行比较。

例如一个无序数组 3、1、7、5、2、4、9、6，将其升序的结果则如下：

一开始有序表中无数据，直接插入3

从第二个数开始，插入一个元素1，然后和有序表中记录3比较，1<3，所以插入到记录 3 的左侧

向有序表插入记录 7 时，同时有序表中记录 3 进行比较，3<7，所以插入到记录 3 的右侧

向有序表中插入记录 5 时，同时有序表中记录 7 进行比较，5<7，同时 5>3，所以插入到 3 和 7 中间

照此规律，依次将无序表中的记录 4，9 和 6插入到有序表中

如何实现

代码实现

function insertionSort6(array) {
    const length = array.length
    let element, flag
    for (let index = 0; index < length; index++) {
        flag = index - 1
        element = array[index];
        while (flag>=0 && array[flag]>element) {
            array[flag+1] = array[flag]
            flag--
        }
        array[flag+1] = element
    }
    return array
}

复杂度

时间复杂度：最好是O(n)，最坏是O(n^2)

扩展到n：O(n-1) => O(n)

扩展到n：O(（0+n-1）*n/2) => O(n²)

空间复杂度

O(1)：属于稳定算法（相同的数字在排序前和排序后的相对位置是不变的）

应用场景

插入排序时间复杂度是 O(n2)，适用于数据量不大，算法稳定性要求高，且数据局部或整体有序的数列排序

---

欢迎关注我：

欢迎关注