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

步驟1 :構(gòu)造一個(gè)步長序列delta1、delta2...、deltak ，其中delta1=n/2 ，后面的每個(gè)delta是前一個(gè)的1/2 ， deltak=1;

步驟2 :根據(jù)步長序列、進(jìn)行k趟排序;

步驟3 :對第i趟排序，根據(jù)對應(yīng)的步長delta，將等步長位置元素分組，對同一組內(nèi)元素在原位置上進(jìn)行直接插入排序。

【C代碼】

下面是算法的C語言實(shí)現(xiàn)。

(1)常量和變量說明

data：待排序數(shù)組data，長度為n，待排序數(shù)據(jù)記錄在data[0]、data[1]、...、data[n-1]中。

n：數(shù)組a中的元素個(gè)數(shù)。

delta：步長數(shù)組。

(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分)

根據(jù)說明和c代碼，填充c代碼中的空(1) ~ (4)。

【問題2】(4分)

根據(jù)說明和c代碼，該算法的時(shí)間復(fù)雜度(5)O(n2) (小于、等于或大于)。該算法是否穩(wěn)定(6) ( 是或否)。

【問題3】(3分)

對數(shù)組(15、9、7、8、20、-1、 4)用希爾排序方法進(jìn)行排序，經(jīng)過di-趟排后得到的數(shù)組為(7)。

信管網(wǎng)參考答案：

【問題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)

查看解析：m.xiexiliangjiufa.com/st/4508523548.html

相關(guān)推薦：

點(diǎn)擊查看/下載：軟件設(shè)計(jì)師歷年真題匯總

點(diǎn)擊查看：軟件設(shè)計(jì)師在線培訓(xùn)課程 丨 免費(fèi)試聽課程

免費(fèi)練習(xí)：軟件設(shè)計(jì)師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)