shell.h

各种排序方法源码

#include<string.h>
//-------------------------------固定增量排序函数--------------------------------------//
void shellinsert(node *d,int num,int inc,int &jc,int &bc)
{//以给定增量inc作一趟希尔排序
	int i,j;
	for(i=inc+1;i<=num;++i)
	{
		bc++;
		if(d[i].data<d[i-inc].data)   //须将插入d[i]有序增量子表
		{
			bc++;jc++;
			d[0].data=d[i].data;     //暂存在d[0]
			strcpy(d[0].c,d[i].c);
			for(j=i-inc;j>0&&(bc++,d[0].data<d[j].data);j-=inc)   //记录后移，查找插入位置
			{    
				d[j+inc].data=d[j].data;
				strcpy(d[j+inc].c,d[j].c);
				jc++;
			} 
			d[j+inc].data=d[0].data;       //插入
			strcpy(d[j+inc].c,d[0].c);
			jc++;
		}
	}
}
//----------------------------希尔排序函数---------------------------------------------//
void shellsort(node *d,int num,int dlt[],int t,int &jc,int &bc)
{//以递减增量排序函数，最终为1
	int k;
	for(k=t-1;k>=0;--k)     //以给定增量dlt[k]对数据进行排序
	{shellinsert(d,num,dlt[k],jc,bc);bc++;}
}
//------------------------希尔排序驱动及增量数组求解函数---------------------------------//
void dlta(node *d,int num,int &jc,int &bc)
{//求得增量数组和驱动希尔排序程序
	int *dlt,i=0,t,ti=1;
	dlt=(int *)malloc(31*sizeof(int));  //增量数组
	dlt[i++]=1;
	while(i<31)
	{
		dlt[i]=(dlt[i-1]+1)*2-1;    //dlt[k]=2的(t-k+1)次－1，t为排序趟数
		i++;
		if(dlt[i-1]<num)  ti=i-1;  
	}
	printf(" 请输入排序趟数(增量序列dlt[k]=2e(t-k+1)－1)(不大于%d):",ti);   //排序趟数输入，求得增量数组
	scanf("%d",&t);
	shellsort(d,num,dlt,t,jc,bc);   //希尔排序
	free(dlt);   //空间释放
}