摘要訊息 : 比桶排序法節省空間的排序演算法.

0. 前言

桶排序法 (《【演算法】桶排序法 (Bucket Sort)》) 的缺點非常明顯, 當元素的範圍非常大的時候, 需要配置的空間可能超過記憶體容量. 另外, 如果大量元素集中在某個區間, 剩下元素的分佈十分不均勻的話, 可能導致大量記憶體是空閒的. 為了解決這個問題, 我們就需要改進桶排序法.

本篇文章中, 我們主要討論的是升序的基數排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.

更新紀錄 :

• 2022 年 4 月 30 日進行第一次更新和修正.

1. 以基數為基礎的空間

現在我們要求被排序的集合 $\mathscr {S}$ 中的數字必須是整型數字, 而不能再是英文字母這些. 因為如果要以基數為基礎配置空間, 那麼被排序的元素必須可以被分解為基數.

任何數字都可以被分解. 以基數為 $10$ 為例, 數字 $928$ 可以被分解為 $\displaystyle {9 \times 100 + 2 \times 10 + 8 \times 1}.$ 如果基數改為 $12$, 那麼 $928$ 可以被分解為 $\displaystyle {7 \times 120 + 7 \times 12 + 4 \times 1}.$ 我們可以發現, 如果基數為 $r$, 那麼任意數字 $\alpha$ 可以被分解為 $\displaystyle {\begin {aligned} \alpha &= \left \lfloor \frac {\alpha \mod r^{n}}{r^{n - 1}} \right \rfloor \times r^{n} + \left \lfloor \frac {\alpha \mod r^{n - 1}}{r^{n - 2}} \right \rfloor \times r^{n - 1} + ... + \left \lfloor \frac {\alpha \mod r^{1}}{r^{0}} \right \rfloor \times r^{0} \\ &= \alpha \mod r \times r^{0} + \left \lfloor \frac {\alpha \mod r^{2}}{r} \right \rfloor \times r^{1} + ... + \left \lfloor \frac {\alpha \mod r^{n}}{r^{n - 1}} \right \rfloor \times r^{n}, \end {aligned}}$ 得到分解後的集合 $\left \{ \alpha \mod r, \left \lfloor \frac {\alpha \mod r^{2}}{r} \right \rfloor, ..., \left \lfloor \frac {\alpha \mod r^{n}}{r^{n - 1}} \right \rfloor \right \}$. 接下來的排序就以這個分解之後的集合為基礎.

如果基數是 $r$, 那麼我們就配置 $r$ 個連結串列, 而不是 $r$ 個輔助空間. 因為一般來說, 基數可能遠小於集合中最大的那個元素, 所以可能存在大量的重複. 另外, 此處我們配置的是連結串列 (《【資料結構】連結串列》) 而不是前向連結串列 (《【資料結構】前向連結串列》) 的原因在於我們每次插入都是在尾部, 這個連結串列可以很快做到, 但是前向連結串列卻需要尋訪所有元素.

還有一個問題就是對集合中任意的數字分解之後, 分解集合 $\displaystyle {\left \{ \alpha \mod r, \left \lfloor \frac {\alpha \mod r^{2}}{r} \right \rfloor, ..., \left \lfloor \frac {\alpha \mod r^{n}}{r^{n - 1}} \right \rfloor \right \}}$ 中元素的數量可能存在不同. 例如某個集合中最小的元素 $24 = 2 \times 10^{1} + 2 \times 10^{0}$, 而最大的元素 $124 = 1 \times 10^{2} + 2 \times 10^{1} + 2 \times 10^{0}$. 也就是說, 對於 $24$ 的分解集合是 $\left \{ 4, 2 \right \}$, $124$ 的分解集合是 $\left \{ 4, 2, 1 \right \}$. 為了解決這個問題, 我們將 $24$ 視為 $24 = 0 \times 10^{2} + 2 \times 10^{1} + 2 \times 10^{0}$. 這樣, $24$ 的分解集合就應該是 $\left \{ 4, 2, 0 \right \}$.

2. 基數排序法

對於十以內的非負整數, 大家在手動進行排序的時候, 肯定按照數字的大小進行. 對於一百以內的非負整數, 大家在排序的時候可以先對個位進行排序, 個位排好序之後按個位數的大小合併元素到一個新的集合, 再對十位進行排序. 這個時候, 由於數字已經先按照了個位排序, 所以在按照十位進行排序之後, 那些十位相同的數字就會局部有序. 那些十位不相同的數字, 會按照十位的大小從小到大進行排列, 由於個位已經局部有序, 所以這些一百以內的非負整數整體有序. 對於一千以內一萬以內等等的非負整數也是類似, 按照個位十位百位前位等進行排序, 最終就會使得集合中的數字有序.

一般來說, 上面的說法是針對基數為 $10$, 即 $r = 10$ 的情況. 但是對於任意的正整數 $r$, 上面的排序方法仍然成立. 至於如何進行分解, 第 1 節中的分解集合便派上了用場.

我們稱 Algorithm 1 為基數排序法 (radix sort).

例題 1. 設集合 $\mathscr {S} = \left \{ 216, 521, 425, 116, 91, 515, 124, 34, 96, 24 \right \}$, 使用 Algorithm 1 以基數 $r = 10$ 對 $\mathscr {S}$ 進行排序.

$解$ :

首先我們對個位進行排序 :

按順序合併之後, 有 $\mathscr {S} = \left \{ 521, 91, 124, 34, 24, 216, 116, 96 \right \}$. 繼續按照十位排序 :

按順序合併之後有 $\mathscr {S} = \left \{ 515, 216, 116, 521, 124, 24, 425, 34, 91, 96 \right \}$. 繼續按照百位排序 :

按順序合併之後最終有 $\mathscr {S} = \left \{ 24, 34, 91, 96, 116, 124, 216, 425, 515, 521 \right \}$. 集合 $\mathscr {S}$ 有序.

$\blacksquare$

3. 穩定性討論

顯然, 基數排序法是穩定的排序法, 而且必須是穩定的排序演算法. 其實基數排序法是否穩定, 取決於在連結串列插入新元素的時候, 是否在尾部插入. 如果基數排序法是不穩定的, 不妨假設在插入連結串列的時候是頭部插入的, 那麼像 $\mathscr {S} = \left \{ 521, 515 \right \}$ 這樣的集合, 在按照個位數進行排序之後, 有 $\mathscr {S} = \left \{ 521, 515 \right \}$; 在按照十位數進行排序之後, 有 $\mathscr {S} = \left \{ 515, 521 \right \}$; 在按照百位數進行排序的時候, 如果我們是在頭部插入的元素, 那麼合併之後有 $\mathscr {S} = \left \{ 521, 515 \right \}$. 也就是我們按照集合中的順序, 先插入了 $515$, 然後在頭部, 即 $515$ 之前插入了 $521$. 這樣, 最終得到的集合並不是有序的. 所以, 基數排序法是穩定的排序演算法.

4. 複雜度分析

基數排序法需要按照基數 $r$ 配置 $r$ 個輔助性空間, 其餘操作的輔助性空間數量和元素數量 $n$ 或者 $r$ 都無關, 是常數級別的, 所以基數排序法的空間複雜度是 $\Theta(r)$. 這裡要注意, $r$ 不一定滿足 $r \leq n$, 所以我們不能簡單地認為基數排序法的空間複雜度是 $O(n)$ 或者 $\Omega(n)$. 基數排序法需要尋訪集合 $\mathscr {S}$ 中的元素次數是 $\left \lceil \log_{r}{\max \mathscr {S}} \right \rceil \times n$ 次, 所以時間複雜度應該是 $\Theta(n)$. 這裡又要注意, 雖然基數排序法和桶排序法的時間複雜度都是 $\Theta(n)$, 但是基數排序法顯然是比桶排序法要慢的, 這個慢取決於 $n$ 前面的係數, 這個係數在時間複雜度中是沒有體現的.

5. 實作

Code 1. 基數排序法
#include <list>
#include <cmath>

void radix_sort(int arr[], int size, int radix = 10) {
    auto bucket {new std::list<int>[radix] {}};
    auto m {static_cast<int>(std::ceil(log(*max_element(arr, arr + size)) / log(radix)))};
    for(auto i {1}; i <= m; ++i) {
        for(auto j {0}; j < size; ++j) {
            auto index {static_cast<int>(arr[j] % static_cast<int>(std::pow(radix, i)) / std::pow(radix, i - 1))};
            bucket[index].push_back(arr[j]);
        }
        auto cursor {arr};
        for(auto j {0}; j < radix; ++j) {
            while(not bucket[j].empty()) {
                *cursor++ = bucket[j].front();
                bucket[j].pop_front();
            }
        }
    }
    delete[] bucket;
}

對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 radix_sort 即可.