希尔排序——C语言实现

????????????????????????????????

?一、希尔排序思想：

??希尔排序本质上也是直接插入排序，但是会先进行预排序，使原序列更接近有序序列，最后将预排之后的序列进行直接插入排序。

?二、思路详解：

?大家看这个序列：arr1[] = {9，8，7，6，5，4，3，2，1，0}，如果用直接插入排序，那么需要往后移动元素的次数为n*(n-1)/2，也就是45次；
但如果是这个序列呢：arr2[] = {0，1，2，3，5，4，8，7，6，9}；，用直接插入排序，需要移动元素的次数仅为4次。

由此可见，对于一个已经比较有序的序列，采用直接插入排序，效果是非常显著的。那么，我们能不能对序列arr1进行处理后使之变成一个相对有序的序列呢？答案是肯定的，这里我们便用到希尔排序的预排序了。

?什么是预排？

预排序：将无序序列以gap为间隔进行分组，所有间隔相同的为一组，分别对每组进行直接插入排序。

如上图：我们假设gap=3，那么我们可以将上面的序列分为红黄蓝三组，对每组进行一次直接插入排序，那么我们将可以得到一个相对有序的序列，
arr3[]={3,2,1,6,5,4,9,8,7}，这样我们就把大的数尽快的排到序列尾部，小的数尽快的排到序列头部。排一趟就行了吗？接下来直接进行直接插入排序吗？答案否定的。看下图：

可以看到，我们会进行多次的预排序，只要gap>1就是预排，当gap==1时，就是直接插入排序。那么我们的代码该怎么写呢？

?三、代码实现

//希尔排序
void ShellSort(int* arr, int sz)
{
	int count=0;//这是我为了看看希尔排序和直接插入排序的性能比较而设置的计数
	int gap = sz;//设置排序的间隔
	while ( gap > 1 )
	{
	   //这里一定要保证gap最后进来循环后为1，所以对此加1
		gap = gap / 3 + 1;//gap>1为与排序，gap==1，为直接插入排序
		
		for (int i = 0; i < sz - gap; i++)//这里并不是一次性把一组排完，而是挨个往后，一组一个轮流排
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
					count++;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
	printf("希尔插入排序后移次数count=%d", count);
}

void test()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[1]);
	ShellSort(arr, sz);
	printf("\n");
	Print(arr, sz);
}

int main()
{
	test();
	return 0;
}

所有的接口都已经写好，大家可以直接复制到vs2017测试。