数据结构之希尔排序

这篇具有很好参考价值的文章主要介绍了数据结构之希尔排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

活动地址：CSDN21天学习挑战赛

作者简介：大家好我是小唐同学(๑>؂<๑），为梦想而奋斗的小唐，让我们一起加油！！！

个人主页：小唐同学(๑>؂<๑）的博客主页

系列专栏：数据结构

博友们如果也是新手入门数据结构我希望大家可以多加练习数据结构题库在牛客网就有已经给大家附上链接，可以直接点击跳转：刷题点这里

牛客网支持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]);
	}
	
	
 }