希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

1.排序原理

主要是通过增量的步长来进行分组，然后对每一组进行直接插入排序

<mark>排序过程</mark>

简单示例，例如：
[4 7 3 8 2 6 5 1]
第一趟排序：
	步长：step=4 分组：[4 2]、[7,6]、[3 5]、[8 1]
	对每一组进行直接插入排序得：[2 4]、[6,7]、[3 5]、[1 8]
	整体排序后：[2 6 3 1 4 7 5 8]
第二趟排序：
	步长：step=2 分组：[2 3 4 5]、[6 1 7 8]
	对每一组进行直接插入排序得：[2 3 4 5]、[1 6 7 8]
	整体排序后：[2 1 3 6 4 7 5 8]
第三趟排序：
	步长：step=1 分组：[2 1 3 6 4 7 5 8]
	对每一组进行直接插入排序得：[1 2 3 4 5 6 7 8]
	整体排序后：[1 2 3 4 5 6 7 8]
排序结束

<mark>图示</mark>

2.源代码：

#include<stdio.h>
#define N 10
void ShellSort(int num[],int len)
{
	int i,j,temp,step;
	for(step=len/2;step>=1;step/=2)//步长间隔每次减半
		for(i=step;i<len;i+=step)//按步长遍历数组
		{
			//插入排序过程
			if(num[i]<num[i-step])
			{
				temp=num[i];
				for(j=i-step;num[j]>temp;j-=step)
					num[j+step]=num[j];
				num[j+step]=temp;
			}
		}
}
int main()
{
	int num[N]={9,8,7,6,5,4,3,2,1,0};
	ShellSort(num,N);
	for(int i=0;i<N;i++)
		printf("%d ",num[i]);
	printf("\n");
	return 0;
}