【題目】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}假設(shè)輸入的 n 為不大于 100 的正整數(shù)k 為不小于 2 且不大于 100 的正整數(shù)val[i]在 int 表示范圍內(nèi)完成下面的判斷題和單選題判斷題1.這是一個(gè)不穩(wěn)定的排序算法。 2.該算法的空間復(fù)雜度僅與 n 有關(guān)。 3.該算法的時(shí)間復(fù)雜度為O(m(nk))。 單選題1.當(dāng)輸入為“5 3 98 26 91 37 46”時(shí)程序第一次執(zhí)行到第 36 行val[]數(shù)組的內(nèi)容依次為 。A. 91 26 46 37 98B. 91 46 37 26 98C. 98 26 46 91 37D. 91 37 46 98 262.若 val[i]的最大值為 100k 取 時(shí)算法運(yùn)算次數(shù)最少。A. 2B. 3C. 10D. 不確定3.當(dāng)輸入的 k 比 val[i]的最大值還大時(shí)該算法退化為 算法。A. 選擇排序B. 冒泡排序C. 計(jì)數(shù)排序D. 桶排序【題目考點(diǎn)】1. 基數(shù)排序【解題思路】40intmain()41{42init();43solve();44for(inti0;in;i)coutval[i];45coutendl;46return0;47}先看主函數(shù)首先調(diào)用了init()函數(shù)應(yīng)該是初始化了什么東西。然后調(diào)用solve()應(yīng)該是解決了什么問題最后輸出val數(shù)組的值。val數(shù)組為結(jié)果。接下來按順序看各個(gè)函數(shù)先看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個(gè)數(shù)字到val數(shù)組。maximum這個(gè)詞一看就是要求最大值后面果然是循環(huán)求val數(shù)組的最大值最大值為maximum。接下來只要maximum大于等于k就除以km增加1。這是在求maximum在k進(jìn)制下的位數(shù)。比如k是10 maximum是123一開始m為1第1次判斷maximum k滿足條件maximum除以k后變?yōu)?2m變?yōu)?。第2次判斷maximum k滿足條件maximum除以k后變?yōu)?m變?yōu)?。第3次判斷maximum k不滿足條件m為3即123是3位數(shù)。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()函數(shù)base變量的意義一會兒再確定。進(jìn)行i從0~m-1進(jìn)行m次循環(huán)。每次循環(huán)內(nèi)部進(jìn)行了多次循環(huán)。首先使cnt數(shù)組下標(biāo)0~k-1都設(shè)為0即數(shù)組清零。而后j從0~n-1循環(huán)n是數(shù)值個(gè)數(shù)為val數(shù)組的長度因此這一次循環(huán)是遍歷val數(shù)組。對val數(shù)組中的每個(gè)元素val[j]求val[j]/base%k結(jié)合base初值為1每次循環(huán)結(jié)束時(shí)base * k根據(jù)經(jīng)驗(yàn)可以了解到val[j]/base%k是在取val[j]的某一位數(shù)字具體來說是val[j]在k進(jìn)制下的第i位數(shù)字最低位為第0位例如十進(jìn)制下個(gè)位是第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進(jìn)制下的第i位數(shù)字進(jìn)行計(jì)數(shù)。統(tǒng)計(jì)val數(shù)組中各個(gè)數(shù)第i位的數(shù)字出現(xiàn)的個(gè)數(shù)。cnt[x]表示在val數(shù)組所有數(shù)的第i位中數(shù)字x出現(xiàn)的個(gè)數(shù)。由于是k進(jìn)制數(shù)字因此一位數(shù)可以出現(xiàn)的數(shù)字只能是0~k-1因此cnt的下標(biāo)范圍是0~k-1。接下來j從1~k-1執(zhí)行cnt[j] cnt[j - 1]是將cnt組變?yōu)樵璫nt數(shù)組的前綴和cnt[x]表示在val數(shù)組所有數(shù)的第i位中數(shù)字0~x出現(xiàn)的總次數(shù)?，F(xiàn)在需要按照val數(shù)組的第i位為val數(shù)組中的元素進(jìn)行排序使用temp數(shù)組臨時(shí)保存排序后的元素。以下用x表示val[j]/base%k即val[j]下k進(jìn)制下的第i位的數(shù)字。數(shù)字0~x出現(xiàn)的總次數(shù)為cnt[x]那么val[j]就是排序后的第cnt[x]個(gè)數(shù)字應(yīng)該在下標(biāo)cnt[x]-1的位置。因此設(shè)temp[cnt[x]-1] val[j];即temp[cnt[val[j]/base%k]-1] val[j];接下來下一個(gè)第i位的數(shù)字為x的val數(shù)組中的數(shù)值可以認(rèn)為是排序后的第cnt[x]-1個(gè)數(shù)字在temp中的下標(biāo)應(yīng)該比之前減1所以cnt[x]--下一次還是通過temp[cnt[x]-1] val[j];把數(shù)值賦值到temp數(shù)組中。為了保持排序的穩(wěn)定性對于val數(shù)組中第i位數(shù)字相同的各個(gè)數(shù)值在val數(shù)組中靠后的數(shù)值賦值到temp數(shù)組中也應(yīng)該是靠后的。由于對temp數(shù)組的賦值順序是從后向前賦值的(表示賦值位置的cnt[x]不斷減少)因此遍歷val數(shù)組的順序也應(yīng)該是從后向前遍歷的。最后把temp數(shù)組中的元素復(fù)制到val數(shù)組中。該過程即可以將val數(shù)組中的元素按照第i位的數(shù)字從小到大排序。i從0~m-1循環(huán)先按第0位從小到大排序然后按第1位從小到大排序而后按第2位。。。最后一次按第m-1位從小到大排序每次排序使用的是穩(wěn)定的計(jì)數(shù)排序的方法共有基數(shù)個(gè)桶即k個(gè)桶。該排序算法叫做基數(shù)排序?！敬鸢讣敖馕觥颗袛囝}1.這是一個(gè)不穩(wěn)定的排序算法。 答F?；鶖?shù)排序是多趟計(jì)數(shù)排序計(jì)數(shù)排序是穩(wěn)定的排序算法整體也是穩(wěn)定的排序算法。2.該算法的空間復(fù)雜度僅與 n 有關(guān)。 答F。val數(shù)組的長度為n而cnt數(shù)組的長度為k即數(shù)值的基數(shù)?；鶖?shù)排序的空間復(fù)雜度與數(shù)字個(gè)數(shù)n與基數(shù)k都有關(guān)空間復(fù)雜度為O(nk)O(nk)O(nk)3.該算法的時(shí)間復(fù)雜度為O(m(nk))。 答T。第27行進(jìn)行m次循環(huán)循環(huán)內(nèi)部有進(jìn)行n次的循環(huán)也有進(jìn)行k次的循環(huán)。因此時(shí)間復(fù)雜度為O(m(nk))O(m(nk))O(m(nk))單選題1.當(dāng)輸入為“5 3 98 26 91 37 46”時(shí)程序第一次執(zhí)行到第 36 行val[]數(shù)組的內(nèi)容依次為 。A. 91 26 46 37 98B. 91 46 37 26 98C. 98 26 46 91 37D. 91 37 46 98 26答D5個(gè)數(shù)3進(jìn)制第一次執(zhí)行到36行時(shí)只是按照這5個(gè)數(shù)字在3進(jìn)制下的第0位從低到高進(jìn)行排序。數(shù)字在3進(jìn)制下第0位的數(shù)字為該數(shù)值除以3的余數(shù)十進(jìn)制數(shù)值98269137463進(jìn)制第0位數(shù)字22111由于排序是穩(wěn)定的因此相同數(shù)值按照原順序排列根據(jù)3進(jìn)制第0位數(shù)字排序后的結(jié)果為91 37 46 98 26選D。2.若 val[i]的最大值為 100k 取 時(shí)算法運(yùn)算次數(shù)最少。A. 2B. 3C. 10D. 不確定答D因?yàn)橛羞M(jìn)行n次的循環(huán)第29、31、35行該題沒有給出n是多少n的大小會影響運(yùn)算次數(shù)因此無法只靠k的大小決定運(yùn)算次數(shù)。3.當(dāng)輸入的 k 比 val[i]的最大值還大時(shí)該算法退化為 算法。A. 選擇排序B. 冒泡排序C. 計(jì)數(shù)排序D. 桶排序答C。當(dāng)k比val的最大值更大時(shí)m1相當(dāng)于所有val數(shù)組的數(shù)值在k進(jìn)制下只有1位數(shù)。val[j] / base % k的值就是val[j]cnt數(shù)組就是計(jì)數(shù)數(shù)組用來統(tǒng)計(jì)val數(shù)組中每個(gè)數(shù)值出現(xiàn)的次數(shù)。最后根據(jù)各個(gè)數(shù)值出現(xiàn)的次數(shù)輸出。這樣的排序算法是計(jì)數(shù)排序。桶排序是更大的概念凡是使用哈希函數(shù)將數(shù)值分到多個(gè)桶中的排序算法都可以算是桶排序。計(jì)數(shù)排序是一種特殊的桶排序基數(shù)排序是進(jìn)行了多趟的基數(shù)排序也可以歸類為桶排序。該題更準(zhǔn)確地說還是退化為計(jì)數(shù)排序。