对序列(503，87，512，61，908，170，897，275，653，426)使用希尔排序（增量序列为5、3、1）算法进行排序，补充函数，输出每趟排序后的结果。#include "stdio.h" #define MAXSIZE 20 //顺序表的最大长度 typedef struct { int key; char *otherinfo; }ElemType; //顺序表的存储结构 typedef struct { ElemType r[20]; //存储空间的基地址 int length; //顺序表长度 }SqList; //顺序表类型 void show(SqList L) { int i; for(i=1;i<=L.length;i++) printf("%4d",L.r[i].key); printf("\n"); } void ShellInsert(SqList &L,int dk) { //**************************************** //**************************************** } void ShellSort(SqList &L,int dt[ ],int t) { //按增量序列dt[0..t-1]对顺序表L作t趟希尔排序 int k; for(k=0;k<t;++k) ShellInsert(L,dt[k]); //一趟增量为dt[t]的希尔插入排序 } void main() { SqList L; int dt[3]={5,3,1}; int t=3; L.r[1].key=503; L.r[2].key=87; L.r[3].key=512; L.r[4].key=61; L.r[5].key=908; L.r[6].key=170; L.r[7].key=897; L.r[8].key=275; L.r[9].key=653; L.r[10].key=426; L.length=10; ShellSort(L,dt,3); printf("希尔排序后的结果为："); show(L); }

完整的代码如下：

#include "stdio.h" 
#define  MAXSIZE  20  	//顺序表的最大长度 

typedef struct {
    int key; 
    char *otherinfo; 
}ElemType; //顺序表的存储结构                          

typedef struct { 
    ElemType r[20];		//存储空间的基地址 
    int  length;     	//顺序表长度 
}SqList;			//顺序表类型 

void show(SqList L) { 
    int i; 
    for(i=1;i<=L.length;i++) 		
        printf("%4d",L.r[i].key); 
    printf("\n"); 
} 

void ShellInsert(SqList &L,int dk) { 
    int i, j;
    ElemType temp; //temp用来存放当前要插入的元素
    for(i=dk+1;i<=L.length;i++) {
        if(L.r[i].key<L.r[i-dk].key) { //需要将L.r[i]插入有序增量子表
            temp = L.r[i];
            j = i-dk;
            while(j>0 && temp.key<L.r[j].key) { //将记录后移，查找插入位置
                L.r[j+dk] = L.r[j];
                j = j-dk;
            }
            L.r[j+dk] = temp; //插入到正确位置
        }
    }
    printf("增量为%d的排序结果：", dk);
    show(L);
}

void ShellSort(SqList &L,int dt[],int t) { 
    //按增量序列dt[0..t-1]对顺序表L作t趟希尔排序 
    int k;     
    for(k=0;k<t;++k) {
        ShellInsert(L,dt[k]); //一趟增量为dt[t]的希尔插入排序
    }
} 

void main() { 
    SqList L; 
    int dt[3]={5,3,1}; 
    int t=3; 
    
    L.r[1].key=503; 
    L.r[2].key=87; 
    L.r[3].key=512; 
    L.r[4].key=61; 
    L.r[5].key=908; 
    L.r[6].key=170; 
    L.r[7].key=897; 
    L.r[8].key=275; 
    L.r[9].key=653; 
    L.r[10].key=426; 
    L.length=10; 
    
    printf("初始序列为：");
    show(L);
    
    ShellSort(L,dt,3); 
    
    printf("希尔排序后的结果为："); 
    show(L); 
}

输出结果如下：

初始序列为： 503  87 512  61 908 170 897 275 653 426
增量为5的排序结果： 170  87 512  61 426 503 897 275 653 908
增量为3的排序结果： 170  61 512  87 426 503 897 275 653 908
增量为1的排序结果： 61  87 170 275 426 503 653 897 908 512
希尔排序后的结果为： 61  87 170 275 426 503 653 897 908 512