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

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. 實作

#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 即可.