希尔排序.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
typedef int InfoType;

#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct {				//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1];	//SeqList为顺序表类型，表中第0个单元一般用作哨兵

void main()
{
	void ShellPass(SeqList R,int d);
	void ShellSort(SeqList R);
	int i;
	SeqList R;
	printf("请输入欲排序的数：");
	for (i=1;i<=n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	ShellSort(R);
	printf("排序后：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}

void ShellPass(SeqList R,int d)
{	//希尔排序中的一趟排序，d为当前增量
	int i,j;
	for(i=d+1;i<=n;i++)			//将R[d+1..n]分别插入各组当前的有序区
		if(R[i].key<R[i-d].key) {
			R[0]=R[i];j=i-d;	//R[0]只是暂存单元，不是哨兵
			do {				//查找R[i]的插入位置
				R[j+d]=R[j];	//后移记录
				j=j-d;			//查找前一记录
			} while(j>0&&R[0].key<R[j].key);
			R[j+d]=R[0];		//插入R[i]到正确的位置上
		}
}

void ShellSort(SeqList R)
{
	int increment=n;				//增量初值，不妨设n>0
	do {
		increment=increment/3+1;	//求下一增量
		ShellPass(R,increment);		//一趟增量为increment的Shell插入排序
	} while(increment>1);
}