11-2.c

这些是数据结构结构的经典实现算法

#include  < stdio.h>
#define n 100 //假设的文件长度,即待排序的记录数目
typedef int KeyType; //假设的关键字类型
typedef struct{ //记录类型
   	 	KeyType key; //关键字项
    	//其它数据项,类型InfoType依赖于具体应用而定义
}RecType;
typedef RecType SeqList[n+1];
//SeqList为顺序表类型,表中第0个单元一般用作哨兵
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]到正确的位置上
       } //endif
} //ShellPass
void  ShellSort(SeqList R)
{
    int increment=n; //增量初值,不妨设n>0
    do {
          increment=increment/3+1; //求下一增量
          ShellPass(R,increment); //一趟增量为increment的Shell插入排序
     }while(increment>1);
} //ShellSort
void Initial(SeqList R)
{
	//初始化
}
void main()
{
	SeqList R;
	Initial(R);
	ShellSort(R);
}