cTinGli 2021-06-16 10:24 采纳率: 50%
浏览 117
已采纳

数据结构中的排序问题

  1. 若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行希尔排序,首次增量为5,写出每步过程及结果。
  • 写回答

1条回答 默认 最新

  • bostonAlen 2021-06-16 11:01
    关注
    排序前:[10,7,36,4,8,56,10,11,77,15]
    -------增量d=5-------
    数组情况:[10,7,36,4,8,56,10,11,77,15]
    未排序分组:
    第0分组[10,56]
    第1分组[7,10]
    第2分组[36,11]
    第3分组[4,77]
    第4分组[8,15]
    排序后分组:
    第0分组[10,56]
    第1分组[7,10]
    第2分组[11,36]
    第3分组[4,77]
    第4分组[8,15]
    数组情况:[10,7,11,4,8,56,10,36,77,15]
    -------增量d=3-------
    数组情况:[10,7,11,4,8,56,10,36,77,15]
    未排序分组:
    第0分组[10,4,10,15]
    第1分组[7,8,36]
    第2分组[11,56,77]
    排序后分组:
    第0分组[4,10,10,15]
    第1分组[7,8,36]
    第2分组[11,56,77]
    数组情况:[4,7,11,10,8,56,10,36,77,15]
    -------增量d=1-------
    数组情况:[4,7,11,10,8,56,10,36,77,15]
    未排序分组:
    第0分组[4,7,11,10,8,56,10,36,77,15]
    排序后分组:
    第0分组[4,7,8,10,10,11,15,36,56,77]
    数组情况:[4,7,8,10,10,11,15,36,56,77]
    排序后:[4,7,8,10,10,11,15,36,56,77]
    
    #define SHELL_MAX_SIZE 10
    /*
     定义希尔排序的数据结构
     */
    typedef struct{
        int data[SHELL_MAX_SIZE];//定义数组
        int lenth;//当前数组的长度
    }Shell;
    
    /*
     希尔排序:执行的时间依赖于增量数组.
     增量数组:
     1.建议是降序的.会按照增量的数组顺序做每次的插入排序.
     2.尽量避免增量序列中的增量为互为倍数情况.
     3.最后一个肯定是1,因为最后一次操作是要将整个数组进行排序.
     优势在于:按照前面增量进行排序后,有形成阶段范围的有序,减少了比较次数和移动结点次数
     shell:待排序数组信息
     d[]:增量的数组,会按照增量的数组顺序做每次的插入排序.最后一个元素肯定是1.
     dSize:增量数组的长度
     */
    void shellSort(Shell shell,int d[],int dSize);
    
    
    /*
     希尔排序中的一次排序
     每个分组内使用插入排序进行排序
     shell:希尔数据对象
     d:增量.分组中元素相差的间距
     */
    Shell shellOnceSort(Shell shell,int d);
    
    /*
     打印数组中的分组
     shell:希尔数据对象
     d:增量.分组中元素相差的间距
     第0组:[0,0+dk,0+2*dk,0+3*dk,....]
     第1组:[1,1+dk,1+2*dk,1+3*dk,....]
     第d-1组:[2,2+dk,2+2*dk,2+3*dk,....]
     */
    void printShellGroup(Shell shell,int d);
    
    /*
     打印Shell数据
     */
    void printShell(Shell shell,int start,int end);
    
    
    /*
     希尔排序
     shell:待排序数组信息
     d[]:增量的数组,会按照增量的数组顺序做每次的插入排序.
     dSize:增量数组的长度
     */
    void shellSort(Shell shell,int d[],int dSize){
        printf("排序前:");
        printShell(shell,0,shell.lenth-1);
        int i=0;
        //遍历增量数组
        for(i=0;i<dSize;i++){
            //按照增量分组,组内进行排序进行排序
           shell= shellOnceSort(shell, d[i]);
        }
        printf("排序后:");
        printShell(shell,0,shell.lenth-1);
        
    }
    
    /*
     希尔排序中的一次排序
     每个分组内使用插入排序进行排序
     shell:希尔数据对象
     d:增量.分组中元素相差的间距
     */
    Shell shellOnceSort(Shell shell,int d){
        //1.按照增量d将待排序数组分成d-1组.0~d-1
        //2.开始遍历角标范围:d~shell.length.往每个分组中使用插入排序进行插入.
        //默认情况
        //第0组:有序:[0] 无序:[0+dk,0+2*dk,0+3*dk,....]
        //第1组:有序:[1] 无序:[1+dk,1+2*dk,1+3*dk,....]
        //第d-1组:有序:[d-1] 无序:[2+dk,2+2*dk,2+3*dk,....]
        printf("-------增量d=%d-------\n",d);
        printf("数组情况:");
        printShell(shell, 0, shell.lenth-1);
        printf("未排序分组:\n");
        printShellGroup(shell, d);
        int i,j;
        int temp;//插入排序用到的临时变量
        //3.[d~shell.lenth-1]是无序的,那么就遍历此范围,插入到自己所属的分组中
        for(i=d;i<shell.lenth;i++){
            //3.1:分组内进行插入排序
            if(shell.data[i]<shell.data[i-d]){
                temp=shell.data[i];
                j=i-d;
                //3.2.此时需要找到组内插入的位置
                while (j>=0 && temp<shell.data[j]) {
                    //寻找插入的位置,并且组内进行移动数据
                    shell.data[j+d]=shell.data[j];
                    //组内往前查找
                    j=j-d;
                }
                //3.3找到了组内插入的位置,将值插入即可
                shell.data[j+d]=temp;
            }
        }
        //4.打印当前增量排序后情况
        printf("排序后分组:\n");
        printShellGroup(shell, d);
        printf("数组情况:");
        printShell(shell, 0, shell.lenth-1);
        return shell;
    }
    /*
     打印分组情况
     */
    void printShellGroup(Shell shell,int d){
        int  i,j;
        for(i=0;i<d;i++){
            printf("第%d分组[",i);
            for(j=i;j<shell.lenth;j+=d){
                if(j==i){
                    printf("%d",shell.data[j]);
                }else{
                    printf(",%d",shell.data[j]);
                }
            }
            printf("]\n");
        }
    }
    
    /*
     打印Shell数据
     */
    void printShell(Shell shell,int start,int end){
        printf("[");
        for(int i=start;i<=end;i++){
            if(i==start){
                printf("%d",shell.data[i]);
            }else{
                printf(",%d",shell.data[i]);
            }
        }
        printf("]\n");
    }
    
    int main(int argc, const char * argv[]) 
    {
        Shell shell={{10,7,36,4,8,56,10,11,77,15},10};
        //增量数组
        int  ds[]={5,3,1};
        //希尔排序
        shellSort(shell,ds,3);
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 Sharepoint JS开发 付费技术指导
  • ¥15 输入程序运行仿真后,烟雾值不实时检测,变成固定值
  • ¥20 数据排序,可选择排序方向
  • ¥15 修改一下代码,考虑进程到达时间不同的情况
  • ¥15 帮我看看这是个啥题,带解题过程和结果,条件如下FCF = 290471.33 g1 = 15% r = 8% g2 = 4% n = 5
  • ¥15 edem模拟颗粒不显示或者生成失败
  • ¥15 Python代码编写
  • ¥15 php 将rtmp协议转hls协议,无法播放
  • ¥20 python代码编写
  • ¥20 使用MPI广播数据遇到阻塞