插入和希尔

• 插入排序
• • 时间和空间复杂度分析
• 希尔排序
• • 时间和空间复杂度分析

本篇文章将插入排序和希尔排序放在一起讲解，是因为后者可以说是前者的排序方式的一种优化，思路上大体一样，插入和希尔在整个排序的大章节中，算是比较简单的，与冒泡排序一样，相信大家理解起来也不会那么的困难

插入排序

在排序这一章节，很有意思的是，各种排序可以根据它们的名字猜出大概的思路，就比如插入排序，冒泡排序，快速排序等，从名字就可以看出各种排序的特点来。

插入排序的思路（文字）
我们先以一组比较短的数据来讲解一下插入排序的总体思路。

以数组【7，6，5，2，3，1】为例
我们将第二个数字 6 标记为end 将数组的第一个数字到end之间的所有数字看作成一个小的数组，即【7， 6】。 将end (6) 与end-1 (7) 进行比较，大小的向后移动，移动完之后，就是【6， 7】。 然后将end向后移动一位，到达数字 5 。此时数组中的数据为【6，7，5，2，3，1】

然后将【6，7，5】看作一个小数组进行排序，首先end (5) 和end-1 (7) 进行比较，大的向后移动，数组变成【6，5，7】 然后end向前移动一位，到达5的位置，然后end (5) 和 end-1 (6) 进行比较，大的数向后移动，数组变成【5，6，7】

此时数组【5，6，7，2，3，1】
然后end再从原来的位置向后移动一位，到达2的位置，然后重复的进行上述的比较，直到end走到数组的最后一个数子。

上述就是插入排序思路的文字解释了，当热对初学者来说是晦涩难懂，不过没关系，下面就用动图给大家演示一下这个过程，之后大家再结合下面的代码看一遍，保证药到病除！！

动图演示
画图的不好，勿喷

其实每次移动的就只有end而已，因为end-1会随着end的变化而变化的，其次就是，每次比较end和end-1，只要end-1比end大就交换两这，也就是上述所说到的大的数字向后走。

从其中我们不难看出来，这个过程是需要有两个循环的，一层循环控制的是end，当end走到数组外排序就完成了，内层循环是控制end和end-1之间小数组的，内层循环结束的条件就是end>0，因为当end是第一个数据的时候，end-1就会出现错误❌。

看到这里我想大家可以分析一下时间复杂度了，待会我们再来看时间复杂度的分析。

下面我们直接给出代码：

#include 
void Insert(int* a, int n)
{int i = 0;for(i = 1; i < n; ++i){int end = i;while(end > 0){if(a[end] < a[end-1]){//交换int tmp = a[end];a[end] = a[end-1];a[end-1] = tmp;}end--;}}
}void Test()
{int arr[] = {-3,1,2,3,5,7,19,2,15,10,8,3,7,-1,-2};int sz = sizeof(arr) / sizeof(arr[0]);Insert(arr, sz);//打印数据int i = 0;for(i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}int main()
{Test();return 0;
}

时间和空间复杂度分析

实现了算法之后我们就来谈一下时间复杂度和空间复杂度吧

首先很好理解的是空间复杂度肯定是O(1)，不理解的去补一下时间复杂度和空间复杂度的计算吧。

再然后就是时间复杂度的计算，其实也很好理解，每一次end无论是在小数组中遍历还是在大数组中进行遍历，都是n，所以整体的时间复杂度就是 O(n^2)。

希尔排序

上面我们说过希尔排序是对插入排序的一种优化，插入排序虽然做到了成功排序，但是在时间复杂度上还是消耗太大，接下来我们看一下希尔排序是怎么对插入排序进行优化的。

希尔排序的思路（文字）
为了更好的讲解希尔排序的思路，我们以一个比较长一点的数组为例
以数组【-3,1,2,3,5,7,19,2,15,10】为例

希尔排序与插入排序的区别在于，希尔排序会对原数据进行一个预排序。
OK，下面先来讲解一下什么是预排序：
插入排序的时候，是直接以数组的第二个数字为end，依次往后的进行排序，每次和end进行比较的都是end-1，这就导致了时间复杂度是N^2的结果，但是如果我们在判断小数组的数据是否有序时，有序就跳出来，那么再假设此时的数据大部分都是有序的话，有一些的小数组就不必进如循环，从而帮我们节省了一定的时间。

现在我们要做的就是如何让原本错乱的数据出现一定的有序数字，这就是我们的预排序需要做的事情了，此时我们就需要跳跃式的进行插入排序，所谓的跳跃式就是，不再直接先对相邻的两个数字进行判断，而是先对相距一定距离的两个数字进行大小的判断，再通过不短的缩短数字之间的间距，从而对数据进行一个预排序的目的。

我们将这个间距暂时的命名为gap。

当gap从大到小不断缩短的这个过程就是预排序的过程，当gap为1的时候，就是插入排序了，只不过在gap为1的时候，由于预排序的作用，数据大概都已经是有序的了。

此时再进行一次插入排序，数据就会完全的有序。

看到这里的话，如果你是之前了解过希尔排序的，相信已经能写出代码来了。加油老铁！

同样的接下来我们还是用动态图来演示一遍上述的过程。

动图演示

勿喷！老铁。

这里我只演示了gap第一次值为4的走法，这趟循环过后，我们就可以再次通过gap = gap / 3 + 1来缩小gap，再次让数据更加的趋向有序一点。

所以我们是需要有三层循环的，第一层来控制gap的缩小
第二层我们来控制end的结束，我们不难发现，end结束的条件就是小于 n - gap
第三层来控制以gap为间距的小数组的排序

现在我们来解释为什么是gap = gap / 3 + 1，其实gap的起始值为多少都是可以的，只不过不能是太小（要不然预排序就发挥不特性了），关键的是，我们需要让gap的最后一次的值为1，因为只有gap的最后一次的值为1，才能完成对预排序过后数据的完全有序，gap / 3 + 1最终的值就只能为1，此时就正好进行最后一次的插入排序。

下面是代码：

void Shell(int* a, 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 = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//来的这里有两种可能//1.前面的数据都已经有序了//2.小的数据向前走a[end + gap] = tmp;}}
}Test1()
{int arr[] = { -3,1,2,3,5,7,19,2,15,10,8,3,-7,1,2,-10 };int sz = sizeof(arr) / sizeof(arr[0]);Shell(arr, sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
int main()
{Test1();return 0;
}

刚开始看不懂的话，大家可以以上面的数据为例，自己用笔画着走一遍，大致也就能明白了。

时间和空间复杂度分析

关于希尔排序的空间复杂度肯定也是O(1)了，希尔排序的时间复杂度就比较的难推了，我只认为自己写的不够好，就截断了，有人觉得，这个也每比直接插入排序快多少吧，但是它还是要比直接插入排序要快的，时间复杂度大概为O(n^(2/3))，证明大家感兴趣的话，可以找一下相关的文章看一下，但是没必要，你只要知道它比直接插入排序要快一些就OK了。