c++利用桶排序对5000个随机数进行排序

桶排序（Bucket Sort）是一种非比较型整数排序算法，它将元素分布到有限数量的“桶”中，然后对每个桶内的元素分别独立进行排序，最后按顺序合并所有桶的内容。在C++中使用桶排序对大量随机数进行排序的基本步骤如下：

1. **创建桶数组**：首先确定所需的桶的数量，通常选择足够大的值，如5000（这里的5000是个假设数字，实际取决于数据范围）。然后创建一个大小等于这个数量的空数组作为桶。

2. **分配元素到桶**：遍历待排序的5000个随机数，对于每个数，计算它落在哪个桶内。可以使用取模运算找到其在桶中的索引位置。

3. **排序桶中的元素**：对于每一个桶，如果内部元素数量小于或等于某个阈值，可以直接认为是有序的；否则可以使用其他排序算法（如插入排序、快速排序等），对每个桶内的元素进行内部排序。

4. **合并桶**：将所有桶中的元素依次取出并按照它们在原数组中的顺序连接起来，就得到了排序好的序列。

#include <iostream>
#include <vector>
#include <cstdlib> // 需要用到rand()函数

void bucketSort(std::vector<int>& arr, int bucketSize) {
    if (arr.empty()) return; // 如果数组为空，直接返回
    std::vector<std::vector<int>> buckets(bucketSize);
    for (int num : arr) {
        int index = num % bucketSize; // 计算元素落入的桶
        buckets[index].push_back(num); // 将元素放入对应的桶
    }

    for (auto& bucket : buckets) {
        if (!bucket.empty()) {
            sort(bucket.begin(), bucket.end()); // 对每个非空桶进行排序
        }
    }

    int currentIndex = 0;
    for (const auto& bucket : buckets) {
        for (int num : bucket) {
            arr[currentIndex++] = num; // 将已排序的元素合并回原数组
        }
    }
}

// 示例使用
int main() {
    const int n = 5000;
    std::vector<int> randomNumbers(n, 0); // 生成5000个随机数
    // ... (填充随机数)
    bucketSort(randomNumbers, 10); // 假设我们用10个桶
    // 现在randomNumbers数组应该是排序后的
    // ...
    return 0;
}