計數排序

什么是計數排序

• 

?

?

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

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

實例講解

現有列表：

1 3 2 4 1 2 3 1 3 5

首先建一個列表（元素為下標），接下來遍歷計數每個元素有多少個，創建一個新列表存儲數量。

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

（列表寫的簡化，見諒）

代碼的實現

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

?

計數排序的時間復雜度

第一層循環count“+”了n次，第二層是append“+”n次，兩層循環循環加起來是2n，因此時間復雜度為O(n)