前言：学习希尔排序前最好先掌握插入排序，在进行；不会的可以点击——>【排序算法】插入排序-CSDN博客
一、希尔排序：
希尔排序，也称为缩小增量排序，是一种基于插入排序的快速改进算法。由Donald Shell于1959年提出。 它的基本思想是将待排序的元素按照一定的增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序在一般用于处理大量数据！！
二、思路：
分成2个阶段：
1、预排序：这个阶段将待排序的数据分成gap组，对每组数据进行插入排序。
2、插入排序：gap==1时，也就是只有1组的情况，这个数组就变成有序数组了。
具体详情：
1、将一个小于n（元素个数的）的整数作为gap增量，所有距离为gap的元素作为一组数据（也就是我们说的将数组分成gap组）然后对每一组数据进行插入排序，排好后，取一个比第一增量小的整数（比原gap小的组数）重新将新的gap距离的元素作为一组数据，接着上述操作；重复这些操作
2、当gap不断细分到了gap==1即将所有元素分为一组时，进行插入排序，数据变成有序！
下面的动图，我觉的比较直观的了？当然没看懂也没关系，下面会有讲解
先分组，然后你会发现我们分了三组，我们以3个元素为一组分的，但是有的组元素个数未满三个，因为元素之间的距离和数组长度的差异，会有点不同，但是影响不大哈，值得注意的是距离差3，不是元素个数差3哈，个数是只差了2个元素，从图里也可以看出来
分为3个组：
第一组：8、7、5
第二组：9、2、4
第三组：1、3
对第一组进行插入排序
然后接下来是下标为0+gap+gap的位置来一次插入排序，该位置本来的元素是5，经过插入排序后，5到了这组数据的最前面；此时这一组的数据是不是变成有序了
当每组都进行完插入排序后，我们可以发现小的数几乎靠近左边，大的数几乎靠近右边。大致粗略有点顺序了
然后将gap==1，进行一次整体的插入排序；因为数据比较少 所以这里gap的分化次数也比较少
三、时间复杂度：(有点难证明，记住即可)
O（N^1.3）
四、实现：
先考虑一组的实现哈。发现了没？其实和插入排序实现很相似，这里如果gap==1就是插入排序了。我们用的gap为3，实现过程和插入排序的写法大差不差，就是end+1换成了end+gap
✨我们对于每一组元素都要进行插入排序，用到了for循环来保证每个组进行交换，外层的i控制的是你的每一轮的j开始时每个组的头位置，内层j是保证你遍历的都是自己组的成员，这个是以一组进行的排序，排完一组后再排另一组，直到gap组排完；不知道你发现了没有，先写底层逻辑再写真的会很清晰；我们会顺畅很多✨
但是🤔🤔🤔我不想要三层循环嵌套，可以修改一下，之前是一组一组的进行，就是说排好一组在进行另一组。现在我直接交错进行，先第一组的第一个元素，然后第二组的第一个元素，然后第三组的第一个元素，直到gap组的第一个元素都进行了一次插入排序，接下来再是第一组的第二个元素……以此类推；
为啥 🤔是 i<n-gap；因为我们会抽处 end+gap 这张牌，所以当到了每个组倒数第二个元素就可以了也就是i只要到最后一组的倒数第二个元素空了，因为最后一个元素会和前一个元素比较的，不要越界访问
最后我们要完成gap的变化，gap不是一直不变的，会不断地变小，直到gap==1；也就是第二个阶段：对整个数组进行插入排序。所以gap是个变值；
整体代码：
void ShellSort(int* a, int n)
{
int gap = n;
//gap的组数越大，数据可以更快的跳到后面，小的更快跳到前面，但是越不接近有序；反之，gap越接近有序
while (gap > 1)
{
//巧妙的用的除法，/2 /3 /4都行，但是有人证明了/3更好，还要加1，因为gap小于3的话gap/3==0
//最后一次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 (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}gap的选取：
gap刚开始时从每组3个数据开始进行分组插入排序，然后gap=gap/3+1不断地分化组数（分的组数在减少，但是相反的每组数据个数在增加）加一个 1 是为了保证最后一次满足gap==1，因为gap/3 gap小于3时得到的商只能是0；并不是只能gap/3，也可以gap/2等等，但是目前gap/3+1是时间复杂度被验证过了的
分组组数的特点：
gap越大，每一组的数据间隔越大（中间隔的元素个数多），插入一次的幅度更大，大的数据能够更快的跳到后面，小的数据也能更快的跳到前面，但是越远离有序
gep越小，每组数据间隔越小（中间隔的元素个数少），此时数据跳到后面也就越慢，小的数据跳到前面也越慢；但是越接近有序，即gap==1时就是有序的
为了便于观察，没有写+1，gap初始为n（数据个数）在第一次分组时，gap以3个数据为一组，第二次分组时gap在原来的基础上再除以3 此时以9个数据为一组进行分组，依次类推，gap越小，每组内元素个数越多；
感 谢 观 看