2. 从业资格
  3. 希尔排序算法又称最小增量排序算法，其基本思想是: 步骤1 :构造一个步长序列d

希尔排序算法又称最小增量排序算法，其基本思想是: 步骤1 :构造一个步长序列d

考试题库2022-08-02  73
问题 希尔排序算法又称最小增量排序算法，其基本思想是:步骤1 :构造一个步长序列delta1、delta2...、deltak ，其中delta1=n/2 ，后面的每个delta是前一个的1/2 ， deltak=1；步骤2 :根据步长序列、进行k趟排序；步骤3 :对第i趟排序，根据对应的步长delta，将等步长位置元素分组，对同一组内元素在原位置上进行直接插入排序。【C代码】下面是算法的C语言实现。（1）常量和变量说明data：待排序数组data，长度为n，待排序数据记录在data[0]、data[1]、...、data[n-1]中。n：数组a中的元素个数。delta：步长数组。（2）C程序#include ＜stdio.h>void shellsort(int data[ ], int n){    int *delta,k,i,t,dk,j;    k=n;    delta=(int *)nalloc(sizeof(int)*(n/2));    if(i=0)        do{            ( 1 ) ;             delta[i++]=k;        }while ( 2 ) ;     i=0;    while((dk=delta)>0){        for(k=delta;k＜n;++k)        if( ( 3 ) ) {             t=data[k];            for(j=k-dk;j>=0&&t＜data[j];j-=dk){                data[j+dk]=data[j];            }/*for*/        ( 4 ) ;        //data[j+dk]=t;        }/*if*/        ++i;    }/*while*/}【问题1】（8分）根据说明和c代码，填充c代码中的空(1) ~ (4)。【问题2】（4分）根据说明和c代码，该算法的时间复杂度(5)O(n2) (小于、等于或大于)。该算法是否稳定(6) ( 是或否)。【问题3】（3分）对数组(15、9、7、8、20、-1、 4)用希尔排序方法进行排序，经过di-趟排后得到的数组为(7)。
选项
答案
解析 【问题1】（8分）
（1）k=k/2
（2）k>1
（3）data[k]＜data[k-dt]
（4）data[j+dk]=t
【问题2】（4分）
（5）小于
（6）否

【问题3】（3分）
（7）(4，9，-1，8，20，7，15)
转载请注明原文地址:https://www.tihaiku.com/congyezige/2409364.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)