递归桶排序是否为更优选择？原理分析与实现探讨

咱们先回忆下标准桶排序的路子：把arr[i]塞进bucket[n*array[i]]对应的桶里，每个桶内部随便用个排序算法处理，最后按顺序把所有桶的元素攒起来就是有序列表了。但这儿有个坑——最坏情况下的时间复杂度直接就跟桶里用的子排序算法绑定了，比如子排序用冒泡的话，最坏就是O(n²)，这显然不太理想。

那我就琢磨了：要是咱们递归地用桶排序来处理每个桶呢？这不就不用依赖其他排序算法了嘛，全程用桶排序的逻辑嵌套处理。下面是补全后的完整可运行代码：

#include<iostream>
#include<vector>
using namespace std;

vector<float> bucketSort(vector<float> arr) {
    // 递归终止条件：数组长度小于等于1时直接返回（已经有序）
    if (arr.size() <= 1) {
        return arr;
    }

    int bucketCount = arr.size();
    vector<vector<float>> buckets(bucketCount);

    // 将元素分配到对应桶中，假设元素范围在[0,1)
    for (float num : arr) {
        int bucketIndex = bucketCount * num;
        buckets[bucketIndex].push_back(num);
    }

    // 递归处理每个桶，再合并结果
    vector<float> sortedResult;
    for (auto& bucket : buckets) {
        vector<float> sortedBucket = bucketSort(bucket);
        sortedResult.insert(sortedResult.end(), sortedBucket.begin(), sortedBucket.end());
    }

    return sortedResult;
}

// 测试用例
int main() {
    vector<float> testArr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
    vector<float> sortedArr = bucketSort(testArr);

    cout << "排序后的数组：";
    for (float num : sortedArr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

几点说明： #

• 这段代码默认待排序元素是**[0,1)**区间的浮点数，如果要处理其他范围的数值，需要先做映射转换，比如把[a,b)区间的数转换为(x - a) / (b - a)，将其映射到[0,1)区间后再进行分桶。
• 递归终止条件设置为数组长度≤1，这是因为长度为0或1的数组本身就是有序的，无需再进行分桶操作。
• 极端场景下（比如所有元素都集中在同一个桶里），单纯递归桶排序的时间复杂度会退化为O(n²)。如果要优化这种情况，可以在桶内元素数量超过某个阈值时，切换到快速排序这类O(n log n)的排序算法，平衡最坏情况和平均情况的性能。

内容的提问来源于stack exchange，提问作者Sourav