c-希尔排序

浏览量 1

希尔排序其实就是分组直接插入排序。先将一个待排列的数据分成若干个小组，然后对每个分组进行直接插入排序，最后将每个数据自成一组，进行直接插入排序，可得到排好的结果。

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//希尔排序，分组插入排序
void sort(int a[],int len)
{
	int j,gap;
	//分组
	for(gap=len/2;gap>0;gap/=2)
		//直接插入排序
		for(j=gap;j<len;j  )
			if(a[j]<a[j-gap])
			{
				int tmp=a[j];
				int k=j-gap;
				while(k>=0&&a[k]>tmp)
				{
					a[k gap]=a[k];
					k-=gap;
				}
				a[k gap]=tmp;
			}	
}
void main()
{
	time_t ts;//时间数据类型
	unsigned int num = time(&ts);//获取时间，转换为整数
	srand(num);//初始化随机数种子
	int a[10];
	//初始化数组
	for (int i = 0; i < 10; i  )
	{
		a[i] = rand() % 10;
		printf("%d",a[i]);
	}
	printf("n");
	sort(a,10);
	for (int i = 0; i < 10; i  )
	{
		printf("%d",a[i]);
	}
	system("pause");
}

举个例子： 7852448160 每两个数作为一组，可分为5组，即[7,4],[8,8],[5,1],[2,6],[4,0],代码中的gap=5就是两个数之间的间隔。对每组做直接插入排序（从小到大）可以得到： 4812078564 然后gap/=2（gap=2）再分成2组，即[4,1,0,8,6],[8,2,7,5,4],排序之后得到： 0214456788 gap=1,每个数作为一组，排序之后得到结果： 0124456788

排序

0 人点赞