希尔排序的思维及代码完成

希尔排序的基本思维

希尔排序简略点来说,便是直接刺进排序的优化,能比直接刺进排序应对更多的情况,但两者仍是有些差异:

ps:假如有不清楚直接刺进排序的兄弟能够这篇文章,里边有具体的介绍:
/post/715497…

在咱们排序时,假设咱们想用直接刺进排序来排,可是要排序的数组刚好是个逆序的,那它的时间复杂度就会比较大,也便是说履行的过程会更多更繁琐,而为了优化这种排序的过程,咱们能够先对这种数组进行预排序,预排序便是先让这个数组进行粗略的排序,目的便是让数组更挨近有序,而不是一个完全的逆序数组,这样直接刺进排序在履行的时分,功率就会变高,这便是希尔排序的思维。

那么怎么进行预排序呢?咱们能够把他们分成几个组,来进行排序,比方下面这个数组(假设最后的成果为升序):

image.png

咱们能够先令gap等于3(后面会解释gap究竟怎么取值),意思便是把该数组每3个空分一个组,如下图(end为数组的下标):

image.png

在咱们分好组之后,接下来就能够开端预排序了,也便是一组一组的排序,排序方式跟直接刺进排序相同:

如上图所示,排序从蓝色分组中的第一组的第二个数5开端,跟直接刺进排序相同,将前面的9看作现已排好的数组,5小于9,因而9要往后移,注意移动的时分是以gap为单位移动的;

蓝色这第一组排完序后,end++,开端对绿色分组中的第一组开端排序,tmp也变成的绿色这第一组中要刺进的数据,完成这几步操作后数组的状况如下图所示:
image.png

如上图所示,此刻排序从绿色分组中的第一组开端,因而arr[end]指向该分组中的第一个元素1,tmp指向的7为此刻要刺进的元素,重复直接刺进排序的过程,1和7排完序后,end++,tmp则变成紫色这一组中要刺进的数据,如下图所示:

image.png
用直接刺进排序的方法,重复以上操作。

直到这一步(如下图所示):

image.png

首要咱们仍是用直接刺进排序的方式来排,5小于9,因而9要往后移,5要往前移到9本来的方位,然后end以gap为单位,向前移到8的方位,再让tmp和8进行比较,然后重复上述操作,由于本来end是指的8的方位,因而在这个基础上,end++,如下图所示:

image.png
由此能够发现,tmp此刻现已越界了,end所在的方位刚好是n-gap-1,因而能够将该条件作为排序停止的条件,此刻gap为3的排序就完成了。

这时的数组现已挨近有序了,但希尔排序并不是只需要排这一轮,gap的值在每一轮排序停止后都会削减,由于gap的值每削减一次,数组就会更挨近有序,当gap值为1时,此刻的希尔排序就相当于直接刺进排序了,那么究竟怎么操控gap的值呢?

//怎么操控gap的值:
int gap = n;
while (gap > 1)
{
	gap = gap / 2;
	//用于操控gap的值
	//此处省掉排序的主体
}

如上述代码所示,咱们能够用while来操控gap的值,gap的值在每一轮排序停止后,都会整除一次2,可是为什么是除2呢?

由于gap的值不管为多少,在整除n次2今后,终究的值都会变成1,满足直接刺进排序的条件,比方当gap为5,整除2后会变成2,再整除2后就变成了1

希尔排序的代码完成

当咱们了解上述希尔排序的首要思维后,就能够来写代码了,废话不多说,直接放代码:

#include<stdio.h>     /*printf*/
void PrintArray(int* arr, int len)    /*打印数组内容*/
{
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", arr[i]);
	}
	printf("\n");
}
void ShellSort(int* arr, int n)      /*希尔排序*/
{
	int gap = n;
	//gap:分组的根据,gap的值每减小一次,排序就会越挨近有序
	while (gap > 1)
		//当gap的值为1时,排序就相当于直接刺进排序
	{
		gap = gap / 2;
		//操控gap的值,使其终究能够等于1,满足直接刺进排序的条件
		for (int i = 0; i < n - gap; i++)
			//end排完序后的方位为n-gap-1,因而将n-gap作为停止条件
		{
			int end = i;
			int tmp = arr[end + gap];
			//将要刺进的数据存到tmp傍边
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					//假如tmp的值较小,则arr[end]以gap为单位向后移动
					end = end - gap;
					//gap持续向前比较
				}
				else
				{
					break;
					//排序完成后退出循环
				}
			}
			arr[end + gap] = tmp;
			//此刻tmp后面的值都比它大,前面要么没有数据,要么都比它小
			//tmp成功刺进
		}
	}
	PrintArray(arr, n);         /*打印函数*/
}
int main()
{
	int arr[] = { 9,1,2,5,7,4,8,6,3,5 };
	int len = sizeof(arr) / sizeof(arr[0]);
	//核算数组的长度
	ShellSort(arr, len);       /*希尔排序*/
	return 0;
}

运行成果:

image.png


以上便是本篇文章的全部内容,假如你觉得对你多少有些帮助,能够点个赞或许收藏一波支持一下哦,欢迎各位大佬批评指正,咱们下次再见!