C++ 桶排序介绍与可视化演示 (优化版 v3)

#include <iostream>     // 用于输入输出 (For input/output)
#include <vector>      // 用于动态数组 (For dynamic arrays)
#include <algorithm>   // 包含 sort, min, max 等算法 (Includes sort, min, max algorithms)
#include <cmath>       // 用于数学函数，例如 abs (For math functions like abs)
#include <limits>      // 用于获取浮点数极值，如 epsilon (For numeric limits, e.g., epsilon)
using namespace std;

// 桶排序函数 (处理浮点数，可适配整数)
// arr: 待排序的浮点数向量 (通过引用传递以修改原数组)
// bucketCount: 要使用的桶的数量 
void bucketSort(vector& arr, int bucketCount) {
    int n = arr.size();
    // 处理边界情况：空数组或只有一个元素，无需排序
    if (n <= 1) return;

    // 1. 找到数组中的最大值和最小值
    float minValue = arr[0];
    float maxValue = arr[0];
    for (int i = 1; i < n; ++i) {
        minValue = min(minValue, arr[i]); // 使用 min
        maxValue = max(maxValue, arr[i]); // 使用 max
    }

    // 如果所有元素都相同，则无需排序 (另一个边界情况)
    if (minValue == maxValue) return;

    // 确保桶数量至少为1
    // Ensure bucketCount is at least 1
    if (bucketCount <= 0) bucketCount = 1;

    // 2. 计算桶的范围 (确保至少为很小的正数，防止除零或区间为0)
    // 注意：特殊处理最大值，将其放入最后一个桶是更稳健的做法
    float range = (maxValue - minValue) / bucketCount;
    // 处理 range 极小或为 0 的情况 (例如所有值非常接近)
    const float epsilon = numeric_limits::epsilon(); // 获取机器 epsilon
    if (range < epsilon) range = epsilon; // 使用机器 epsilon 作为最小范围

    // 3. 创建桶（使用二维向量，每个桶是一个 vector）
    vector> buckets(bucketCount);

    // 4. 将元素分配到对应的桶中
    for (int i = 0; i < n; ++i) {
        // 计算元素应该放入哪个桶的索引
        int bucketIndex;
        // 使用 epsilon 进行浮点数比较，更稳健，处理最大值
        if (abs(arr[i] - maxValue) < epsilon) {
             bucketIndex = bucketCount - 1; // 显式将最大值（或非常接近的值）放入最后一个桶
        } else if (abs(arr[i] - minValue) < epsilon && bucketCount > 1) {
             // 最小值（或接近的）放入第一个桶（如果多于一个桶）
             bucketIndex = 0;
        } else {
             // 通过 (当前值 - 最小值) / 区间大小 来确定相对位置
             bucketIndex = static_cast((arr[i] - minValue) / range);
        }

        // 边界检查，防止计算误差导致越界 (钳位到 [0, bucketCount-1])
        bucketIndex = max(0, min(bucketIndex, bucketCount - 1)); // 使用 max, min
        buckets[bucketIndex].push_back(arr[i]); // 将元素添加到桶中 / Add element to the bucket
    }

    // 5. 对每个非空桶内的元素进行排序
    for (int i = 0; i < bucketCount; ++i) {
        if (!buckets[i].empty()) {
            // 这里使用 C++ 标准库的排序算法 (通常是 IntroSort, 平均 O(N log N))
            // 对于非常小的桶，插入排序可能因常数因子小而更快 (但最坏 O(N^2))
            sort(buckets[i].begin(), buckets[i].end()); // 使用 sort

            // 示例：如果需要对小桶使用插入排序 (可选优化)
            // const int INSERTION_SORT_THRESHOLD = 32;
            // if (buckets[i].size() < INSERTION_SORT_THRESHOLD) {
            //    insertionSort(buckets[i]); // 假设有 insertionSort 函数 / Assuming an insertionSort function exists
            // } else {
            //    sort(buckets[i].begin(), buckets[i].end());
            // }
        }
    }

    // 6. 将所有桶中的元素按顺序合并回原数组
    int currentIndex = 0;
    for (int i = 0; i < bucketCount; ++i) {
        for (float val : buckets[i]) {
            arr[currentIndex++] = val;
        }
    }
}

// 示例主函数 (Example main function)
int main() {
    vector data = {0.42, 10.32, 0.33, 0.52, 10.37, 0.47, 0.5, 1.7, 0.12, 8.98, 0.66};
    int numBuckets = 5; // 指定桶数 
    cout << "原数组: ";
    for (float val : data) cout << val << " ";
    cout << endl;

    bucketSort(data, numBuckets); // 调用桶排序 

    cout << "Sorted array (" << numBuckets << " buckets): ";
    for (float val : data) cout << val << " ";
    cout << endl;

    return 0;
}
                

注意: 上述代码为了教学和简洁性使用了 float 并依赖 sort 进行桶内排序。在实际生产环境中，对于非常小的桶，自定义的插入排序可能更高效。强烈推荐在项目中使用 前缀代替 using namespace std; 以避免命名空间污染。