在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较

相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于

1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的

下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个

要排序的数被分成一组，排序完成。下面有几种用C语言实现的方法：

方法一：

严格按照定义来实现的算法

void ShellSort1(int *array, int len)
{
	int i, j, grap, k, tmp;
	for(grap=len/2; grap>0; grap/=2)//步长
	{
		for(i=0; i<grap; i++)//直接插入排序
		{
			for(j=i+grap; j<len; j+=grap)
			{
				if (array[j]<array[j-grap])
				{
					tmp = array[j];
					k = j-grap;
					while(k>=0 && array[k]>tmp)
					{
						array[k+grap] = array[k];
						k -= grap;
					}
					array[k+grap] = tmp;
				}
			}
		}
	}
}

void ShellSort2(int *array, int len)
{
	int i,j,grap,tmp,k;
	
	for(grap=len/2; grap>0; grap /=2)
	{
		for(j=grap; j<len; j++)<span><span class="comment">//从数组第gap个元素开始</span></span>
		{
			if (array[j]<array[j-grap])<span><span class="comment">//每个元素与自己组内的数据进行直接插入排序</span><span> </span></span>
			{
				tmp = array[j];
				k = j-grap;
				while(k>=0 && tmp<array[k])
				{
					array[k+grap] = array[k];
					k = k-grap;
				}
				array[k+grap] = tmp;
			}
			
		}
	}
}

void ShellSort3(int *array, int len)
{
	int i,j,k,tmp;
	
	for(k=len/2; k>0; k/=2)
	{
		for(i=k; i<len; i++)
		{
			tmp = array[i];
			for(j=i-k; j>=0 && array[j]>tmp; j-=k)
			{
				array[j+k] = array[j];
			}
			array[j+k] = tmp;
		}
	}
}

void ShellSort4(int *array, int len) 
{
	int i,j,gap;
	for(gap=len/2; gap>0; gap/=2)
	{
		for(i=gap; i<len; i++)
		{
			for(j=i-gap; j>=0 && array[j]>array[j+gap]; j-=gap)
			{
				swap(&array[j], &array[j+gap]);
			}
		}
	}
}

void ShellSort(int *array, int len)
{
	int i,j, tmp, k;
	
	k = len/2;/*间距值*/
	while(k>=1)
	{
		for(i=k; i<len; i++)
		{
			tmp = array[i];
			j = i-k;
			while(j>=0 && array[j]>tmp)
			{
				array[j+k] = array[j];
				j -= k;
			}
			array[j+k] = tmp;
		}
		k = k/2;/*缩小间距值*/
	}
}

希尔排序算法