信管网案例分析

希尔排序算法又称最小增量排序算法，其基本思想是:

步骤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

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[i])>0){

for(k=delta[i];k

if( ( 3 ) ) {

t=data[k];

for(j=k-dk;j>=0&&t

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] (4)data[j+dk]=t

【问题2】(4分)

(5)小于

(6)否

【问题3】(3分)

(7)(4，9，-1，8，20，7，15)

查看解析：www.cnitpm.com/st/4508523548.html

相关推荐：

点击查看/下载：软件设计师历年真题汇总

点击查看：软件设计师在线培训课程 丨 免费试听课程

免费练习：软件设计师考试题库(模拟试题、章节练习、每日一练)