c++利用桶排序实现对数组排序

桶排序是一种非比较型整数排序算法，它将元素分布到有限数量的“桶”中，然后分别对每个桶内的元素进行排序，最后再按照桶的顺序合并所有桶的内容得到有序序列。在 C++ 中实现桶排序需要以下几个步骤：

1. **初始化桶**：创建大小相等的空桶数组，通常选择能容纳数组最大值的整数范围作为桶的数量。

2. **分桶**：遍历待排序的数组，把每个元素放入对应的桶中。这里的关键在于找到合适的映射函数，比如取余法，将元素均匀地分布在各个桶中。

3. **桶内排序**：对于每个桶，单独对其进行排序。这一步可以采用其他已知的排序算法（如插入排序、冒泡排序等），因为桶内部的元素已经较少，效率相对较高。

4. **合并结果**：所有桶排序完成后，将每个桶中的元素依次取出，按顺序组成最终的有序数组。

5. **优化**：如果原始数据已经是近似有序的，桶排序的性能会非常好；但如果数据随机分布，则桶排序的效果可能会变差。在这种情况下，可以考虑先使用快速排序或其他高效的排序算法做预处理，然后再进行桶排序。

// 示例代码（简化版）
#include <vector>
#include <iostream>

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& subArr : buckets) {
        // 对每个桶进行排序（例如使用插入排序）
        insertionSort(subArr);
    }
    
    int i = 0;
    for (const auto& subArr : buckets) {
        for (int num : subArr) {
            arr[i++] = num;
        }
    }
}

// 插入排序示例
void insertionSort(std::vector<int>& nums) {
    for (size_t i = 1; i < nums.size(); ++i) {
        int key = nums[i];
        size_t j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
}