【演算法筆記】計數排序 / 桶排序 / 基數排序
===
目錄（Table of Contents）
[TOC]
---
大家好我是 LukeTseng！這篇是我的一個小小學習筆記，為了想要了解更快速的排序法，所以特別製作了此篇。
在總結部分會將這三種排序法的各個優缺點，以及其他屬性等等做比較。
總之廢話不多說，進入正題吧：
計數排序法（Counting Sort）
---
計數排序法（Counting Sort）是一個有線性時間成長的排序法，相較於以往較為基礎的泡沫排序法（Bubble Sort）、插入排序法（Insertion Sort）（時間複雜度：O(n^2)）等，或是適用於大資料且排序速度較快的排序法：快速排序法（Quick Sort）、合併排序法（Merge Sort）（時間複雜度：O(n log n)），都還要來得快。
它的時間複雜度是 O(n)，如果要準確一點說的話，是 O(n+k)，k 是資料量。
適用情況在於資料量少的時候，有多少呢？資料量在幾千個以內，且資料範圍不超過幾百個（例如 1 到 100 或 1 到 500）的時候，計數排序法就仍有效率排序。
計數排序的演算步驟如下：
1. 找出要排序的數列當中之最大值
2. 初始化一個長度為 max+1 的列表如 `counting_list`（因為我對 Python 最熟，故先用列表稱呼），所有元素都為 0。
3. 將原本數列中的元素做「計數」，而將計數結果寫入 `counting_list` 對應的索引值。
- 比如說原數列 = `[1,2,3,4,5,2,3,2,1,0,0]`，那就把裡面每個數字出現的次數算出來，稱為計數。然後因為最大值是 5，所以 counting_list 總共會有 6 項元素，索引值就等於原數列的數字（0~5）。最終 `counting_list = [2,2,2,2,1,1]`，裡面數字對應代表 0 ~ 5 出現的次數。
4. 進行 `counting_list[i] = counting_list[i – 1] + counting_list[i]`（項數跟前一項元素相加），讓每個元素存儲的是待排序數列中小於或等於該元素的數字個數。
5. 將原始數列從末端開始迭代，根據 `counting_list` 將每個元素放置到新的排序數列中，然後將對應的 `counting_list` 值減 1。
有關 5.，原始數列從末端開始迭代，
假設原數列 = `[1,2,3,4,5,2,3,2,1,0,0]`，則會從 0 開始，那這個 0 會去找 `counting_list` 索引為 0 的地方，然後將索引 0 的元素減 1，得到索引 1，再把 0 放到新的已排序數列的索引 1（從 `counting_list` 的元素 - 1 得來）。
接下來就以此類推，原始數列的下一個元素 0，同樣找到 `counting_list` 索引為 0 的元素，再扣 1，得到索引 0，放進去新的已排序數列的索引 0。
以下是計數排序的動圖以及說明（Source：[typescript-algorithms/src/algorithms/sorting/counting-sort/README.md at master · Lugriz/typescript-algorithms](https://github.com/Lugriz/typescript-algorithms/blob/master/src/algorithms/sorting/counting-sort/README.md)）：
在 Count Array C. 對原始數列做前綴和這件事情：
### Python 實作
註：前綴和（prefix sum）就是前面講的 `counting_list[i] = counting_list[i – 1] + counting_list[i]`，目前項數與前項的和。
```python=
def count_sort(input_array):
# 為 M 設定 input_array 的最大值
M = max(input_array)
# 把 count_array 所有元素設為 0，陣列長度為 M + 1
count_array = [0] * (M + 1)
# 作「計數」之動作，意即將 input_array 出現的數字之次數做計算
for num in input_array:
count_array[num] += 1
# 計算 count_array 的每個索引處的前綴和
for i in range(1, M + 1):
count_array[i] += count_array[i - 1]
# output_array 即為最終已排序之序列，此動作即為它做初始化
output_array = [0] * len(input_array)
# 開始進行排序，從 input_array 末端開始迭代
for i in range(len(input_array) - 1, -1, -1):
output_array[count_array[input_array[i]] - 1] = input_array[i]
count_array[input_array[i]] -= 1
return output_array
# 驅動程式之程式碼
if __name__ == "__main__":
# Input array
input_array = [4, 3, 12, 1, 5, 5, 3, 9]
# Output array
output_array = count_sort(input_array)
for num in output_array:
print(num, end=" ") # 1 3 3 4 5 5 9 12
```
Source：[Counting Sort - Data Structures and Algorithms Tutorials - GeeksforGeeks](https://www.geeksforgeeks.org/counting-sort/)
桶排序法（Bucket Sort）
---
看文字不懂？去看這支影片吧：[How to Bucket Sort - Youtube](https://www.youtube.com/watch?v=GAU102t5n4U)
桶排序（Bucket Sort）很特別，跟以往的排序法用的演算方式不同，以往都是用比較排序，而桶排序則像是分配性的排序（非比較排序就對了）。
這個排序法適用於數值分佈範圍較小且資料相對均勻的情況。主要原理是將輸入資料分配到不同的「桶」（buckets）中，然後對每個桶內的資料進行單獨排序，最後再將所有桶內的資料合併，就能得到排序後的結果。
桶排序是一種拿空間換時間的排序法，桶排序的最佳和平均時間複雜度通常為 O(n + k)，但最壞情況可能會到 O(n^2)。
桶排序的演算步驟如下：
1. 建桶：建立定量的桶子。桶子的數量取決於待排序的數列元素範圍和精度。通常桶子的數量等於待排序的數列元素個數（數列元素個數 -> 意即一個數列的長度）。
2. 分配：根據 ***範圍***（比如說 0 ~ 10、11 ~ 19 ...） 將待排序數列中的元素插入到桶中。
- 從待排序數列中取出每個元素。
- 將元素乘以桶數列的長度。
- 將結果（元素乘以桶數列的長度）轉換為整數（若有小數點就把小數點去掉，只留整數），可做為桶數列的索引。
- 將元素放入桶中，索引為之前計算出來的。
- 不斷重複上述步驟
3. 桶內排序：將每個非空桶內的元素進行排序。
- 排序法用穩定的排序法下去排序（如：Bubble Sort、Merge Sort 等）
4. 合併：收集每個非空桶中的元素並將其放回原始數列當中。
- 按順序迭代每個桶。
- 將桶中的每個單獨元素插入原始數列中。
- 一旦一個元素被複製，就會從桶中刪除。
- 對所有桶重複此過程，直到收集完所有元素。
### Python 實作
```python=
def insertion_sort(bucket):
for i in range(1, len(bucket)):
key = bucket[i]
j = i - 1
while j >= 0 and bucket[j] > key:
bucket[j + 1] = bucket[j]
j -= 1
bucket[j + 1] = key
def bucket_sort(arr):
n = len(arr)
buckets = [[] for _ in range(n)]
# 把列表中的元素放進不同的桶子裡
for num in arr:
bi = int(n * num)
buckets[bi].append(num)
# 用插入排序法對個別的桶子排序
for bucket in buckets:
insertion_sort(bucket)
# 將所有桶子連接到 arr[]
index = 0
for bucket in buckets:
for num in bucket:
arr[index] = num
index += 1
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
bucket_sort(arr)
print("Sorted array is:")
print(" ".join(map(str, arr)))
```
Source：[Bucket Sort - Data Structures and Algorithms Tutorials - GeeksforGeeks](https://www.geeksforgeeks.org/bucket-sort-2/)
基數排序法（Radix Sort）
---
看文字不懂？去看這支影片吧：[Radix Sort | GeeksforGeeks - Youtube](https://www.youtube.com/watch?v=nu4gDuFabIM)
基數排序法（Radix Sort）是一種線性排序演算法，有基於「按位數排序」的概念。
這個排序法會把每個元素看作是由多個「位數」組成，並從最低有效位數（Least Significant Digit, LSD）到最高有效位數（Most Significant Digit, MSD）逐位進行排序。經過多次穩定的排序，得出完整的已排序數列。
基數排序的時間複雜度為 O(d*(n+k))，其中 d 是位數的數量，n 是數據的數量，k 是每位數的取值範圍（如十進制數的 k = 10）。
基數排序的演算步驟如下：
假設待排序數列 `a = [170, 45, 75, 90, 802, 24, 2, 66]`
1. 找到數列當中最大的元素，即 802。因為它有 3 位數，所以進行 3 次排序。
2. 第一輪（第一次排序）按個位數排序：
- 170 (0), 90 (0), 802 (2), 2 (2), 24 (4), 45 (5), 75 (5), 66 (6)
- 排序後：170, 90, 802, 2, 24, 45, 75, 66
- 註：(0)、(2) 是這些數字的個位數。
3. 第二輪（第二次排序）按十位數排序：
- 802 (0), 2 (0), 24 (2), 45 (4), 66 (6), 170 (7), 75 (7), 90 (9)
- 排序後：802, 2, 24, 45, 66, 170, 75, 90
4. 第三輪（第三次排序）按百位數排序：
- 2 (002), 24 (024), 45 (045), 66 (066), 75 (075), 90 (090), 170 (170), 802 (802)
- 排序後：2, 24, 45, 66, 75, 90, 170, 802（排序完成）
### Python 實作
```python=
def countingSort(arr, exp1):
n = len(arr)
# 將 output 列表設與 arr 長度相同
output = [0] * (n)
# 初始化 count 列表全為 0
count = [0] * (10)
# 將原始數列的元素之出現次數儲存在 count[]
for i in range(0, n):
index = arr[i] // exp1
count[index % 10] += 1
# 計算前綴和，確保已排序元素出現在實際位置上
for i in range(1, 10):
count[i] += count[i - 1]
# Build the output array
i = n - 1
while i >= 0:
index = arr[i] // exp1
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# 將 output[] 賦值給 arr[]
i = 0
for i in range(0, len(arr)):
arr[i] = output[i]
def radixSort(arr):
# 尋找最大值以此確認最大位數
max1 = max(arr)
# 對每個數字進行計數排序。注意，傳遞的不是數字，而是 exp
# exp 是 10^i（10 的 i 次方），其中 i 是當前數字，也就是 exp 的數值
# LukeTseng 補：exp 代表著幾位數的意思，exp = 1 就是個位數, 2 = 十位數，以此類推
exp = 1
while max1 / exp >= 1:
countingSort(arr, exp)
exp *= 10
# Driver code
arr = [170, 45, 75, 90, 802, 24, 2, 66]
# Function Call
radixSort(arr)
for i in range(len(arr)):
print(arr[i], end=" ")
```
Source：[Radix Sort - Data Structures and Algorithms Tutorials - GeeksforGeeks](https://www.geeksforgeeks.org/radix-sort/)
總結
===
| **排序法** | **計數排序法（Counting Sort）** | **桶排序法（Bucket Sort）** | **基數排序法（Radix Sort）** |
| -------- | -------- | -------- | -------- |
| **基本原理** | 根據數字出現的頻率來排序 | 將數據分散到多個桶中，桶內排序後合併 | 基於數位位置的多次穩定排序 |
| **時間複雜度** | O(n + k) | 最佳 / 平均：O(n + k)；最壞：O(n^2) | O(d*(n + k)) |
| **空間複雜度** | O(k) | O(n + k) | O(n + k) |
| **穩定性** | Y | Y | Y |
| **原地演算法** | N | N | N |
| **適用情況** | 資料範圍小且為整數值 | 資料均勻分布 | 資料為整數或固定長度的字符串、資料範圍大但位數少 |
| **優點** | 線性時間複雜度、簡單易做、穩定 | 對均勻分布的資料效率高 | 對小數字有效、穩定 |
| **缺點** | 不適用於浮點數或大範圍資料、需要額外空間儲存計數數列 | 空間複雜度高、效率依賴於資料的分布 | 需要知道資料的範圍和位數、對於大範圍的資料不如計數排序快 |
原地演算法（或稱就地演算法：in-place algorithm）：簡單來說就是空間複雜度很低的演算法，通常是 O(1)，因為它只在原始資料結構上進行修改，不需要額外的空間來儲存中間結果。
參考資料
===
[Counting Sort - Data Structures and Algorithms Tutorials - GeeksforGeeks](https://www.geeksforgeeks.org/counting-sort/)
[[演算法]計數排序(Counting sort). 原理 | by 安安我里夫啦 | Medium](https://medium.com/@ananimziv/%E6%BC%94%E7%AE%97%E6%B3%95-%E8%A8%88%E6%95%B8%E6%8E%92%E5%BA%8F-counting-sort-0883c36a77ac)
[演算法學習筆記：計數排序（Counting Sort）、基數排序（Radix Sort） - 拉爾夫的技術隨筆 - Medium](https://medium.com/@ralph-tech/%E6%BC%94%E7%AE%97%E6%B3%95%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-%E8%A8%88%E6%95%B8%E6%8E%92%E5%BA%8F-counting-sort-%E5%9F%BA%E6%95%B8%E6%8E%92%E5%BA%8F-radix-sort-5b0c8e596f81)
[Bucket Sort - Data Structures and Algorithms Tutorials - GeeksforGeeks](https://www.geeksforgeeks.org/bucket-sort-2/)
[桶排序 Bucket sort - Rust Algorithm Club](https://rust-algo.club/sorting/bucket_sort/)
[iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天](https://ithelp.ithome.com.tw/m/articles/10279536)
[[演算法]桶排序(Bucket sort) - 安安我里夫啦 - Medium](https://medium.com/@ananimziv/%E6%BC%94%E7%AE%97%E6%B3%95-%E6%A1%B6%E6%8E%92%E5%BA%8F-bucket-sort-11f01fbd425d)
[Radix Sort - Data Structures and Algorithms Tutorials - GeeksforGeeks](https://www.geeksforgeeks.org/radix-sort/)
[基數排序 Radix sort - Rust Algorithm Club](https://rust-algo.club/sorting/radix_sort/index.html)
[[演算法] 學習筆記 — 13. 基數排序法 Radix Sort | by Amber Fragments | Medium](https://medium.com/@amber.fragments/%E6%BC%94%E7%AE%97%E6%B3%95-%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-13-%E5%9F%BA%E6%95%B8%E6%8E%92%E5%BA%8F%E6%B3%95-radix-sort-45317967ad03)
Sign in with Wallet
Connect another wallet