原理

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

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

步驟

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

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

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

反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個元素就將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計數(shù)排序，希望對大家有所幫助，如果想要了解更多Python相關(guān)知識，請關(guān)注IT培訓(xùn)機(jī)構(gòu):千鋒教育。