C++桶排序算法详解（从零开始掌握高效排序技巧）

桶排序适用条件

• 输入数据是浮点数或整数，且数值范围已知；
• 数据分布相对均匀（避免某个桶中元素过多）；
• 对时间复杂度有较高要求（理想情况下可达 O(n)）。

C++桶排序实现步骤

1. 确定数据的最大值和最小值，计算桶的数量；
2. 创建若干个空桶（通常用 vector> 表示）；
3. 将每个元素根据映射规则放入对应的桶中；
4. 对每个非空桶内部进行排序（如使用 std::sort）；
5. 按顺序将所有桶中的元素合并回原数组。

完整 C++ 桶排序代码示例

#include <iostream>#include <vector>#include <algorithm>void bucketSort(std::vector<double>& arr) {    if (arr.empty()) return;    // 1. 找到最大值和最小值    double minVal = *std::min_element(arr.begin(), arr.end());    double maxVal = *std::max_element(arr.begin(), arr.end());    // 2. 创建桶    int bucketCount = arr.size();    std::vector<std::vector<double>> buckets(bucketCount);    // 3. 将元素分配到桶中    for (double num : arr) {        int index = static_cast<int>((num - minVal) / (maxVal - minVal + 1) * bucketCount);        // 防止最大值越界        if (index == bucketCount) index--;        buckets[index].push_back(num);    }    // 4. 对每个桶排序并合并    int k = 0;    for (int i = 0; i < bucketCount; ++i) {        if (!buckets[i].empty()) {            std::sort(buckets[i].begin(), buckets[i].end());            for (double val : buckets[i]) {                arr[k++] = val;            }        }    }}// 测试函数int main() {    std::vector<double> data = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};    std::cout << "排序前: ";    for (double d : data) std::cout << d << " ";    std::cout << std::endl;    bucketSort(data);    std::cout << "排序后: ";    for (double d : data) std::cout << d << " ";    std::cout << std::endl;    return 0;}

算法复杂度分析

- 时间复杂度：理想情况下为 O(n + k)，其中 n 是元素个数，k 是桶的数量。最坏情况（所有元素落入同一个桶）退化为 O(n²)。

- 空间复杂度：O(n + k)，需要额外空间存储桶。

总结

通过本教程，你已经掌握了C++排序教程中一个高效而实用的算法——桶排序。它特别适合处理均匀分布的小数数据。记住，桶排序实现的关键在于合理设计桶的数量和映射规则。多加练习，你就能灵活运用这一算法解决实际问题！

关键词：C++桶排序算法、桶排序实现、C++排序教程、桶排序原理