C语言希尔排序详解！！！速过-Toy模板网

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

希尔排序是什么？

关于时间复杂度

希尔排序的源代码

希尔排序源代码的详解

希尔排序是什么？

之前我们说了三个排序（插入排序，选择排序，冒泡排序）有需要的铁铁可以去看看之前的讲解。

但因为之前的排序时间复杂度都是n^2.接下来介绍的希尔排序是一个时间优于前面三种排序的算法

C语言希尔排序详解！！！速过,c语言,数据结构,数据结构,算法,排序算法,c语言

由上图我们看到排序被分为了许多组（不同的颜色），这就是希尔排序的

第一步：分组小排（自己取得名）

这一阶段呢就是要将每个组进行一个排序让其每个组都是有序的，这样形成一个散乱但比之前更有序的结果，可以从图中第一轮结果看出。

但我们发现好像这也没有序啊，当然了，如果这么简单那这个时间负责度就是n了，所以就需要下一步了。

第二步：改间隔，重新排。

由于第一步的开荒，数组比刚开始有序的多但还是模糊，接下来如果我们把间隙改小，那每一个小组的数字就会增多，但又由于之前第一组的原因其实有些数据已经其实已经到了属于自己的位置，那接下来就会减少损耗（不用交换数据）。就这样到gap==1（每组的间隔），就有序了

总的希尔排序，就是先分组，在排序，每次使模糊的答案清晰一点（每一次的损耗都会减小），最终当gap == 1时，只需轻轻擦拭即可得出答案。

关于时间复杂度

C语言希尔排序详解！！！速过,c语言,数据结构,数据结构,算法,排序算法,c语言

因为gap的原因所以希尔排序是不稳定的。

希尔排序的源代码

void ShellSort(int* a, int n)
{
	int gap = n;
	while(gap>1)
	{
		gap = gap / 2;
		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;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序源代码的详解

首先传入一个数组a，和数组个数n。

gap == n，为什么要gap > 1呢？因为当gap一直除以2，最后一组的gap 一定是2。

因为之前介绍到，到gap == 1时排完这时候数组就是有序的了。所以当 gap == 2 / 2 == 1时。最后一趟走完就可以走出循环了。文章来源地址https://www.toymoban.com/news/detail-831032.html

到了这里，关于C语言希尔排序详解！！！速过的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！