【題目】CSP-S 2022 提高級 第一輪 閱讀程序21#includeiostream23usingnamespacestd;45constintMAXN105;67intn,m,k,val[MAXN];8inttemp[MAXN],cnt[MAXN];910voidinit()11{12cinnk;13for(inti0;in;i)cinval[i];14intmaximumval[0];15for(inti1;in;i)16if(val[i]maximum)maximumval[i];17m1;18while(maximumk){19maximum/k;20m;21}22}2324voidsolve()25{26intbase1;27for(inti0;im;i){28for(intj0;jk;j)cnt[j]0;29for(intj0;jn;j)cnt[val[j]/base%k];30for(intj1;jk;j)cnt[j]cnt[j-1];31for(intjn-1;j0;j--){32temp[cnt[val[j]/base%k]-1]val[j];33cnt[val[j]/base%k]--;34}35for(intj0;jn;j)val[j]temp[j];36base*k;37}38}3940intmain()41{42init();43solve();44for(inti0;in;i)coutval[i];45coutendl;46return0;47}假設輸入的 n 為不大于 100 的正整數k 為不小于 2 且不大于 100 的正整數val[i]在 int 表示范圍內完成下面的判斷題和單選題判斷題1.這是一個不穩定的排序算法。 2.該算法的空間復雜度僅與 n 有關。 3.該算法的時間復雜度為O(m(nk))。 單選題1.當輸入為“5 3 98 26 91 37 46”時程序第一次執行到第 36 行val[]數組的內容依次為 。A. 91 26 46 37 98B. 91 46 37 26 98C. 98 26 46 91 37D. 91 37 46 98 262.若 val[i]的最大值為 100k 取 時算法運算次數最少。A. 2B. 3C. 10D. 不確定3.當輸入的 k 比 val[i]的最大值還大時該算法退化為 算法。A. 選擇排序B. 冒泡排序C. 計數排序D. 桶排序【題目考點】1. 基數排序【解題思路】40intmain()41{42init();43solve();44for(inti0;in;i)coutval[i];45coutendl;46return0;47}先看主函數首先調用了init()函數應該是初始化了什么東西。然后調用solve()應該是解決了什么問題最后輸出val數組的值。val數組為結果。接下來按順序看各個函數先看init()10voidinit()11{12cinnk;13for(inti0;in;i)cinval[i];14intmaximumval[0];15for(inti1;in;i)16if(val[i]maximum)maximumval[i];17m1;18while(maximumk){19maximum/k;20m;21}22}輸入n和k然后輸入n個數字到val數組。maximum這個詞一看就是要求最大值后面果然是循環求val數組的最大值最大值為maximum。接下來只要maximum大于等于k就除以km增加1。這是在求maximum在k進制下的位數。比如k是10 maximum是123一開始m為1第1次判斷maximum k滿足條件maximum除以k后變為12m變為2。第2次判斷maximum k滿足條件maximum除以k后變為1m變為3。第3次判斷maximum k不滿足條件m為3即123是3位數。24voidsolve()25{26intbase1;27for(inti0;im;i){28for(intj0;jk;j)cnt[j]0;29for(intj0;jn;j)cnt[val[j]/base%k];30for(intj1;jk;j)cnt[j]cnt[j-1];31for(intjn-1;j0;j--){32temp[cnt[val[j]/base%k]-1]val[j];33cnt[val[j]/base%k]--;34}35for(intj0;jn;j)val[j]temp[j];36base*k;37}38}而后看solve()函數base變量的意義一會兒再確定。進行i從0~m-1進行m次循環。每次循環內部進行了多次循環。首先使cnt數組下標0~k-1都設為0即數組清零。而后j從0~n-1循環n是數值個數為val數組的長度因此這一次循環是遍歷val數組。對val數組中的每個元素val[j]求val[j]/base%k結合base初值為1每次循環結束時base * k根據經驗可以了解到val[j]/base%k是在取val[j]的某一位數字具體來說是val[j]在k進制下的第i位數字最低位為第0位例如十進制下個位是第0位十位是第1位例va[j] 123, k 10base1, val[j]/base%k 123/1%10 3base10, val[j]/base%k 123/10%10 2base10, val[j]/base%k 123/100%10 1而cnt[val[j]/base%k]的意思就是將val[j]在k進制下的第i位數字進行計數。統計val數組中各個數第i位的數字出現的個數。cnt[x]表示在val數組所有數的第i位中數字x出現的個數。由于是k進制數字因此一位數可以出現的數字只能是0~k-1因此cnt的下標范圍是0~k-1。接下來j從1~k-1執行cnt[j] cnt[j - 1]是將cnt組變為原cnt數組的前綴和cnt[x]表示在val數組所有數的第i位中數字0~x出現的總次數。現在需要按照val數組的第i位為val數組中的元素進行排序使用temp數組臨時保存排序后的元素。以下用x表示val[j]/base%k即val[j]下k進制下的第i位的數字。數字0~x出現的總次數為cnt[x]那么val[j]就是排序后的第cnt[x]個數字應該在下標cnt[x]-1的位置。因此設temp[cnt[x]-1] val[j];即temp[cnt[val[j]/base%k]-1] val[j];接下來下一個第i位的數字為x的val數組中的數值可以認為是排序后的第cnt[x]-1個數字在temp中的下標應該比之前減1所以cnt[x]--下一次還是通過temp[cnt[x]-1] val[j];把數值賦值到temp數組中。為了保持排序的穩定性對于val數組中第i位數字相同的各個數值在val數組中靠后的數值賦值到temp數組中也應該是靠后的。由于對temp數組的賦值順序是從后向前賦值的(表示賦值位置的cnt[x]不斷減少)因此遍歷val數組的順序也應該是從后向前遍歷的。最后把temp數組中的元素復制到val數組中。該過程即可以將val數組中的元素按照第i位的數字從小到大排序。i從0~m-1循環先按第0位從小到大排序然后按第1位從小到大排序而后按第2位。。。最后一次按第m-1位從小到大排序每次排序使用的是穩定的計數排序的方法共有基數個桶即k個桶。該排序算法叫做基數排序。【答案及解析】判斷題1.這是一個不穩定的排序算法。 答F。基數排序是多趟計數排序計數排序是穩定的排序算法整體也是穩定的排序算法。2.該算法的空間復雜度僅與 n 有關。 答F。val數組的長度為n而cnt數組的長度為k即數值的基數。基數排序的空間復雜度與數字個數n與基數k都有關空間復雜度為O(nk)O(nk)O(nk)3.該算法的時間復雜度為O(m(nk))。 答T。第27行進行m次循環循環內部有進行n次的循環也有進行k次的循環。因此時間復雜度為O(m(nk))O(m(nk))O(m(nk))單選題1.當輸入為“5 3 98 26 91 37 46”時程序第一次執行到第 36 行val[]數組的內容依次為 。A. 91 26 46 37 98B. 91 46 37 26 98C. 98 26 46 91 37D. 91 37 46 98 26答D5個數3進制第一次執行到36行時只是按照這5個數字在3進制下的第0位從低到高進行排序。數字在3進制下第0位的數字為該數值除以3的余數十進制數值98269137463進制第0位數字22111由于排序是穩定的因此相同數值按照原順序排列根據3進制第0位數字排序后的結果為91 37 46 98 26選D。2.若 val[i]的最大值為 100k 取 時算法運算次數最少。A. 2B. 3C. 10D. 不確定答D因為有進行n次的循環第29、31、35行該題沒有給出n是多少n的大小會影響運算次數因此無法只靠k的大小決定運算次數。3.當輸入的 k 比 val[i]的最大值還大時該算法退化為 算法。A. 選擇排序B. 冒泡排序C. 計數排序D. 桶排序答C。當k比val的最大值更大時m1相當于所有val數組的數值在k進制下只有1位數。val[j] / base % k的值就是val[j]cnt數組就是計數數組用來統計val數組中每個數值出現的次數。最后根據各個數值出現的次數輸出。這樣的排序算法是計數排序。桶排序是更大的概念凡是使用哈希函數將數值分到多個桶中的排序算法都可以算是桶排序。計數排序是一種特殊的桶排序基數排序是進行了多趟的基數排序也可以歸類為桶排序。該題更準確地說還是退化為計數排序。