計數器排序是是一種簡單直觀且穩定的排序算法。如果已知一個輸入數組中的元素x，我們知道了這個數組中比x小的元素的個數，那么我們就可以直接把x放到（x+1）的位置上，這就是計數排序的基本思想。在計數器排序中，單個元素的次序主要依賴於他們之間的比較，所以這一類的排序算法也屬於比較排序的一種。基於這個思想，計數排序的一個主要問題就是如何統計數組中元素的個數。
如果當存在幾個相同的元素時，則需要對排序進行做適當的調整，因為不能把所有的元素放到同一個位置上。
基本介紹
- 中文名：計數器排序
- 外文名：Sorting by counter
- 類型：排序算法
- 分類：計算機科學-排序算法-比較排序
原理,實現原理,實現步驟,實現語言,其他信息,
原理
計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。
實現原理
為一組數在排序之前先統計這組數中其他數小於這個數的個數，則可以確定這個數的位置。例如要排序的數為 7 4 2 1 5 3 1 5；則比7小的有7個數，所有7應該在排序好的數列的第八位，同理3在第四位，對於重複的數字，1在1位和2位（暫且認為第一個1比第二個1小），5和1一樣位於6位和7位。
實現步驟
（1）創建關鍵值（計數列表）
（2）遍歷序列中的每一個元素，相應的計數器增加1
（3）重新將元素存儲列表中
實現語言
Python語言
def sort(l):
n = len(l)
res = [None] * n
# 首次循環遍歷, 每個列表的數都統計
for i in range(n):
# p 表示 a[i] 大於列表其他數 的次數
p = 0
# q 表示 等於 a[i] 的次數
q = 0
# 二次循環遍歷, 列表中的每個數都和首次循環的數比較
for j in range(n):
if l[i] > l[j]:
p += 1
elif l[i] == l[j]:
q += 1
for k in range(p, p+q): # q表示 相等的次數,就表示, 從 P 開始索引後, 連續 q 次,都是同樣的 數
res[k] = l[i]
return res
print(sort([5,5,5,4,3,54,6,76,34,31,9,43,7,12,11,3]))
#輸出結果 [3, 3, 4, 5, 5, 5, 6, 7, 9, 11, 12, 31, 34, 43, 54, 76]
其他信息
計數排序的一個重要性質是穩定性，具有相同值的元素在輸出數組中的相對次序與輸入數組數組中的次序相同。這種穩定性在進行排序的數據電郵衛星數據的時候比較重要。
