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

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. 實作

Code 1. 桶排序法
#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 即可.