首页 > 代码库 > 希尔排序算法——缩小增量法排序

希尔排序算法——缩小增量法排序

希尔排序——1959年shell提出而得名,也称为缩小增量排序算法,它是直接插入排序的改进,效率比较高,适合于中小规模的排序。

具体的算法实现步骤为:首先得知道直接插入排序的算法,然后就是选择增量给原数列进行分组,对每个分得的小组进行直接插入排序便可,然后逐渐减小这个增量,依然进行新的分组的直接插入排序,直到增量为1,此时数列便是有序数列了。具体的代码如下:

首先是对特定的增量的分组的直接插入排序:

void _insert(int *A,int d,int length) //d为增量
{
	int temp=0;
	int j=0;
	for(int i=d;i<length;i++)
	{
		temp=A[i];
		for(j=i-d;j>=0 && A[j]>temp;j-=d)
		{
			A[j+d]=A[j];
		}
		A[j+d]=temp;
	}
}
然后就是选择增量来循环调用上面的函数便可:

void _shell(int *A,int length)
{
	for(int i=length/2;i>0;i=i/2)
	{
		_insert(A,i,length);
	}
}
下面编写测试代码:

void main()
{
	int ia[]={0,4,2,1,9,2};
	int length=sizeof(ia)/sizeof(int);
	_shell(ia,length);
	for(int i=0;i<length;i++)
	{
		cout<<ia[i]<<" ";
	}
}
测试结果如下:





希尔排序算法——缩小增量法排序