希尔排序概念

希尔排序（Shellsort）也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。希尔（Donald Shell）于1959年提出这种排序算法。

希尔排序是非稳定排序算法。

希尔排序算法思路

动图演示：

希尔排序是按其设计者希尔的名字命名的，该算法由希尔1959年公布。希尔可以说是一个脑洞非常大的人，他对普通插入排序的时间复杂度进行分析，得出了以下结论：
 1.普通插入排序的时间复杂度最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序。
 2.普通插入排序的时间复杂度最好情况下为O(N)，此时待排序列为升序，或者说接近升序。

于是希尔就想：若是能先将待排序列进行一次预排序，使待排序列接近有序（接近我们想要的顺序），然后再对该序列进行一次直接插入排序。因为此时直接插入排序的时间复杂度为O(N)，那么只要控制预排序阶段的时间复杂度不超过O(N2)，那么整体的时间复杂度就比直接插入排序的时间复杂度低了。

希尔排序实现

希尔排序，又称缩小增量法。其基本思想是：
 1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
 2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

问题：为什么要让gap由大到小呢？
answer：gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。

注：一般情况下，取序列的一半作为增量，然后依次减半，直到增量为1（也可自己设置）。

举个例子分析一下：
 现在我们用希尔排序对该序列进行排序。
 

我们用序列长度的一半作为第一次排序时gap的值，此时相隔距离为5的元素被分为一组（共分了5组，每组有2个元素），然后分别对每一组进行直接插入排序。

gap的值折半，此时相隔距离为2的元素被分为一组（共分了2组，每组有5个元素），然后再分别对每一组进行直接插入排序。

gap的值再次减半，此时gap减为1，即整个序列被分为一组，进行一次直接插入排序。

该题中，前两趟就是希尔排序的预排序，最后一趟就是希尔排序的直接插入排序。

代码示例：

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;//gap折半
		int i = 0;
		//进行一趟排序
		for (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;
		}
	}
}

时间复杂度：O(N*logN)  空间复杂度：O(1)

平均时间复杂度：O（N^ 1.3 ~ N^ 1.5）