- #include <stdio.h>
- #define LT(a,b)((a) < (b)) //对两个数值型关键字比较的约定
- #define MAX_SIZE 20 //用作示例的小顺序表的最大长度
- #define N 10 //记录数组长度
- #define T 3 //增量序列数组长度
- typedef int KeyType;
- typedef int InfoType;
- typedef struct //记录结构类型
- {
- KeyType key;
- InfoType otherinfo;
- }RedType;
- typedef struct //顺序表结构类型
- {
- RedType r[MAX_SIZE+1];
- int length;
- }SqList;
- void PrintSqList(SqList L) //打印顺序表
- {
- int i;
- for(i = 1;i <= L.length;i++)
- {
- printf("(%d,%d) ",L.r[i].key,L.r[i].otherinfo);
- }
- printf("\\n");
- }
- void PrintSqListKey(SqList L) //输出顺序表L的关键字
- {
- int i;
- for(i = 1;i <= L.length;i++)
- {
- printf("%d ",L.r[i].key);
- }
- printf("\\n");
- }
- void ShellInsert(SqList &L,int dk) //对顺序表L进行一趟希尔插入排序
- {
- int i,j;
- for(i = dk + 1;i <= L.length;i++)
- {
- if LT(L.r[i].key,L.r[i-dk].key)
- {
- 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]; //插入到相应位置
- }
- }
- }
- void ShellSort(SqList &L,int dlta[],int t) //按增量序列dlta[0,...,t-1]对顺序表L进行希尔排序
- {
- int k;
- for(k=0;k<t;k++) //对所有的增量序列
- {
- ShellInsert(L,dlta[k]); //一趟增量为dlat[k]的希尔插入排序
- printf("dlta[%d]=%d,第%d趟排序结果(仅输出关键字):",k,dlta[k],k+1);
- PrintSqListKey(L);
- }
- }
- void main()
- {
- RedType d[N] = {{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}}; //记录数组
- SqList m; //顺序表
- int i,dt[T] = {5,3,1}; //增量序列数组(从大到小,最后一项的值必为1)
- for(i=0;i<N;i++)
- {
- m.r[i+1] = d[i];
- }
- m.length = N;
- printf("希尔排序前:\\n");
- PrintSqList(m);
- printf("\\n");
- ShellSort(m,dt,T); //按增量序列dt[0,...,T-1]对顺序表作希尔排序
- printf("希尔排序后:\\n");
- PrintSqList(m);
- printf("\\n");
- return;
- }
- //该片段来自于http://www.codesnippet.cn/detail/140520133334.html
来源: http://www.codesnippet.cn/detail/140520133334.html