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

0. 前言

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

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

更新紀錄 :

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

1. 以基數為基礎的空間

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

任何數字都可以被分解. 以基數為 1010 為例, 數字 928928 可以被分解為 9×100+2×10+8×1.\displaystyle {9 \times 100 + 2 \times 10 + 8 \times 1}. 如果基數改為 1212, 那麼 928928 可以被分解為 7×120+7×12+4×1.\displaystyle {7 \times 120 + 7 \times 12 + 4 \times 1}. 我們可以發現, 如果基數為 rr, 那麼任意數字 α\alpha 可以被分解為 α=αmod  rnrn1×rn+αmod  rn1rn2×rn1+...+αmod  r1r0×r0=αmod  r×r0+αmod  r2r×r1+...+αmod  rnrn1×rn,\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}} 得到分解後的集合 {αmod  r,αmod  r2r,...,αmod  rnrn1}\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 \}. 接下來的排序就以這個分解之後的集合為基礎.

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

還有一個問題就是對集合中任意的數字分解之後, 分解集合 {αmod  r,αmod  r2r,...,αmod  rnrn1}\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×101+2×10024 = 2 \times 10^{1} + 2 \times 10^{0}, 而最大的元素 124=1×102+2×101+2×100124 = 1 \times 10^{2} + 2 \times 10^{1} + 2 \times 10^{0}. 也就是說, 對於 2424 的分解集合是 {4,2}\left \{ 4, 2 \right \}, 124124 的分解集合是 {4,2,1}\left \{ 4, 2, 1 \right \}. 為了解決這個問題, 我們將 2424 視為 24=0×102+2×101+2×10024 = 0 \times 10^{2} + 2 \times 10^{1} + 2 \times 10^{0}. 這樣, 2424 的分解集合就應該是 {4,2,0}\left \{ 4, 2, 0 \right \}.

2. 基數排序法

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

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

Algorithm 1. 基數排序法

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

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

:

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

Figure 1-1. 按個位數進行排序

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

Figure 1-2 按十位數進行排序

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

Figure 1-3. 按百位數進行排序

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

\blacksquare

3. 穩定性討論

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

4. 複雜度分析

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

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