計數(shù)排序

什么是計數(shù)排序

計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

簡單來說計數(shù)排序就是對對列表進(jìn)行排序，已知列表中的范圍數(shù)都在0~100之間。設(shè)計時間復(fù)雜度為O(n)的算法。

實例講解

現(xiàn)有列表：

1 3 2 4 1 2 3 1 3 5

首先建一個列表（元素為下標(biāo)），接下來遍歷計數(shù)每個元素有多少個，創(chuàng)建一個新列表存儲數(shù)量。

0??? 0

1??? 0

2??? 0

3??? 0

4??? 0

5??? 0

第一次：

0??? 0

1??? 1

2??? 0

3??? 0

4??? 0

5??? 0

第二次

0??? 0

1??? 1

2??? 0

3??? 1

4??? 0

5??? 0

……

最后

0??? 0

1??? 3

2??? 2

3??? 3

4??? 1

5??? 1

接下來得到最終列表：

1 1 1 2 2 3 3 3 4 5

（列表寫的簡化，見諒）

代碼的實現(xiàn)

def count_sort(lst,max_count=100): ?# 傳入列表和最大值
?
? ? count = [0 for i in range(max_count+1)] ?# 計數(shù)列表
?
? ? for val in lst:
?
? ? ? ? count[val] += 1 ?# val即為下標(biāo)
?
? ? lst.clear() ?# 寫到lst中之前需要情況lst
?
? ? for ind,val in enumerate(count): ?# 下標(biāo)和值
?
? ? ? ? for i in range(val): ?# 查看個數(shù)并增加到列表中
?
? ? ? ? ? ? lst.append(ind)
?
?
?
import random
?
lst1 = [random.randint(0,5) for i in range(10)]
?
print(lst1)
?
count_sort(lst1)
?
print(lst1)
?
# 輸出結(jié)果
?
# [2, 2, 0, 1, 4, 3, 5, 4, 0, 3]
?
# [0, 0, 1, 2, 2, 3, 3, 4, 4, 5]