對於桶排序法, 如果給出的數據範圍太大, 以至於超過了記憶體的最大容量, 那麼顯然排序無法在這台電腦上完成. 另外, 就算數據範圍沒有超過記憶體最大容量, 但是排序的數據比較少, 我們仍然要大面積地配置記憶體以供桶排序法使用, 並且其中絕大部分的記憶體都是被浪費的. 因此, 我們既希望使用空間換取時間, 但是又不至於大面積地浪費記憶體. 於是, 被改進過的桶排序 - 基數排序法就誕生了

和桶排序法一樣, 被用於基數排序法的數據必須可以被轉型為整形型別, 因為我們要將數字按照某一個基數將其分解, 然後分別對分解之後的數字進行排序

以 10 為例, 令基數為 10, 那麼任何數字都可以被分解為若干個 0 - 9 之間的數字; 令基數為 15, 那麼任何數字都可以被分解為若干個 0 - 14 之間的數字

分解數字需要除法和取餘數, 對於任意基數 r 和任意數字 \alpha, 可以將其分解為

\alpha \ \% \ r,\ \ \  (\alpha \ \% \ r^{2}) / r, \ \ \  (\alpha \ \% \ r^{3}) / r^{2}, \ \ \  ..., \ \ \  (\alpha \ \% \ r^{n}) / r^{n - 1}

以 928 為例, 使用這種方法, 我們可以將數字 928 以 10 為基數, 分解為 9、2、8 (即 928 = 9 * 10^{2} +  2 * 10^{1} + 8 * 10^{0}). 但是使用上面的順序, 我們得到的數字是 8、2、9, 也就是倒著的. 對於一組數字來說, 我們首先對最後一位進行排序, 然後對倒數第二位進行排序, ..., 直到對第一位進行排序, 這樣就得到了一個有序的序列. 這便是基數排序

和桶排序一樣, 我們同樣使用連結串列對數字進行排序 :

#include <forward_list>



using std::forward_list;



int radix_sort_power(int base, unsigned exponent) {

    if(not exponent) {

        return 1;

    }

    int result {1};

    while(true) {

        if(exponent % 2) {

            result *= base;

        }

        exponent /= 2;

        if(not exponent) {

            break;

        }

        base *= base;

    }

    return result;

}

inline typename forward_list<int>::const_iterator before_end(const forward_list<int> &list) {

    auto before_end {list.cbefore_begin()};

    const auto the_end {list.cend()};

    while(true) {

        auto next {before_end};

        if(++next == the_end) {

            return before_end;

        }

        ++before_end;

    }

}

void radix_sort(int arr[], int size, forward_list<int> &out_list, int radix = 10) {

    auto bucket {new forward_list<int>[radix]};

    forward_list<int> list;

    auto exponent {1};

    while(true) {

        auto flag {true};

        for(auto i {0}; i < size; ++i) {

            auto digit {(arr[i] % radix_sort_power(radix, exponent)) / radix_sort_power(radix, exponent - 1)};

            if(flag and digit) {

                flag = false;

            }

            bucket[digit].insert_after(before_end(bucket[digit]), arr[i]);

        }

        ++exponent;

        list.clear();

        if(flag) {

            out_list = move(bucket[0]);

            break;

        }

        for(auto i {0}; i < radix; ++i) {

            list.insert_after(before_end(list), bucket[i].cbegin(), bucket[i].cend());

            bucket[i].clear();

        }

        auto i {0};

        for(auto begin {list.cbegin()}, end {list.cend()}; begin not_eq end; ++begin) {

            arr[i++] = *begin;

        }

    }

    delete[] bucket;

}

函式 radix_sort_power 是用於計算乘方的函式, 裡面所使用的演算法並非直接相乘, 稍有優化, 但是這個演算法我們暫時不詳細解釋. 函式 before_end 用於獲得連結串列最後一個結點, 因為插入的位置是這個結點之後. 由於基數排序是桶排序的改進, 因此穩定性不可變, 這也是為了維護穩定性所必須的. 函式 radix_sort 除了宣告了一些必要的變數之外, 進入了一個無止盡的迴圈, 這個迴圈的終結由迴圈之內的變數 flag 決定. flag 表示如果這一次分解數字的結果都是 0, 那麼說明已經排序完成了. 一開始, flag 的值為 true, 當遇到分解的數字不為 0 時, flag 的值更變為 flase. 例如對於序列 {88, 1, 100, 2000}, 迴圈至多進行 5 次, 因為到了第五次, 分解的數字都為 0, 而第四次 88、1、100 分解的數字為 0, 但是 2000 分解的到的數字是 2, 所以此時還不能結束迴圈. 當每一個數字分解都得到 0, 那麼就會將所有的數字都歸入 bucket[0]

對於泛型的實作方式, 可以參考本人的 GitHub : GitHub 點擊直達, 搜尋 radix_sort