数据结构之希尔排序
作者简介：大家好我是小唐同学(๑><๑），为梦想而奋斗的小唐，让我们一起加油！！！
编辑
个人主页：小唐同学(๑><๑）的博客主页
系列专栏：数据结构
博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已经给大家附上链接，可以直接点击跳转：刷题点这里
牛客网支持ACM模式哦，刷算法题也很推荐哦！！！
下面上文章------》
目录
希尔排序介绍：
希尔排序实际上就是将一组数据进行分组排序（等距元素为一组进行排序），在每一组内进行直接插入排序，让后每一次减少间距，进行排序，到距离为1结束。
希尔排序也可以认为直接插入排序的优化版，优化肯定要从直接插入排序的优点来想
（1）在待排序序列基本有序时，直接插入排序效率会大大提高。
（2）在待排元素数量较小时，直接插入排序效率也会大大提高。
希尔排序就是把这两个优点给放大、利用起来。
希尔排序分组：
希尔排序是如何进行分组那？
对于这个d应该会产生疑惑的，
d1=n/2(n为元素的数量---第一次距离)
d2=d1/2;(向后递推)
dn+1=dn/2
当d=1时结束。
算法步骤：
输入：
一个数组（可以任一序列）
数据存储时要从数组的1开始存储 下标为0的位置是用来做中间临时量，用来进行比较
输出：
输出一个有序序列
算法理解：
希尔排序我们理解起来可以与直接插入排序进行比较，毕竟希尔排序也是在直接插入排序基础上进行的，无非就是多了分组的步骤，那我们可以理解为在组内进行直接插入排序，但是组之间距离为d,所以我们理解的希尔可以根据直接插入排序进行理解，需要把直接插入排序中+1的地方换成+d
实例代码：
#include <stdio.h> int main() { int n; scanf("%d",&n); int a[n+1]; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } int j; int d; for(d=n/2;d>=1;d=d/2) { for(int i=d+1;i<=n;i++) //j是用来比较前方元素 i是向后循环 { a[0]=a[i]; j=i-d; while(j>0&&a[0]<a[j]) { a[j+d]=a[j]; j=j-d; } a[j+d]=a[0]; //因为跳出循环时j-d了，然而a[0]比-d后的a[j]大所以它在后边 所以j+d要+回来 } } for(int i=1;i<=n;i++) { printf("%d ",a[i]); } }
复杂度分析：
时间复杂度：
时间复杂度是不确定的，根据d的取值不同是没办法确定的
空间复杂度：
在希尔排序中只是借用了几个临时变量；
则空间复杂度为：O(1)。
