C++ 实现桶排序的示例代码

下面是一份详细的攻略，带有示例说明。

桶排序简介

桶排序是一种基于计数的排序算法。它将一些数据分到不同的桶里，再对每个桶中的数据进行排序，最后按照桶的顺序依次输出所有数据，即可得到排好序的序列。

桶排序的时间复杂度是 $O(n)$，空间复杂度也是 $O(n)$，适用于元素值分布比较均匀的数据。

C++ 桶排序示例

下面是一份 C++ 实现桶排序的示例代码：

#include <iostream>
#include <vector>

using namespace std;

void bucketSort(vector<int>& nums) {
    // 找到最大值和最小值
    int max_value = nums[0];
    int min_value = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        max_value = max(max_value, nums[i]);
        min_value = min(min_value, nums[i]);
    }

    // 计算桶的数量
    int bucket_num = max_value / 10 - min_value / 10 + 1;

    // 初始化桶
    vector<vector<int>> buckets(bucket_num);

    // 将元素放入桶中
    for (int i = 0; i < nums.size(); i++) {
        int index = (nums[i] - min_value) / 10;
        buckets[index].push_back(nums[i]);
    }

    // 对桶中的元素进行排序
    for (int i = 0; i < bucket_num; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // 将桶中的元素取出来
    int index = 0;
    for (int i = 0; i < bucket_num; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            nums[index++] = buckets[i][j];
        }
    }
}

int main() {
    vector<int> nums = {15, 34, 28, 19, 64, 72, 44, 77, 96, 101};
    bucketSort(nums);
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;

    return 0;
}

上述代码实现了桶排序算法的所有步骤：

1. 计算最大值和最小值
2. 计算桶的数量
3. 初始化桶
4. 将元素放入桶中
5. 对桶中的元素进行排序
6. 将桶中的元素取出来，得到排好序的数组

值得注意的是，上述代码中将每个桶的大小定为 10，这有助于避免桶溢出的发生。同时，如果元素值分布过于不均匀，可以调整桶的大小，提高桶排序算法的效率。

示例说明

假设现在有一组数据，包含如下元素：

15, 34, 28, 19, 64, 72, 44, 77, 96, 101

我们可以使用桶排序算法将它们排序，得到如下结果：

15, 19, 28, 34, 44, 64, 72, 77, 96, 101

上述示例使用的桶的大小为 10，可以通过调整桶的大小进行优化。同时，如果元素值分布过于不均匀，可以调整桶的大小，提高算法的效率。