摘要訊息 : 一種不依賴於元素比較的排序演算法.

0. 前言

如果有足夠多的空間來儲存元素, 那麼就可以考慮一種使用空間來換時間的排序法, 也就是桶排序法.

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

更新紀錄 :

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

1. 有序範圍空間

若要排序的集合 \mathscr {S} 中, 最大的元素為 n, 最小的元素為 m, 那麼我們可以為 \mathscr {S} 配置至少 n - m + 1 個空間. 我們將這些額外配置的輔助空間稱為桶 (bucket). 若 e \in \mathscr {S}, 則必定有 e \in [m, n], 因此我們就把它放入第 e - m + 1 個空間中即可. 如果集合中的元素存在重複的話, 我們可以把上面的 n - m + 1 個空間更換成 n - m + 1 個前向連結串列 (《【資料結構】前向連結串列》).

例題 1. 設集合 \mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \}, 根據 Algorithm 1 對集合 \mathscr {S} 建立桶. 其中, C_{1} 和 C_{2} 在數值上相等, 下標僅用於區分.

解 :

由於 \mathscr {S} 中存在重複的元素, 所以一個桶需要容納多個元素, 我們採用前向連結串列作為桶的低層資料結構. 從 A 到 P 之間, 總共應該配置 16 個前向連結串列 :

\blacksquare

2. 桶排序法

根據 Algorithm 1 獲得若干個桶之後, 我們只需要按順序尋訪每一個桶, 然後把桶中的元素提取出來按順序排列, 便可以得到一個有序的集合 :

我們合稱 Algorithm 1 和 Algorithm 2 為桶排序法 (bucket sort) 或者箱排序 (bin sort).

3. 穩定性討論

根據例題 1 中的 Figure 1, 我們可以看到, C_{1} 在 \mathscr {S} 中就排在了 C_{2} 前面, 在桶中仍然排在 C_{2} 前面. 因此我們是否可以簡單地判定桶排序法是穩定的排序演算法呢? 不能. Figure 1 中是畫出來的, 我們不必考慮在前向連結串列中插入元素所需要的步驟. 而實際上, 如果要在前向連結串列尾部插入元素, 我們還需要尋訪前面的所有元素. 於是一般來說, 我們會選擇將 C_{2} 插入到前向連結串列頭部, 那麼 C_{2} 將排在 C_{1} 之前. 在合併桶中的元素的時候, 也會從頭到尾按順序拿出元素. 最終, 原先排在 \mathscr {S} 後面的元素就會反過來排在前面. 也就是說, 那些在 \mathscr {S} 中相同的元素, 在 {\mathscr {S}}' 中是倒序排列的.

4. 複雜度分析

如果我們要對集合 \mathscr {S} 中的元素使用桶排序法, 那麼 Algorithm 1 會配置 \max \mathscr {S} - \min \mathscr {S} + 1 個空間. 而桶排序法剩下的操作所需要的輔助空間和元素數量無關. 我們記 r = \max \mathscr {S} - \min \mathscr {S}, 那麼桶排序法的空間複雜度為 \Theta(r). 桶排序法在建立桶的時候會尋訪所有元素一次, 在合併元素的時候會尋訪所有桶. 嚴格來說, 桶排序法的時間複雜度為 \Theta(n + r). 但是一般來說, 我們以集合中的元素數量為評價標準, 所以會認為桶排序法的時間複雜度為 \Theta(n).

除了名次排序法 (《【演算法】名次排序法 (Ranking Sort)》) 之外, 剩下所有排序演算法都是原地重排的排序演算法. 所以桶排序法是我們目前遇見的第一個時間複雜度為 \Theta(n) 級別 (線性級別) 的排序演算法, 這是典型的空間換時間思想.

5. 實作

#include <algorithm>
#include <forward_list>

int mapping(int x, int base) {
    return base ? (base > 0 ? x - base : x + -base) : x;
}
typename std::forward_list<int>::const_iterator before_last(const std::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;
    }
}
void bucket_sort(int arr[], int size) {
    const auto max {*std::max_element(arr, arr + size)};
    const auto min {*std::min_element(arr, arr + size)};
    const auto range {max - min + 1};
    auto list_array {new std::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]);
    }
    std::forward_list<int> r {};
    for(auto i {0}; i < range; ++i) {
        r.merge(list_array[i]);
    }
    delete[] list_array;
    auto it {r.cbegin()};
    for(auto i {0}; it not_eq r.cend(); ++i) {
        arr[i] = *it++;
    }
}

對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 bucket_sort 即可.