史上最全的希爾排序算法

思想簡單描述:

在直接插入排序算法中，每次插入一個數(shù)，使有序序列只增加1個節(jié)點(diǎn)，并且對插入下一個數(shù)沒有提供任何幫助。如果比較

相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動時能跨過多個元素，則進(jìn)行一次比較就可能消除多個元素交換。D.L.shell于

1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中記錄的

下標(biāo)相差d.對每組中全部元素進(jìn)行排序，然后再用一個較小的增量對它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時，整個

要排序的數(shù)被分成一組，排序完成。下面有幾種用C語言實(shí)現(xiàn)的方法：

方法一：

嚴(yán)格按照定義來實(shí)現(xiàn)的算法

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;
				}
			}
		}
	}
}

方法二：代碼量太大了，不夠簡潔清晰。因此進(jìn)行下改進(jìn)和優(yōu)化

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++)//從數(shù)組第gap個元素開始
		{
			if?(array[j]<array[j-grap])//每個元素與自己組內(nèi)的數(shù)據(jù)進(jìn)行直接插入排序?
			{
				tmp?=?array[j];
				k?=?j-grap;
				while(k>=0?&&?tmp<array[k])
				{
					array[k+grap]?=?array[k];
					k?=?k-grap;
				}
				array[k+grap]?=?tmp;
			}
			
		}
	}
}

方法三：在將以上的代碼進(jìn)行下改進(jìn)

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;
		}
	}
}

方法四：還可以再次優(yōu)化：

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]);
			}
		}
	}
}

另一種方法是根據(jù)其它論壇上進(jìn)行整理的，也是比較容易理解一種方法

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;/*縮小間距值*/
	}
}

應(yīng)該還會有更多，更優(yōu)，更好的實(shí)現(xiàn)方法，由于水平有限，不足之處，還請大家多多指正！