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

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

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

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

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

試題四
閱讀下列說明和c代碼，回答問題1至問題3，將解答寫在對應(yīng)欄內(nèi)。
[說明]
某應(yīng)用中需要對100000個整數(shù)元素進(jìn)行排序，每個元素的取值在0～5之間。排序算法的基本思想是：對每一個元素x，確定小于等于x的元素個數(shù)(記為m)，將x放在輸出元素序列的第m個位置。對于元素值重復(fù)的情況，依次放入第m-1、m-2、…個位置。例如，如果元素值小于等于4的元素個數(shù)有10個，其中元素值等于4的元素個數(shù)有3個，則4應(yīng)該在輸出元素序列的第10個位置、第9個位置和第8個位置上。
算法具體的步驟為：
步驟1：統(tǒng)計每個元素值的個數(shù)。
步驟2：統(tǒng)計小于等于每個元素值的個數(shù)。
步驟3：將輸入元素序列中的每個元素放入有序的輸出元素序列。
[C代碼]
下面是該排序算法的C語言實現(xiàn)。
常量和變量說明
R：常量，定義元素取值范圍中的取值個數(shù)，如上述應(yīng)用中R值應(yīng)取6。
i：循環(huán)變量。
n：待排序元素個數(shù)。
a：輸入數(shù)組，長度為n。
b：輸出數(shù)組，長度為n。
c：輔助數(shù)組，長度為R，其中每個元素表示小于等于下標(biāo)所對應(yīng)的元素值的個數(shù)。
12函數(shù)sort
1 void sort(int n, int a[], int b[])  {
2    int c[R], i;
3    for(i=0; i＜  11  ; i++)  {
4    c[i]=0;
5    }
6    for(i=0; i＜n; i++)  {
7    c[a[i]]=  12  ;
8    }
9    for(i=1; i＜R; i++)  {
10    c[i]=  13  ;
11    }
12    for(i=0; i＜n; i++)  {
13    b[c[a[i]]-1]=  14  ;
14    c[a[i]]=c[a[i]]-1;
15    }
16  }
【問題1】根據(jù)說明和C代碼，填充C代碼中的空缺(1)～(4)。
【問題2】根據(jù)C代碼，函數(shù)的時間復(fù)雜度和空間復(fù)雜度分別為  (5)  和  (6)  (用O符號表示)。
【問題3】根據(jù)以上C代碼，分析該排序算法是否穩(wěn)定。若穩(wěn)定，請簡要說明(不超過100字)；若不穩(wěn)定，請修改其中代碼使其穩(wěn)定(給出要修改的行號和修改后的代碼)。

信管網(wǎng)cnit**************：
11 r 22 c[a[i]]+1 13 c[i-1]+c[i] 14 c[a[i]]-1 時間 o（n2） 空間 o（n2）

信管網(wǎng)cnit**************：
看完了才明白 原來題目中的11,12,13,14 是 空缺 1,2,3,4 問題一 1 r 2 c[a[i]]++ 3 c[i] + c[i-1] 4 a[i] 問題二 5 n^2 6 n 問題三 不穩(wěn)定排序 for（ i ＝ n； i ＞0； i --）

信管網(wǎng)cnit**************：
【問題1】 11.r 12.c[a[i]]++ 13. 14. 【問題2】 時間復(fù)雜度o（n^2）,空間復(fù)雜度o（1） 【問題3】