希尔排序

      所谓希尔排序既是插入排序的变种，希尔排序是把记录按下标的一定增量分组（建议初始增量为length/2），对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。每次排序都是建立在前一次的排序基础之上，从而可以达到排序的目的。希尔排序的时间复杂度最大为o2，效率十分高。观察下图排序数据的变化（摘自网上别的大神）

    

C代码如下：

#include <stdio.h>
void swap(int *,int *);
void sort(int *,int);
int main(void)
{
	int i=0;
	int num[10]={9,1,2,5,7,4,8,6,3,5};
	sort(num,10);
	for(i=0;i<10;i++)
	{
		printf("%d  ",num[i]);
	}
	printf("\n");
	return 0;
}
//交换数组中两个元素
void swap(int *a,int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//排序
void sort(int *num,int length)
{
	int i=0,j=0,k=0;
	//i控制分组增量
	for(i=length/2;i>0;i/=2)
	{
		//j初始化为i，往前检查，使得增量为i的每个组里，在j位置之前都是有序的（组内有序）
		for(j=i;j<length;j++)
		{
			k = j;
			//往j之前检查，使之有序
			while((k-i>=0)&&num[k-i]>num[k])
			{
				swap(num+k-i,num+k);
				k-=i;
			}
		}
	}
}