【演算法筆記】計數排序 / 桶排序 / 基數排序

大家好我是 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）的時候，計數排序法就仍有效率排序。

計數排序的演算步驟如下：

找出要排序的數列當中之最大值
初始化一個長度為 max+1 的列表如 counting_list（因為我對 Python 最熟，故先用列表稱呼），所有元素都為 0。
將原本數列中的元素做「計數」，而將計數結果寫入 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 出現的次數。
進行 counting_list[i] = counting_list[i – 1] + counting_list[i]（項數跟前一項元素相加），讓每個元素存儲的是待排序數列中小於或等於該元素的數字個數。
將原始數列從末端開始迭代，根據 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）：

68747470733a2f2f332e62702e626c6f6773706f742e636f6d2f2d6a4a63686c7931426b54632f574c4771434644647643492f41414141414141414148412f6c756c6a416c7a3270744d6e64495a4e48304b4c545475514d4e73667a44654651434c63422f73313630

在 Count Array C. 對原始數列做前綴和這件事情：

68747470733a2f2f312e62702e626c6f6773706f742e636f6d2f2d785071796c6e67714153592f574c47713370396e3976492f414141414141414141484d2f4a48647458416b4a593877597a444d4258787161726a6d687050684d3075384d41434c63422f73313630

Python 實作

註：前綴和（prefix sum）就是前面講的 counting_list[i] = counting_list[i – 1] + counting_list[i]，目前項數與前項的和。

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

桶排序法（Bucket Sort）

看文字不懂？去看這支影片吧：How to Bucket Sort - Youtube

桶排序（Bucket Sort）很特別，跟以往的排序法用的演算方式不同，以往都是用比較排序，而桶排序則像是分配性的排序（非比較排序就對了）。

這個排序法適用於數值分佈範圍較小且資料相對均勻的情況。主要原理是將輸入資料分配到不同的「桶」（buckets）中，然後對每個桶內的資料進行單獨排序，最後再將所有桶內的資料合併，就能得到排序後的結果。

桶排序是一種拿空間換時間的排序法，桶排序的最佳和平均時間複雜度通常為 O(n + k)，但最壞情況可能會到 O(n^2)。

桶排序的演算步驟如下：

建桶：建立定量的桶子。桶子的數量取決於待排序的數列元素範圍和精度。通常桶子的數量等於待排序的數列元素個數（數列元素個數 -> 意即一個數列的長度）。
分配：根據範圍（比如說 0 ~ 10、11 ~ 19 …）將待排序數列中的元素插入到桶中。
- 從待排序數列中取出每個元素。
- 將元素乘以桶數列的長度。
- 將結果（元素乘以桶數列的長度）轉換為整數（若有小數點就把小數點去掉，只留整數），可做為桶數列的索引。
- 將元素放入桶中，索引為之前計算出來的。
- 不斷重複上述步驟
桶內排序：將每個非空桶內的元素進行排序。
- 排序法用穩定的排序法下去排序（如：Bubble Sort、Merge Sort 等）
合併：收集每個非空桶中的元素並將其放回原始數列當中。
- 按順序迭代每個桶。
- 將桶中的每個單獨元素插入原始數列中。
- 一旦一個元素被複製，就會從桶中刪除。
- 對所有桶重複此過程，直到收集完所有元素。

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

基數排序法（Radix Sort）

看文字不懂？去看這支影片吧：Radix Sort | GeeksforGeeks - Youtube

基數排序法（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]

找到數列當中最大的元素，即 802。因為它有 3 位數，所以進行 3 次排序。
第一輪（第一次排序）按個位數排序：
- 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) 是這些數字的個位數。
第二輪（第二次排序）按十位數排序：
- 802 (0), 2 (0), 24 (2), 45 (4), 66 (6), 170 (7), 75 (7), 90 (9)
- 排序後：802, 2, 24, 45, 66, 170, 75, 90
第三輪（第三次排序）按百位數排序：
- 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 實作

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

總結

排序法	計數排序法（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
適用情況	資料範圍小且為整數值	資料均勻分布	資料為整數或固定長度的字符串、資料範圍大但位數少
優點	線性時間複雜度、簡單易做、穩定	對均勻分布的資料效率高	對小數字有效、穩定
缺點	不適用於浮點數或大範圍資料、需要額外空間儲存計數數列	空間複雜度高、效率依賴於資料的分布	需要知道資料的範圍和位數、對於大範圍的資料不如計數排序快