軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：www.bestofbreeders.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：www.bestofbreeders.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2025/12/7）在線測(cè)試：www.bestofbreeders.com/exam/ExamDayAL.aspx?t1=4&day=2025/12/7

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2025/12/7）

【說(shuō)明】
希爾排序算法又稱最小增量排序算法，其基本思想是:
步驟1 :構(gòu)造一個(gè)步長(zhǎng)序列delta1、delta2...、deltak ，其中delta1=n/2 ，后面的每個(gè)delta是前一個(gè)的1/2 ， deltak=1；
步驟2 :根據(jù)步長(zhǎng)序列、進(jìn)行k趟排序；
步驟3 :對(duì)第i趟排序，根據(jù)對(duì)應(yīng)的步長(zhǎng)delta，將等步長(zhǎng)位置元素分組，對(duì)同一組內(nèi)元素在原位置上進(jìn)行直接插入排序。
【C代碼】
下面是算法的C語(yǔ)言實(shí)現(xiàn)。
（1）常量和變量說(shuō)明
data：待排序數(shù)組data，長(zhǎng)度為n，待排序數(shù)據(jù)記錄在data[0]、data[1]、...、data[n-1]中。
n：數(shù)組a中的元素個(gè)數(shù)。
delta：步長(zhǎng)數(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];kif( ( 3 ) ) {
t=data[k];
for(j=k-dk;j>=0&&tdata[j+dk]=data[j];
}/*for*/
( 4 ) ; //data[j+dk]=t;
}/*if*/
++i;
}/*while*/
}

【問(wèn)題1】（8分）
根據(jù)說(shuō)明和c代碼，填充c代碼中的空(1) ~ (4)。
【問(wèn)題2】（4分）
根據(jù)說(shuō)明和c代碼，該算法的時(shí)間復(fù)雜度(5)O(n2) (小于、等于或大于)。該算法是否穩(wěn)定(6) ( 是或否)。
【問(wèn)題3】（3分）
對(duì)數(shù)組(15、9、7、8、20、-1、 4)用希爾排序方法進(jìn)行排序，經(jīng)過(guò)di-趟排后得到的數(shù)組為(7)。信管網(wǎng)試題答案與解析：www.bestofbreeders.com/exam/ExamDayAL.aspx?t1=4&day=2025/12/7

信管網(wǎng)考友試題答案分享：

信管網(wǎng)1768*******：
//打印數(shù)組 void ｐｒｉｎｔarray（int arr[], int size） {..} void shellsort（int data[ ], int n）{ if （n ＜= 1） return； int ＊delta； int dk； //步長(zhǎng) int i=0,j,k=n； int t； //臨時(shí)存放 delta ＝ （int ＊）malloc（sizeof（int） ＊ （n / 2 + 1））； do{ k ＝ k/2； delta[i++]=k； }while（ k＞1 ）； i=0； while（（dk=delta[i]）＞0）{ for （k ＝ dk； k ＜ n； k++） { if（ data[k]）{ t ＝ data[k]； for（ j=k-dk； j＞=0 && data[j]＞t； j -=dk）{ data[j + dk] ＝ data[j] ； } data[j+dk] ＝ t； } } ｐｒｉｎｔf（＂第 ％d趟 ，步長(zhǎng)為％d 的時(shí)候，排完的數(shù)組為：＂, i+1, dk）； ｐｒｉｎｔarray（data,n）； ++i； } }

信管網(wǎng)1768*******：
void shellsort（int data[ ], int n）{ if （n ＜= 1） return； // 如果數(shù)組長(zhǎng)度小于等于1，無(wú)需排序 int ＊delta； int dk； //步長(zhǎng) int i=0,j,k=n； int t； //臨時(shí)存放 // 分配 delta 數(shù)組，大小為 n/2 + 1 以確保足夠的空間 delta ＝ （int ＊）malloc（sizeof（int） ＊ （n / 2 + 1））； // 把 步長(zhǎng) 存起來(lái) do{ //（1）； k ＝ k/2； delta[i++]=k； }while（ k＞1 ）； //（2） // 當(dāng)n=8時(shí)，delta=[4,2,1] delta[i] ＝ 0； // 終止標(biāo)志 ｐｒｉｎｔf（＂delta：＂）； ｐｒｉｎｔarray（delta,i）； i=0； // 使用生成的步長(zhǎng)序列進(jìn)行希爾排序 while（（dk=delta[i]）＞0）{ // 對(duì)每個(gè)步長(zhǎng) dk 進(jìn)行插入排序 for （k ＝ dk； k ＜ n； k++） { //（3） if（ data[k]）{ t ＝ data[k]； // for（ j=k-dk； j＞=0 && data[j]＞t； j -=dk）{ data[j + dk] ＝ data[j] ； } data[j+dk] ＝ t； //（4） } } ｐｒｉｎｔf（＂％d 的步長(zhǎng)時(shí)：＂, dk）； ｐｒｉｎｔarray（data,n）； ++i； }/＊while＊/ }

信管網(wǎng)cnit**************：
＜br /＞＜img src=＂http://pic.cnitpm.com/upload/2023/02/tbimg/02-26/1677397109.jpg＂ /＞

信管網(wǎng)cnit**************：
＜br /＞＜img src=＂http://pic.cnitpm.com/upload/2022/11/tbimg/11-02/1667342311.jpg＂ /＞

信管網(wǎng)cnit**************：
1. k ＝ k/2 k ＞= 1 data[j + dk] ＞= data[j] data[j+dk]=t 2, 大于 否

信管網(wǎng)試題答案與解析：www.bestofbreeders.com/exam/ExamDayAL.aspx?t1=4&day=2025/12/7