排序2：希尔排序（缩小增量排序）

int gap = 3;
for (int i = 0; i < n - gap; i += gap)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					a[end] = temp;
					end -= gap;
				}
				else
				{
					break;
				}
			}
		}

不难看出，这和直接插入排序的单趟是很相似的。

整个排序的实现

核心思想： 

        1、gap递减，缩小排序组数，最终到gap = 1的时候，就是一次直接插入排序了。

        2、齐头并进。

代码如下：

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//间隔逐渐缩小,最后一次等于插入排序
		gap = gap / 3 + 1;
		//齐头并进
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					a[end] = temp;
					end -= gap;
				}
				else
				{
					break;
				}
			}
		}
	}
}

i 的每次增加从gap变成了1，这样的目的是为了能够逐一的往后走下去，使得每组都能照顾到。

gap赋值n，每次除以3。除以3后加上1的目的是为了能够最后数字变成1。

我们来测试一下：

 结果：

总结

关与希尔排序的时间复杂度问题，是很难计算出来的。

殷人昆老师的《数据结构-用面相对象方法与C++描述》一书中提到：

在n在某个范围的内的时候，时间复杂度约为n^1.3 。当数据过多的时候，时间复杂度也会提高到

n（logn）²。

而希尔排序在排序中也是不稳定的（不稳定：即有可能因为某部分的有序破坏原先的已经变为有序的部分）。