前言：直接插入排序是一种简单直观的插入排序法。其基本思想是将数组分成有序区和无序区，不断的从无序区拿出一个元素插入到有序区中的正确位置中，直至整个数组变得有序。

---

一、插入排序的思想

我们以扑克牌举例，摸牌之前你手中的牌一定是按照一定的顺序排放，当你摸到一张牌，一定是将它按顺序插入到你手中有序的牌列当中。

如下图所示：排列升序数组 [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

二、插入排序的工作原理

①初始状态：我们认为数组的第一个元素是有序的

②取新元素：取第二个元素作为待插入的元素，将其储存在tmp中

③比较和移动：将tmp与它前一个元素比较

如果tmp<前一个元素，就把前一个元素向后挪动一位，给tmp腾出一个空位

继续向左比较，直到找到一个比tmp小的元素，

④插入：再将tmp插入到刚才腾出的空位当中

⑤重复：在继续去数组中的下一个元素，继续上述步骤

以一个简单的数组为例：排升序[5,3,8,2,1]

①初始状态：[5,3,8,2,1]

tmp=3;tmp<5,将5向后挪动一位，变成[5,5,8,2,1]

此时5是空位，将tmp插入到空位中[3,5,8,2,1]

②继续下一个元素8：[3,5,8,2,1]

tmp=8;tmp>5,说明前面的序列里已经没有比8在大的（只有前一个元素比当前元素大，才能往前插入），继续下一个元素；

③tmp=2;tmp<8,将8向后挪动一位，变成[3,5,8,8,1],tmp<5,将5向后挪动一位,[3,5,5,8,1]

tmp<3,将3向后挪动一位，变成[3,3,5,8,1],将tmp插入到3位置上，变成[2,3,5,8,1]

④tmp=1,重复上述步骤,最后数组是[1,2,3,5,8]

三、C语言代码实现直接插入

#include <stdio.h>
void InsertSort(int*a,int n)
{
    for(int i=1;i<n;i++)
    {
        int end=i-1;
        int tmp=a[i];
        while(end>=0)
        {
            if(a[end]>tmp)
            {
                a[end+1]=a[end];
                end--;
            }
            else
                break;
        }
        a[end+1]=tmp;
    }
}

❗注意关键点：while 循环这里有两个退出条件

1. 当end的值<0,即end=-1，退出循环，此时让a[end+1]=a[0]=tmp;
2. 因为break退出，当a[end]<=tmp

四、插入排序的时间复杂度

插入排序的时间复杂度与初始数据集的排列顺序关联，初始数据集有序，插入排序性能最好。

最优情况：当数据集有序，插入排序只会遍历一遍数组，不会发生插入和移动，时间复杂度是O(N)

最坏情况：数据集完全逆序，第一个元素需要和前0个比，第二个需要和前1个比，第三个和前2个比：

T（n）= 0 + 1 + 2 + ... ... + n-1 = (n-1) * n /2

总体的时间复杂度是O（）

五、插入排序的缺陷

1.数据量大时，效率极低

由于插入排序的时间复杂度是O（），这就意味着，如果数据量增加10倍，消耗的时间可能会增加100倍。

2.数据移动非常频繁

我们在刚才的例子中发现，每把一个小数挪到前面，就要把前面排好的数列都要挪动一遍

在计算机中，“写入”内存的操作比单纯的“比较”操作要慢，如果你排序的是复杂的对象（比如一个很大的结构体），频繁地搬运它们会消耗大量的性能。

3.对逆序数据非常敏感

我们在刚才举过的例子中发现，如果排升序，而最小的数在最后，那么这个最小的 要像蜗牛一样一点点经过比较挪动才能到前面来，缺乏“跳跃性”。

---

既然插入排序的痛点是‘一次只能挪一步’，那有没有办法让数据一次移动n步？

这就是我们下节要讲的十大排序插入排序——希尔（SHELL）排序，欲知后事如何，且听下回分解💛🧡💙💜🤎

看到这里啦，就请点赞关注加收藏，一键三连走起🚀