桶排序c++实现（代码）

桶排序是一种非比较型整数排序算法，它通过将元素分到有限数量的“桶”里，对每个桶内的元素再分别进行排序，最后按顺序合并所有桶的结果得到有序序列。以下是使用C++实现桶排序的一个简单示例：

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

// 定义桶大小，可以根据实际情况调整
const int BUCKET_SIZE = 5;

void bucketSort(int arr[], int n) {
    // 创建足够大的空桶
    std::vector<std::list<int>> buckets(BUCKET_SIZE);

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

    // 分别对每个桶进行排序（这里假设内部桶是自排序的）
    for (auto& bucket : buckets) {
        bucket.sort();
    }

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

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

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

    bucketSort(arr, n);

    std::cout << "After sorting with Bucket Sort:\n";
    for (int i : arr) {
        std::cout << i << " ";
    }

    return 0;
}

在这个例子中，我们首先创建了大小相等的`BUCKET_SIZE`个桶，然后遍历输入数组，把每个元素放入对应的桶中。接着对每个桶进行排序，最后按照桶的顺序合并结果。