如果記憶體可以無限, 那麼就可以考慮一種使用空間來換時間的排序法, 也就是桶排序法. 假如排序的範圍是 [m, n], 其中 n > m, 那麼只要宣告 n - m + 1 個序列就可以了. 我們將範圍 [m, n] 影射為 [0, n - m], 如果存在一個值屬於 [m, n] 的序列中, 不妨設這個值為 i, 那麼將 i 影射到範圍 [0, n - m] 中, 不妨設這個值為 j, 那麼只要將這個值插入到第 j 個位置就可以了

由於每一個位置不一定只放置一個元素, 因此要求這個序列的每一個元素又是一個序列, 簡單地來說, 就是陣列的陣列. 接著, 我們需要考慮, 使用怎樣的序列來存儲它們. 首先, 對於範圍 [0, n - m], 可以直接使用內建的陣列, 但是可能需要一個影射函式將原本的 [m, n] 的範圍影射到 [0, n - m] 中. 如果陣列裡面存儲一個陣列, 在 C++ 下, 我們就需要額外的一個陣列來存儲 n - m + 1 個元素, 因為 C++ 中的陣列並不可以直接指派給另外一個陣列. 而使用非線性的資料結構又顯得小題大作, 因此, 我們考慮使用連結串列

我們可以使用一個連結串列的陣列. 當所有的元素都被放入對應的連結串列之後, 我們考慮將所有的連結串列拼接在一起

假如給定的序列範圍是 [0, 7], 集合 \mathscr{X} = \left \{0,2,1,5,7,3,4,3,0\right \}. 那麼對於任意 x \in \mathscr{X}, 只要將其插入到第 x 個陣列的連結串列中就可以了.

我們再來考慮排序的穩定性, 由於一個連結串列中的元素都相同, 只要將後進來的元素插入到連結串列的最後部分, 那麼就可以保持元素的穩定性, 這確實是比直接在最前面插入要慢一些, 但是為了維護穩定性, 總要付出一些代價

最後, 我們考慮影射函式. 對於一個範圍 [m, n] 來說, 如果 m = 0, 那麼就可以直接對 [0, n] 範圍內的陣列進行操作; 如果 m > 0, 範圍要整體向前偏移 m, 也就是對於任意的 i \in \left [ m, n \right ], 影射函式將其影射為 i = i - m; 如果 m < 0, 範圍要整體向後偏移 \left | m\right |, 也就是說對於任意的 i \in \left [ m, n \right ], 影射函式將其影射為 i = i + -m = i + |m| :

有了上述兩個函式作為輔助, 我們可以寫出桶排序法的程式碼 :

#include <algorithm>

#include <forward_list>



using namespace std;



int mapping(int x, int base) {

    return base ? (base > 0 ? x - base : x + -base) : x;

}

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

    auto begin {list.cbefore_begin()};

    while(true) {

        auto after_begin {begin};

        ++after_begin;

        if(after_begin == list.cend()) {

            return begin;

        }

        ++begin;

    }

}

forward_list<int> bucket_sort(int arr[], int size) {

    const auto max {*max_element(arr, arr + size)};

    const auto min {*min_element(arr, arr + size)};

    const auto range {max - min + 1};

    auto list_array {new forward_list<int>[range]};

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

        auto index {mapping(arr[i], min)};

        list_array[index].insert_after(before_last(list_array[index]), arr[i]);

    }

    forward_list<int> r {};

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

        r.merge(list_array[i]);

    }

    delete[] list_array;

    return r;

}

其中, 我們採用標準程式庫中的 forward_list 作為使用的連結串列. std::forward_list 並沒有直接相接結點的函式, 因此我們暫時使用其成員函式 merge 替代. max_elementmin_element 函式都來自於標頭檔 <algorithm>, 用於檢測給定的序列中最大或著最小的元素

需要指出, 這種排序是有限定的適用範圍的. 對於資料型別, 我們要求其必須能夠向整數型別轉換, 否則這個排序很可能就無法成立

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