C++桶排序用代码实现

桶排序是一种非比较型整数排序算法，它通过将元素分到有限数量的“桶”里，对每个桶里的元素分别进行排序，最后再依次合并所有桶得到有序序列。在C++中实现桶排序的关键在于选择合适的桶大小以及处理边界情况。

以下是一个简单的C++桶排序实现示例：

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

// 桶排序函数
void bucketSort(int arr[], int n, int max_val) {
    // 创建一个与最大值相同的大小的空桶列表
    std::list<int> buckets[max_val + 1];

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

    // 对每个桶内的元素进行排序（这里假设桶内元素已经排序）
    for (int i = 0; i <= max_val; ++i) {
        if (!buckets[i].empty()) {
            auto it = buckets[i].begin();
            while (it != buckets[i].end()) {
                arr[j++] = *it++;
            }
        }
    }
}

int main() {
    int arr[] = {5, 8, 1, 9, 3, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_val = *std::max_element(arr, arr + n);
    
    bucketSort(arr, n, max_val);

    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    return 0;
}