使用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)，此时更适合用快速排序等比较排序。

通过桶排序，我们可以在数据分布合理的情况下高效完成排序，尤其适合处理范围明确的数值型数据。