鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

【数据结构】希尔排序

来源:互联网 作者:佚名 时间:2015-09-25 05:43
希尔 排序 的原理参见,维基百科,http://zh.wikipedia.org/wiki/希尔 排序 ,这里给出源代码。 #includestdio.hvoid ShellSort(int a[], int n){int i,j,k,temp,gap;int gaps[]={1,5,13,43,113,297,815,1989,4711,11969,27901,84801,213331,543749,1355339,

希尔排序的原理参见,维基百科,http://zh.wikipedia.org/wiki/希尔排序,这里给出源代码。

#include<stdio.h>

void ShellSort(int a[], int n)
{
	int i,j,k,temp,gap;
	int gaps[]={1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
		213331,543749,1355339,3501671,8810089,21521774,
		58548857,157840433,410151271,1131376761,2147483647};
	for (k=0; gaps[k]<n; k++) ;//取到递增步长里最大的一个
	while(--k >= 0)
	{
		gap = gaps[k];
		for ( i = gap; i < n; i++ )
		{
			j = i - gap;
			temp = a[i];             
			while (( j >= 0 ) && ( a[j] > temp ))
			{
				a[j + gap] = a[j];
				j = j - gap;
			}
			a[j + gap] = temp;
		}

	}

}


int main()
{
	int i;
	int a[9]={9,1,5,8,3,7,4,6,2}; 
	ShellSort(a,9);

	for(i=0 ; i<9 ;i++)  
	{  
		printf("%d ",a[i]);  
	}  

}


 

网友评论
<