bucket_sort.cpp

// bucket_sort.cpp
// -----------------------------------------------------------------
// Bucket Sort（桶排序）
//
// 原理：把值域切成 k 個「桶」，元素依大小分配到對應桶，
//       每個桶內部各自排序（通常用插入排序），最後依序串接。
//
// 時間複雜度：平均 O(n + k)（資料均勻分佈時）
//             最壞 O(n^2)（全部擠進同一桶）
// 空間複雜度：O(n + k)
// 穩定性：取決於桶內排序（用穩定排序則整體穩定）
// 適用：資料大致「均勻分佈」的浮點數或整數。
//
// Compile: g++ -std=c++17 -O2 -Wall -o bucket_sort bucket_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 浮點數版本：值域 [0, 1)
void bucketSortUnit(vector<double>& a) {
    int n = (int)a.size();
    if (n < 2) return;
    vector<vector<double>> buckets(n);
    for (double x : a)
        buckets[min(n - 1, (int)(x * n))].push_back(x);
    a.clear();
    for (auto& b : buckets) {
        sort(b.begin(), b.end());          // 桶內排序（元素少）
        for (double x : b) a.push_back(x);
    }
}

// 整數通用版本：依 min/max 均分成 sqrt(n) 個桶
void bucketSortInt(vector<int>& a) {
    int n = (int)a.size();
    if (n < 2) return;
    int mn = *min_element(a.begin(), a.end());
    int mx = *max_element(a.begin(), a.end());
    if (mn == mx) return;

    int k = max(1, (int)sqrt((double)n));
    vector<vector<int>> buckets(k);
    double range = (double)(mx - mn + 1) / k;
    for (int x : a)
        buckets[min(k - 1, (int)((x - mn) / range))].push_back(x);

    a.clear();
    for (auto& b : buckets) {
        sort(b.begin(), b.end());
        for (int x : b) a.push_back(x);
    }
}

int main() {
    vector<double> d = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434, 0.052};
    cout << "unit doubles before: ";
    for (double x : d) cout << x << " ";
    cout << "\n";
    bucketSortUnit(d);
    cout << "unit doubles after : ";
    for (double x : d) cout << x << " ";
    cout << "\nsorted : " << boolalpha << is_sorted(d.begin(), d.end()) << "\n\n";

    vector<vector<int>> tests = {
        {29, 25, 3, 49, 9, 37, 21, 43},
        {5, 2, 9, 1, 5, 6},
        {-10, 50, 0, -30, 20, 40},
        {7, 7, 7},
        {42},
        {},
    };
    for (auto& t : tests) {
        cout << "before: ";
        for (int x : t) cout << x << " ";
        cout << "\n";
        bucketSortInt(t);
        cout << "after : ";
        for (int x : t) cout << x << " ";
        cout << "\nsorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}