【初阶数据结构和算法】八大排序算法之插入排序（直接插入排序、希尔排序及其对比）
文章目录
一、常见排序算法分类
常见的排序算法有八种，我们简单盘点一下
- 插入排序：直接插入排序、希尔排序
- 选择排序：直接选择排序、堆排序
- 交换排序：冒泡排序、快排
- 希尔排序
- 计数排序
以上就是我们常用的八大排序算法，我们会在后面的排序算法部分为大家一一介绍，今天我们要介绍的就是插入排序这一大类排序（更新）
一、直接插入排序
我们先来简单地介绍一下直接插入排序的思想：
直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤小逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列，我们举一个简单的例子，如图：
在我们玩扑克牌时，拿到牌后首先就是对牌进行排序，我们会将已经排好序的牌放在左手边，然后右边就是我们等待排序的牌
随后我们会将右边没有排好序的牌依次去插入到已经有序的牌中，如上图，2,4,5,10就是一组已经排好序的牌，而7我们就可以看作是我们打牌时放在右边的还未排序的牌，我们想把7排好序，就只需要将7插入到5和10的中间，其它牌不变
这也正是我们直接插入排序的算法思想，将所有的数据分成两部分，左边就是已经排好序的数据，右边则是待排序数据，就是我们上面扑克牌的思想，随后我们将右边待排序的数一个一个插入到有序的数据中，直到最后一个数据插入完成，所有数据也就有序了
现在问题的关键就是，在最开始时我们所有的数据都是乱序，怎么才能将它划分成左右两部分，实际上很简单，只要我们把第一个数据看作一个有序的序列即可，这样左右两部分就被划分出来了，如图：
这样我们就将最开始的数据划分成了两部分，左边只有一个数据，可以看作是有序的，右边是乱序的、待排序的数据，接下来我们要做的就是如何将右边一个一个的元素依次插入到左边的有序序列中
这也是我们直接插入排序的重点，上面我们讲解了直接插入排序的原理，接下来我们就开始介绍直接插入排序的具体实现，我们以升序为例讲解
首先我们可以创建一个变量end作为左边有序序列中的最后一个数据，在最开始时，end就在上图8这个位置上，因为8就是有序的序列的最后一个数据，随后我们要做的就是将3插入到这个有序序列
方法就是，记录下来end+1位置的数据，因为end是左边有序的序列的最后一个数据，那么end+1自然就是右边待排序序列的第一个数据，我们要将end+1这个位置的数据插入到左边的有序序列中，首先就是将它用变量tmp记录下来，它就是我们要往左边有效序列中插入的数据
接下来我们就开始比较end位置的数据和tmp这个数据，看看end位置的数据是否比tmp更大，如果更大，说明我们的tmp要往end位置的左边插入数据，于是我们就可以让end位置的数据往后挪动一下，如图：
此时就可以看到，我们成功将右边的一个数据3插入到了左边的有序序列中，现在这些数据重新被我用绿色框划分成了两部分，左边是新的有序序列，而右边而是新的待排序数据，接下来我们要继续上面我们画出的操作
这里我就不再画图演示了，我们这时候要再来讨论一个问题，是不是每次只需要end位置的数据和tmp比较一次就够了，还是说整个过程是循环进行的，很明显这个过程是循环进行的，那么为什么我们刚刚只比较了一次呢？
因为我们刚刚的有序序列只有一个元素，自然就只需要比较一次了，如果有序序列中有多个元素，那么tmp就要一直去找比它小的元素，如果碰到比它大的数据就让它往后挪动，也可以参考我们上面的图理解
如果一直遇到的都是比tmp大的数据，那么end就会一直- -，到最后就跟上图一样，end直接越界了，我们就需要直接结束循环，将tmp放到end+1的位置上
然后根据上面我们说的思路，我们也会发现一个规律，就是第一次的end指向第一个元素，第二次的end指向第二个元素，因为经过第一次的排序，将右边的一个待排序数据成功插入到了左边，所以我们第二次的end就指向第二个元素(end就是有序序列的最后一个数据，不要忘记了)
那么相当于就是这个end会从第一个数据开始，遍历所有数据，也就是会遍历我们要排序的数组，这里我们就需要一个for循环完成
然后每一个end的比较又是一个循环，循环条件就是end >= 0，只要end没有越界，并且tmp的值比end位置的值小，就会一直将大的数据往后挪，end要- -，直到end越界，再将tmp放到end+1的位置
当然，并不是所有情况都会越界，如果中途碰到了比tmp小的值，那么就直接退出循环，也是将tmp放到end+1的位置，可以根据上面的例子自己画图模拟一下
那么以上就是直接插入排序的所有算法思路以及实现方法，接着我们就按照刚刚将的内容将直接插入排序写出来，如下：
//直接插入排序voidInsertSort(int* arr,int n){for(int i =0; i < n -1; i++){int end = i;int tmp = arr[end +1];while(end >=0){if(arr[end]> tmp){ arr[end +1]= arr[end]; end--;}else{break;}} arr[end +1]= tmp;}}这里我们要注意的是i的范围，i也就是end，它到n-2位置时，就会跟n-1位置进行比较，所以i只需要取0到n-2即可，不明白的可以自己试试写成i < n，然后自己调试看看，会发现当i等于n-1时，会将n-1位置的数据和n位置的数据作比较，会越界
那么说完最后的注意事项之后，我们拿它来排序试试，如图：
可以看到直接插入排序成功帮我们完成了排序任务，接下来我们来分析一下直接插入排序的时间复杂度，由于它有两层循环，外层循环一直都是n，内层循环最坏情况下也是n，所以最后直接插入排序的时间复杂度大致为O(N^2)
二、希尔排序
希尔排序是直接插入排序的优化排序，也属于插入排序，我们上面学习的直接插入排序的时间复杂度为O(N^2)，并不理想，至于原因我们可以文末测试给大家看看
首先我们先来分析分析为什么直接插入排序很慢，其中一个很重要的原因就是，在我们将右边待排序的数据插入左边排好序的数据时，很可能出现右边的数据出现较大或较小的数据
我们就以升序为例，如果右边的数据都是较小的数据，那么在往左边插入数据的时候，就会造成左边数据的多次挪动，导致性能下降，除非数据源本来就接近或稍微有序，那么我们数据的挪动就变少了，一下就能将数据插入到左边，效率就高了
哎~，确实有道理，如果我们在执行直接插入排序前，让数组接近有序，就会让排序的速度快很多，这就是希尔排序优化的基本思路，那么它是怎么做到的呢？我们一起来学习一下
希尔排序的思路就是通过“分组”排序进行优化，通过分组对数据源进行预处理，就是分别将每组的数据排成有序，这样将能将数据从杂乱无章，变得接近或稍微有序，然后再去进行一次直接插入排序，就可以让数据有序
首先我们对数组进行分组，分组不是挨着的数据为一组，而是跳着跳着进行分组，我们可以简单画个图，如下：
在上图中，我们将数据分成了两组，红色为一组，绿色为一组，每个组元素之间的距离为2，在分组时并没有选择挨着的数据为一组，这是为什么呢？
如果我们将挨着的数据划为一组，那么各组排完序之后一定会出现这样的问题，如图：
这样挨着区域划分，我们排序后，也只是局部有序，但是我们要从全局去看呀，我们希望经过预排序后，也就是每个组排序之后，整个数组看起来接近有序，上面的划分可以一下就看出来，局部是有序的，但是从整体的角度看起来，这些数据还是杂乱无章的
那么如果我们分开划分呢？我们来看看分开划分的效果，如图：
首先我们从肉眼直接进行观察，我们发现这样分组排序后，居然真的能让数据往整体有序进行挪动，这样的原理是什么呢？
这也不难想到，就是因为每组的数据都是分开的，但是组与组之间是相邻的，那么每组在排序时，会将自己较小的数据往前放，由因为组与组之间相邻，最后就能将每组最小的数据相邻，并且出现在所有数据的前面
又由于每组在排序时，会将自己较大的数据往后放，并且组与组之间相邻，那么就能让每组中较大的数据相邻，并且出现在所有数据的后面，这样综合下来，就能实现简单的对所有数据进行预排序，让整体看起来接近有序
如果实在不理解也没关系，至少从我们画的图上面来看，很容易发现将分开的数据划分在一起更好，知道这一点就好了，关键在于我们要知道如何实现预排序
这里我们就不卖关子了，直接开始介绍如何实现预排序，预排序分成很多步，因为如果数据量很大，那么我们无论如何分组，最后都很难让数组看起来有序，所以预排序本身会进行多次，也就是会分多次组进行排序
那么每一次分组我们怎么划分呢？划分成多少组呢？经过一些大佬的研究发现，每次让gap除3+1就能将组分得更加合理，gap最初就是所有数据的个数，比如上图中一共有5个数据，那么它/3+1之后就变成了2，正好是两组，也可以说是每组中各个数据之间的间隔
这里稍微提一下，分成多少组，那么每个数据就会间隔多少，这个是常识性的知识，就简单提一下，分多少组意味着每组间隔多少，注意是间隔，不是数据个数
那么如果一下有1万条数据呢？gap/3+1后就是3千多，我们要将数据划分成3千多组，每组之间的元素间隔3千多的距离，每组则是有3个数据
经过一次这样的分组排序，并不能保证整个数组看起来有序，我们要对它排序后的结果再次进行分组，继续让gap/3+1进行分组，然后对每组进行排序
直到最后一步gap/3+1后为1了，此时每组之间的间隔为1，相当于没有分组，此时会进行一次最终的排序，将所有数据排成有序，这样我们的希尔排序就完成了
最后我们总结一下希尔排序的思路，定义一个gap，默认为数组元素大小，让它循环地去分组，每次分组就是让gap/3+1，每分一次组就对每组进行一次排序，每组的排序就和直接插入排序的思路差不多，这样循环下去，直到gap == 1
因为gap == 1后gap/3+1就为1了，然后我们会发现这时候一直/3+1会造成死循环，所以gap的循环条件为gap > 1，代码如下：
//希尔排序voidShellSort(int* arr,int n){int gap = n;while(gap >1){ gap = gap /3+1;for(int i =0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while(end >=0){if(arr[end]> tmp){ arr[end + gap]= arr[end]; end -= gap;}else{break;}} arr[end + gap]= tmp;}}}我们来使用希尔排序简单排序一下一个数组，看看是否无误，如下：
我们来简单谈谈希尔排序的时间复杂度，它看起来和直接插入排序很像，但是外层还有一个循环，难道是O(N^3)吗，比插入排序还糟糕
其实不是，它是直接插入排序的优化，自然会比直接插入排序快，只是它套了三层循环比较具有迷惑性，希尔排序的时间复杂度很难直接计算，因为它的排序会根据gap的改变而改变，我们来看看《数据结构(C语⾔版)》—严蔚敏老师书中给出的时间复杂度为：
在书中也明确谈到了希尔排序的时间复杂度很难计算，但是我们也要知道它的时间复杂度大致为O(N^1.3)，比起直接插入排序要快很多
但是其实很多人包括我，都不对这个有着三层循环的排序算法抱有期待，看起来根本差距不了多少，所以我们接下来进入测试阶段，一起来感受希尔排序带来的震撼
三、直接插入排序和希尔排序性能对比
首先我们来对比一下直接插入排序和希尔排序的时间复杂度，如下：
- 直接插入排序：O(N ^ 2)
- 希尔排序：O(N ^ 1.3)
看起来相差不远，接着我们来写一个测试程序来生成10万条数据，分别用它们进行排序，测试程序如下：
voidTestOP(){srand((unsignedint)time(NULL));constint N =100000;int* a1 =(int*)malloc(sizeof(int)* N);int* a2 =(int*)malloc(sizeof(int)* N);for(int i =0; i < N;++i){ a1[i]=rand(); a2[i]= a1[i];}int begin1 =clock();InsertSort(a1, N);int end1 =clock();int begin2 =clock();ShellSort(a2, N);int end2 =clock();printf("InsertSort:%d\n毫秒", end1 - begin1);printf("ShellSort:%d\n毫秒", end2 - begin2);free(a1);free(a2);}接着我们在主函数中调用这个函数，注意，要将VS调整到Release版本，这样才能测试出它们真正的性能，运行结果如下：
可以看到在同一台设备上，排序10万条数据直接插入排序耗时598毫秒，也就是差不多0.6秒，而希尔排序只有0.006秒，如果你觉得，它们两个的差距也不远啊，反正都等不了多久，那是因为我们排序的数据量还是太小了
我们将测试程序中的N改为100万，让程序生成100万个随机数用来排序，如下：
constint N =1000000;我们重新运行程序，看看程序的结果：
这时我们惊讶地发现，排序100个随机数时，直接插入排序所耗的时间增长了100倍，来到了60秒，而希尔排序的时间只是增长了10倍，还是在0.1秒之内排好了100万个随机数
60秒和0.1秒，相信大家都清楚之间的差距，但是如果我们要排序的数据更多，它们之间的差距只会更大，具体原因就是O(N^2)这个时间复杂度实在太差了，每增长10倍数据量，时间会增长差不多100倍
所以我们说希尔排序已经是非常优秀的排序算法了，和其余几个O(N * logN)的排序算法差不多，也让我们见识到了直接插入排序和希尔排序的差距，一个三层循环的排序算法如此快，有没有震惊你呢？
那么今天的插入排序的介绍就到这里啦，有什么问题欢迎私信我，后面我们继续讲解排序算法，感谢观看
bye~
