使用C++實現桶排序算法

桶排序（Bucket Sort）的C++實現¶

桶排序是一種非比較型排序算法，它通過將待排序元素分配到多個“桶”中，對每個桶內的元素單獨排序後，再合併所有桶的結果，從而實現整體排序。這種方法的核心是合理劃分桶的範圍，使得每個桶內的元素數量儘量少，以降低排序成本。

算法思路（以浮點數爲例）¶

假設待排序數組的元素均爲範圍在[0,1)的浮點數，且數組長度爲n。步驟如下：
1. 創建桶：根據數組長度n，創建n個空桶（每個桶是一個容器，用於存儲同一區間的元素）。
2. 分配元素到桶：遍歷數組，將每個元素x按桶索引 = static_cast<int>(x * n)的規則放入對應桶中（例如，元素0.42在n=7時，桶索引爲0.42*7=2.94，取整數部分2，放入第2個桶）。
3. 桶內排序：對每個桶內的元素使用內置排序函數（如C++的std::sort）單獨排序。
4. 合併結果：按順序遍歷所有桶，將桶內元素依次取出併合並，得到最終排序數組。

C++代碼實現¶

#include <iostream>
#include <vector>
#include <algorithm>  // 用於std::sort

using namespace std;

// 桶排序函數：輸入爲範圍在[0,1)的浮點數數組
vector<double> bucketSort(vector<double>& arr) {
    int n = arr.size();
    if (n == 0) return arr;  // 空數組直接返回

    // 步驟1：創建n個空桶（每個桶是vector<double>）
    vector<vector<double>> buckets(n);

    // 步驟2：將元素分配到對應的桶中
    for (double x : arr) {
        // 計算桶索引：x在[0,1)範圍內，桶索引 = x * n（取整數部分）
        int bucketIndex = static_cast<int>(x * n);
        buckets[bucketIndex].push_back(x);
    }

    // 步驟3：對每個桶內的元素排序
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());  // 使用內置排序函數，簡單高效
    }

    // 步驟4：合併所有桶的元素
    vector<double> result;
    for (auto& bucket : buckets) {
        result.insert(result.end(), bucket.begin(), bucket.end());
    }

    return result;
}

// 測試函數
int main() {
    vector<double> arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
    cout << "排序前數組：";
    for (double num : arr) cout << num << " ";
    cout << endl;

    vector<double> sortedArr = bucketSort(arr);

    cout << "排序後數組：";
    for (double num : sortedArr) cout << num << " ";
    cout << endl;

    return 0;
}

代碼解釋¶

創建桶：vector<vector<double>> buckets(n)初始化n個空桶，每個桶用於存儲同一區間的元素。
分配元素：通過x * n計算桶索引，確保每個元素落入對應的桶中。例如，0.42*7=2.94（n=7時），桶索引爲2，元素0.42被放入第2個桶。
桶內排序：使用std::sort對每個桶內的元素排序，避免了複雜的排序邏輯。
合併結果：遍歷所有桶，將每個桶的元素依次插入結果數組，最終得到升序排列的數組。

複雜度分析¶

時間複雜度：平均情況下爲O(n)（每個桶內元素均勻分佈時，排序n個桶的總時間爲O(n)）；最壞情況下爲O(n log n)（所有元素落入同一桶，排序該桶的時間爲O(n log n)）。
空間複雜度：O(n + k)（k爲桶的數量，通常k=n，因此空間複雜度爲O(n)）。

適用場景¶

數據分佈均勻：適合處理範圍明確且元素密集的數組（如統計分析中的區間數據）。
避免極端情況：若數據分佈極不均勻（如所有元素落入同一桶），桶排序性能會退化爲O(n log n)，此時更適合用快速排序等比較排序。

通過桶排序，我們可以在數據分佈合理的情況下高效完成排序，尤其適合處理範圍明確的數值型數據。