摘要訊息 : 比桶排序法節省空間的排序演算法.
0. 前言
桶排序法 (《【演算法】桶排序法 (Bucket Sort)》) 的缺點非常明顯, 當元素的範圍非常大的時候, 需要配置的空間可能超過記憶體容量. 另外, 如果大量元素集中在某個區間, 剩下元素的分佈十分不均勻的話, 可能導致大量記憶體是空閒的. 為了解決這個問題, 我們就需要改進桶排序法.
本篇文章中, 我們主要討論的是升序的基數排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.
更新紀錄 :
- 2022 年 4 月 30 日進行第一次更新和修正.
1. 以基數為基礎的空間
現在我們要求被排序的集合 S 中的數字必須是整型數字, 而不能再是英文字母這些. 因為如果要以基數為基礎配置空間, 那麼被排序的元素必須可以被分解為基數.
任何數字都可以被分解. 以基數為 10 為例, 數字 928 可以被分解為 9×100+2×10+8×1. 如果基數改為 12, 那麼 928 可以被分解為 7×120+7×12+4×1. 我們可以發現, 如果基數為 r, 那麼任意數字 α 可以被分解為 α=⌊rn−1αmodrn⌋×rn+⌊rn−2αmodrn−1⌋×rn−1+...+⌊r0αmodr1⌋×r0=αmodr×r0+⌊rαmodr2⌋×r1+...+⌊rn−1αmodrn⌋×rn, 得到分解後的集合 {αmodr,⌊rαmodr2⌋,...,⌊rn−1αmodrn⌋}. 接下來的排序就以這個分解之後的集合為基礎.
如果基數是 r, 那麼我們就配置 r 個連結串列, 而不是 r 個輔助空間. 因為一般來說, 基數可能遠小於集合中最大的那個元素, 所以可能存在大量的重複. 另外, 此處我們配置的是連結串列 (《【資料結構】連結串列》) 而不是前向連結串列 (《【資料結構】前向連結串列》) 的原因在於我們每次插入都是在尾部, 這個連結串列可以很快做到, 但是前向連結串列卻需要尋訪所有元素.
還有一個問題就是對集合中任意的數字分解之後, 分解集合 {αmodr,⌊rαmodr2⌋,...,⌊rn−1αmodrn⌋} 中元素的數量可能存在不同. 例如某個集合中最小的元素 24=2×101+2×100, 而最大的元素 124=1×102+2×101+2×100. 也就是說, 對於 24 的分解集合是 {4,2}, 124 的分解集合是 {4,2,1}. 為了解決這個問題, 我們將 24 視為 24=0×102+2×101+2×100. 這樣, 24 的分解集合就應該是 {4,2,0}.
2. 基數排序法
對於十以內的非負整數, 大家在手動進行排序的時候, 肯定按照數字的大小進行. 對於一百以內的非負整數, 大家在排序的時候可以先對個位進行排序, 個位排好序之後按個位數的大小合併元素到一個新的集合, 再對十位進行排序. 這個時候, 由於數字已經先按照了個位排序, 所以在按照十位進行排序之後, 那些十位相同的數字就會局部有序. 那些十位不相同的數字, 會按照十位的大小從小到大進行排列, 由於個位已經局部有序, 所以這些一百以內的非負整數整體有序. 對於一千以內一萬以內等等的非負整數也是類似, 按照個位十位百位前位等進行排序, 最終就會使得集合中的數字有序.
一般來說, 上面的說法是針對基數為 10, 即 r=10 的情況. 但是對於任意的正整數 r, 上面的排序方法仍然成立. 至於如何進行分解, 第 1 節中的分解集合便派上了用場.
Algorithm 1. 基數排序法
我們稱 Algorithm 1 為基數排序法 (radix sort).
例題 1. 設集合 S={216,521,425,116,91,515,124,34,96,24}, 使用 Algorithm 1 以基數 r=10 對 S 進行排序.
解 :
首先我們對個位進行排序 :
Figure 1-1. 按個位數進行排序
按順序合併之後, 有 S={521,91,124,34,24,216,116,96}. 繼續按照十位排序 :
Figure 1-2 按十位數進行排序
按順序合併之後有 S={515,216,116,521,124,24,425,34,91,96}. 繼續按照百位排序 :
Figure 1-3. 按百位數進行排序
按順序合併之後最終有 S={24,34,91,96,116,124,216,425,515,521}. 集合 S 有序.
■
3. 穩定性討論
顯然, 基數排序法是穩定的排序法, 而且必須是穩定的排序演算法. 其實基數排序法是否穩定, 取決於在連結串列插入新元素的時候, 是否在尾部插入. 如果基數排序法是不穩定的, 不妨假設在插入連結串列的時候是頭部插入的, 那麼像 S={521,515} 這樣的集合, 在按照個位數進行排序之後, 有 S={521,515}; 在按照十位數進行排序之後, 有 S={515,521}; 在按照百位數進行排序的時候, 如果我們是在頭部插入的元素, 那麼合併之後有 S={521,515}. 也就是我們按照集合中的順序, 先插入了 515, 然後在頭部, 即 515 之前插入了 521. 這樣, 最終得到的集合並不是有序的. 所以, 基數排序法是穩定的排序演算法.
4. 複雜度分析
基數排序法需要按照基數 r 配置 r 個輔助性空間, 其餘操作的輔助性空間數量和元素數量 n 或者 r 都無關, 是常數級別的, 所以基數排序法的空間複雜度是 Θ(r). 這裡要注意, r 不一定滿足 r≤n, 所以我們不能簡單地認為基數排序法的空間複雜度是 O(n) 或者 Ω(n). 基數排序法需要尋訪集合 S 中的元素次數是 ⌈logrmaxS⌉×n 次, 所以時間複雜度應該是 Θ(n). 這裡又要注意, 雖然基數排序法和桶排序法的時間複雜度都是 Θ(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
即可.