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

希尔排序的基本思维

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

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

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