希尔排序代码-豆柴文库

您所在位置：网站首页 / 希尔排序代码.doc / 文档详情

在线预览结束，喜欢就下载吧，查找使用更方便

10 金币

下载文档

/ 4

下载提示

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

文本预览

#include<stdio.h>
typedefintInfoType;//定义其它数据项的类型

#defineMAXSIZE20//一个用作示例的小顺序表的最大长度
typedefintKeyType;//定义关键字类型为整型
//c9.h对两个数值型关键字的比较约定为如下的宏定义

//c10-1.h待排记录的数据类型

structRedType//记录类型
{
KeyTypekey;//关键字项
InfoTypeotherinfo;//其它数据项，具体类型在主程中定义
};
#defineEQ(a,b)((a)==(b))
#defineLT(a,b)((a)<(b))
#defineLQ(a,b)((a)<=(b))
structSqList//顺序表类型
{
RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元
intlength;//顺序表长度
};

voidShellInsert(SqList&L,intdk)
{//对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比，
//作了以下修改：
//1.前后记录位置的增量是dk,而不是1;
//2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4
inti,j;
for(i=dk+1;i<=L.length;++i)
ifLT(L.r[i].key,L.r[i-dk].key)
{//需将L.r[i]插入有序增量子表
L.r[0]=L.r[i];//暂存在L.r[0]
for(j=i-dk;j>0&&LT(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j];//记录后移，查找插入位置
L.r[j+dk]=L.r[0];//插入
}
}

voidprint(SqListL)
{
inti;
for(i=1;i<=L.length;i++)
printf("%d",L.r[i].key);
printf("\n");
}

voidprint1(SqListL)
{
inti;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}

voidShellSort(SqList&L,intdlta[],intt)
{//按增量序列dlta[0..t-1]对顺序表L作希尔排序。算法10.5
intk;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序
printf("第%d趟排序结果:",k+1);
print(L);
}
}

#defineN10
#defineT3
voidmain()
{
RedTyped[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqListl;
intdt[T]={5,3,1};//增量序列数组
for(inti=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:");
print(l);
ShellSort(l,dt,T);
printf("排序后:");
print1(l);
}