希尔排序算法的四种方法

思想简单描述:

在直接插入排序算法中，每次插入一个数，使有序序列只增加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]=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++)//从数组第gap个元素开始
		{
			if (array[j]<array[j-grap])//每个元素与自己组内的数据进行直接插入排序 
			{
				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=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=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=0 && array[j]>tmp)
			{
				array[j+k] = array[j];
				j -= k;
			}
			array[j+k] = tmp;
		}
		k = k/2;/*缩小间距值*/
	}
}

应该还会有更多，更优，更好的实现方法，由于水平有限，不足之处，还请大家多多指正！