視覺化展示
計數陣列 (Count Array)
掃描與計數中
寫回陣列中
排序完成
400ms
演算法偽代碼
function countingSort(arr):
1 max_val = max(arr)
2 countArr = new Array(max_val + 1).fill(0)
3 for i = 0 to arr.length - 1:
4 countArr[arr[i]]++ // 計算各元素出現次數
5 target_idx = 0
6 for i = 0 to max_val:
7 while countArr[i] > 0:
8 arr[target_idx] = i // 依序寫回原陣列
9 countArr[i]--
10 target_idx++
操作原理
計數排序法 (Counting Sort) 是一種非比較型的排序演算法。它不依賴元素之間的比較，而是利用陣列的索引（Index）來記錄元素出現的次數。
它的核心思想是：找出陣列中的最大值 k，建立一個長度為 k+1 的新陣列（計數陣列）。接著走訪原本的陣列，每遇到一個數字，就在計數陣列對應的索引位置將次數加一。最後，按照計數陣列的順序和次數，依序將數字填回原本的陣列中，排序就完成了。
操作過程
- 找出最大值： 掃描整個陣列，找出其中的最大值
k。 - 建立計數陣列： 建立一個長度為
k+1的計數陣列，並將所有元素初始化為 0。 - 統計次數： 走訪原陣列，遇到數字
x，就將計數陣列索引為x的位置加 1。 - 寫回原陣列： 從頭掃描計數陣列，索引
i的位置值為c時，代表數字i出現了c次，依序將c個i寫回原陣列即可。
複雜度分析
- 時間複雜度(所有情況):
O(n + k)
其中n是陣列長度，k是陣列中的最大值。因為只需要走訪原陣列和計數陣列各一次，速度非常快（線性時間）。 - 空間複雜度(Space Complexity):
O(k)
需要一個額外的計數陣列，長度取決於原陣列中的最大數字k。如果k極大（例如數字包含一百萬），則會非常消耗記憶體，因此計數排序只適合用在資料範圍較小且集中的情況。