計數排序是一種簡單高效的排序算法，它屬於非比較型排序算法，特別適用於整數排序，尤其是當數據的取值範圍不大時。相比於冒泡排序、選擇排序等基於比較的排序算法，計數排序通過統計元素出現的次數來確定元素的最終位置，從而實現排序，時間複雜度可以達到線性級別（O(n + k)，其中n是待排序元素的個數，k是數據的取值範圍）。
基本思路¶
- 確定數據範圍：首先找出待排序數組中的最小值和最大值，這樣我們就能確定需要統計的元素範圍，避免創建過大的計數數組。
- 統計元素出現次數：創建一個計數數組，長度爲（最大值 - 最小值 + 1），用於記錄每個元素出現的次數。
- 構建排序結果：根據計數數組的統計結果，從最小值開始，依次輸出每個元素，輸出的次數等於該元素在計數數組中記錄的次數。
示例演示¶
以數組 [4, 2, 2, 8, 3, 3, 1] 爲例，演示計數排序的過程：
- 確定數據範圍：數組中的最小值是
1，最大值是8，因此數據範圍是1~8，計數數組長度爲8 - 1 + 1 = 8。 - 統計元素次數：遍歷原數組，統計每個元素出現的次數：
- 元素1出現 1 次
- 元素2出現 2 次
- 元素3出現 2 次
- 元素4出現 1 次
- 元素8出現 1 次
- 其他元素（5、6、7）出現 0 次
因此計數數組爲[1, 2, 2, 1, 0, 0, 0, 1]（索引 0~7 分別對應 1~8 的次數）。 - 構建排序結果：從最小值
1開始，依次輸出計數數組中每個元素的次數：
- 輸出1一次 →[1]
- 輸出2兩次 →[1, 2, 2]
- 輸出3兩次 →[1, 2, 2, 3, 3]
- 輸出4一次 →[1, 2, 2, 3, 3, 4]
- 輸出8一次 →[1, 2, 2, 3, 3, 4, 8]
Python 實現¶
def counting_sort(arr):
# 處理空數組或單元素數組（無需排序）
if not arr:
return []
if len(arr) == 1:
return arr
# 步驟1：確定最小值和最大值
min_val = min(arr)
max_val = max(arr)
# 步驟2：創建計數數組（長度爲最大值-最小值+1，初始化爲0）
count_size = max_val - min_val + 1
count = [0] * count_size
# 步驟3：統計每個元素出現的次數
for num in arr:
# 計算當前元素在計數數組中的索引（元素值 - 最小值）
index = num - min_val
count[index] += 1 # 對應元素出現次數+1
# 步驟4：根據計數數組生成排序結果
sorted_arr = []
for i in range(count_size):
# 當前元素值 = 最小值 + 計數數組索引
num = min_val + i
# 將當前元素重複 count[i] 次添加到結果數組
sorted_arr.extend([num] * count[i])
return sorted_arr
代碼解釋¶
- 邊界處理：如果輸入數組爲空或只有一個元素，直接返回原數組（無需排序）。
- 數據範圍確定：通過
min()和max()獲取數組的最小值和最大值，避免創建過大的計數數組。 - 計數數組構建：長度爲
max_val - min_val + 1，確保覆蓋所有可能的元素。 - 統計次數：遍歷原數組，對每個元素計算其在計數數組中的索引（
num - min_val），並累加次數。 - 生成結果：從最小值開始，按順序輸出每個元素，輸出次數由計數數組中對應位置的值決定。
適用場景與特點¶
- 適用場景：數據爲整數且取值範圍較小（如考試分數、年齡等），或存在大量重複元素時。
- 穩定性：計數排序是穩定排序（相等元素的相對順序在排序後保持不變），因爲重複元素會按原順序依次輸出。
- 內存佔用：若數據範圍過大（如最大值遠大於最小值），計數數組會佔用較多內存，此時可能不適用。
測試示例¶
# 測試用例1：基礎整數數組
arr1 = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr1)) # 輸出：[1, 2, 2, 3, 3, 4, 8]
# 測試用例2：包含負數的數組
arr2 = [-3, 1, 2, -3, 0]
print(counting_sort(arr2)) # 輸出：[-3, -3, 0, 1, 2]
通過上述步驟，計數排序能高效地對整數數組進行排序，尤其適合數據範圍小且重複元素多的場景。