请用C++实现桶排序算法

桶排序是一种非比较型整数排序算法，它将输入数据分布到有限数量的“桶”中，每个桶再分别进行排序，最后汇总所有桶的结果得到有序序列。以下是C++实现的基本步骤：

#include <iostream>
#include <vector>
#include <list>

void bucketSort(int arr[], int n, int bucketSize) {
    // 创建大小为bucketSize的固定大小的桶
    std::vector<std::list<int>> buckets(bucketSize);

    // 将元素放入相应的桶中
    for (int i = 0; i < n; ++i) {
        int index = arr[i] / bucketSize;
        buckets[index].push_back(arr[i]);
    }

    // 对每个桶内的元素单独排序
    for (std::list<int>& bucket : buckets) {
        bucket.sort();
    }

    // 合并所有已排序的桶
    int sortedIndex = 0;
    for (const auto& bucket : buckets) {
        for (auto& num : bucket) {
            arr[sortedIndex++] = num;
        }
    }
}

int main() {
    int arr[] = {5, 8, 1, 9, 3, 7, 2, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << "\n";

    bucketSort(arr, n, 5); // 假设我们选择桶的大小为5

    std::cout << "Sorted array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << "\n";

    return 0;
}

在这个例子中，我们首先计算出桶的数量，并创建相应数量的桶列表。然后遍历数组，将每个元素放到对应的桶中。接着对每个桶里的元素进行排序，最后合并所有的桶，就得到了排序后的数组。