对顺序表L做一趟增量是dk的希尔插入排序

希尔排序是一种插入排序，其基本思想是将待排序的元素按一定间隔分成若干个子序列，对各个子序列进行插入排序，使得整个序列基本有序。然后缩小间隔，再次进行插入排序，直到间隔为1时，即为插入排序。

对于顺序表L做一趟增量是dk的希尔插入排序的步骤如下：

1. 将L分成若干个长度为dk的子序列，每个子序列分别进行插入排序。

2. 将每个子序列排好序后，再将所有子序列合并成一个有序序列。

3. 缩小增量，即将dk除以2，得到新的增量dk/2，再重复步骤1和2，直到增量为1，即为插入排序。

需要注意的是，希尔排序的时间复杂度与增量序列的选择有关。常见的增量序列有希尔增量序列、斐波那契增量序列、Hibbard增量序列等。其中，希尔增量序列的时间复杂度较为稳定，为O(n^2)。

相关问题

#include <iostream>using nanespace std;#def ine MAXSIZE 20 //顺序表的最大长度 typedef struct int key: char *otherinfo;} ElemType: //顺序表的存储结构typedef struct ElemLype *工， //存储空间的基地址 int length; //顺序表长度 }Salist: //顺序表类型 void ShellInsert (Sglist &L, int dk) //对顺序表L做一趟增里是d:的希尔插入排序int i, j: for (i=dk+1;i<=L. length:++i) if (L.r[i].key<L.r [i-dk].key) //for L.r[0]=L.r[i] : for (j=i-dk;j>0 &8L.r[0]. key<L.r[j].key:j-dk)L.r[j+dk]=L.r[0] 1/ellInsert void ShellSort(SaList &L,int dt[],int t)l1/H48.3 //按增里序列dt [0..t-1]对顺序表L作F趟希尔排序intk: for (k=0;k<t:++k) 1 ShellInsert (L, dt[k]): 11-趟增里为at[t]的希尔插入排序//ShellSort void Create_ Sq(SqList &L) int i,n: cout<<"请输入数据个数，不超过”<MLAXSIZE<<"个。"<<end1 ;ciny)n: //4↑tl cout<<"请输入待排序的数据: \n2 : vhile (n>MАХЅІZЕ) cout<<"个数超过上限，不能超过”LAXSIE <<"，请重新输入"<<end1:cinn: for(i=1;i(=n;itt) cin>L. r[i].key:L. lengthHt; void show(SqList L) for(i-l;i<=L. length;i++)out«L.r[i]. keyKendl iThFmain ( )

这段代码是一个希尔排序的实现，其中包括了一个顺序表的定义和创建，以及希尔排序的具体实现。顺序表的结构体包括了一个元素的键值和其他信息，以及表的长度等属性。希尔排序是一种插入排序的改进，通过将数据按一定间隔分组，对每组数据进行插入排序，然后逐步减小间隔，直到间隔为1，最终达到排序的目的。这里的代码实现中，使用了一个增量序列来控制分组间隔的大小，然后对每个间隔大小进行一趟插入排序，最终完成排序。

对序列(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