纯手撸——希尔排序

思想：先分组变成若干个子组，对每个子组分别插入排序，几次过后会得到一个基本有序的整组，对这个整组进行一次直接插入排序即可。

看图写代码：

void ShellSort(int a[],int n)
{
	int tmp,j;
	for(int d=n/2;d>0;d=d/2) //d为选择的步长，逐渐减小
	{
		for(int i=d;i<n;i++)
		{
			tmp=a[i]; //对相隔d个位置的子组用直接插入排序
			for(j=i-d;j>=0&&tmp<a[j];j=j-d)
			{
				a[j+d]=a[j]; //交换
			}
			a[j+d]=tmp;
		}
	}
}