碎碎念念
希尔排序是插入排序的一种，是直接插入排序的改进版。
我们首先来看直接插入排序，其基本思路是，一般先孤立这堆数字的第一个数，那么它自己一个就是有序了，再拿后面的数和它比较，找到大小位置合适的插进去，完了之后这一小堆还是有序的，再拿后面的来和前面的比较，找到合适的位置插进去，直到全部插完。
直接插入排序的优势
从直接插入排序的思想可以知道，如果这堆数原本就比较有序了，那么直接插入排序是非常高效的，因为交换次数会少很多。
直接插入排序的劣势
但有一种情况是，假设是从小到大排序，前面已经排好了一万个有序数，到这10001个数的时候，恰好它是最小的那一个，那么就要和前面的数全部交换一次，，这就出现了交换距离过长的问题，这是我们不希望看到的。
希尔排序
基于直接插入排序的这两个特点，我们引入了它的升级版——希尔排序。
希尔排序又被称作缩小增量排序。
为了解决直接插入排序交换距离过长问题，我们设想如果能让这一堆待排序的数中比较小的数在一边，比较大的数在另一边，那么发生交换的时候就不用跨过千山万水了。
也就是说，我们要先对这一堆数进行预排序，具体操作是，先选定一个数interval（一般是数字的总数的一半）作为第一增量，然后把间隔为interval的数作为一个小组，对这个小组进行直接插入排序，然后缩小interval（一般是让interval减半）作为第二增量，继续分小组进行直接插入排序，以此类推，操作下去，到interval等于1的时候，小组间间隔为1，也就是对全部元素进行直接插入排序，但整个时候，这一堆数已经相对有序了，直接插入排序这个时候就十分高效了。
代码
代码语言：javascript复制#include<stdio.h>
void insert(int a[],int n)
{
int i,temp,j,interval=n/2;
while(interval>0)//和直接插入相比，就是i和j的变化以interval为单位了。
{
for(i=interval;i<n;i=i interval)//划分小组。
for(j=i;j>0;j=j-interval)//小组内进行直接插入排序。
if(a[j]<a[j-interval])
{
temp=a[j];
a[j]=a[j-interval];
a[j-interval]=temp;
}
interval=interval/2;
}
}
int main()
{
int a[10]={7,3,1,6,2,0,5,8,4,9};
insert(a,10);
for(int i=0;i<10;i )
printf("%d ",a[i]);
}链接——直接插入排序
https://blog.csdn.net/weixin_62264287/article/details/122895216?spm=1001.2014.3001.5501
