C++中的桶排序

桶排序是一种分布式排序算法，它将元素分为若干个桶（或称为箱子），然后对每个桶内的元素进行排序，最后按照顺序将各个桶中的元素合并起来。桶排序的基本思想是将待排序的元素分布到不同的桶中，然后对每个桶中的元素进行排序，最终按照桶的顺序将元素合并起来。

桶排序是一种分布式排序算法，适用于元素均匀分布在一定范围内的情况。以下是桶排序的算法描述：

1. 确定桶的数量：首先确定要使用多少个桶来容纳待排序的元素。桶的数量可以根据元素的范围来确定，通常可以使用一个范围划分为若干个桶。

2. 初始化桶：创建桶，并将每个桶初始化为空。

3. 分配元素到桶中：遍历待排序的元素列表，将每个元素分配到对应的桶中。分配的规则可以根据元素的值来确定，例如，可以将元素按照一定的规则映射到桶的索引位置。

4. 在每个桶内部排序：对每个非空的桶进行内部排序。通常可以使用插入排序或其他排序算法对每个桶中的元素进行排序。

5. 合并桶中的元素：按照桶的顺序，将各个桶中的元素合并起来，形成最终的有序序列。

6. 输出排序结果：排序完成后，得到了有序的元素序列。

总结： 桶排序的核心思想是将元素分布到多个桶中，然后对每个桶中的元素进行排序，最后合并各个桶中的元素以获得最终的排序结果。桶排序适用于元素均匀分布的情况，可以在一定程度上提高排序的效率。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义桶排序函数
void bucketSort(vector<int>& arr) {
    const int maxVal = *max_element(arr.begin(), arr.end());
    const int minVal = *min_element(arr.begin(), arr.end());

    // 计算桶的数量
    const int bucketCount = (maxVal - minVal) / 5 + 1;

    // 创建桶并初始化为空
    vector<vector<int> > buckets(bucketCount);

    // 将元素分布到桶中
    for (int i = 0; i < arr.size(); ++i) {
        int bucketIndex = (arr[i] - minVal) / 5;
        buckets[bucketIndex].push_back(arr[i]);
    }

    // 对每个桶内的元素进行插入排序
    for (int i = 0; i < buckets.size(); ++i) {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // 合并桶中的元素
    int index = 0;
    for (int i = 0; i < buckets.size(); ++i) {
        for (int j = 0; j < buckets[i].size(); ++j) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    vector<int> arr = {37, 89, 41, 65, 91, 53, 29, 77, 19};

    // 调用桶排序函数
    bucketSort(arr);

    // 打印排序后的数组
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}