原理

當(dāng)輸入的元素是n個(gè)0到k之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是Θ(n+k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍(等于待排序數(shù)組的最大值與最小值的差加上1)，這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。例如：計(jì)數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。

步驟

找出待排序的數(shù)組中最大和最小的元素

統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)

對(duì)所有的計(jì)數(shù)累加(從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加)

反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

代碼

defcount_sort(list):

min=2147483647

max=0

#取得最大值和最小值

forxinlist:

ifx

min=x

ifx>max:

max=x

#創(chuàng)建數(shù)組C

count=[0]*(max-min+1)

forindexinlist:

count[index-min]+=1

index=0

#填值

forainrange(max-min+1):

forcinrange(count[a]):

list[index]=a+min

index+=1

returnlist

以上內(nèi)容為大家介紹了Python計(jì)數(shù)排序，希望對(duì)大家有所幫助，如果想要了解更多Python相關(guān)知識(shí)，請(qǐng)關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。