程序分享--排序算法--桶排序

关注我，持续分享逻辑思维&管理思维； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》《做好面试准备，迎接2024金三银四》。

-------------------------------------正文----------------------------------------

桶排序：概述
桶排序又叫箱排序，是计数排序的升级版，它的工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。网络中很多博文写的桶排序实际上都是计数排序，并非标准的桶排序，要注意辨别。

桶排序：算法描述

1.找出待排序数组中的最大值max、最小值min
2.使用 动态数组bucketArr作为桶，桶里放的元素也用bucketArr存储。桶的数量为(max-min)/arr.size()+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
5.遍历桶数组，把排序好的元素放进输出数组

#include <iostream>
#include <vector>
#include <algorithm>
 
void bucketSort(std::vector<int>& arr, int bucketSize)
 {
    if (arr.empty() || bucketSize <= 0) return;
 
    int minValue = *std::min_element(arr.begin(), arr.end());
    int maxValue = *std::max_element(arr.begin(), arr.end());
 
    int numBuckets = (maxValue - minValue) / bucketSize + 1;
    std::vector<std::vector<int>> buckets(numBuckets);
 
    // 分配元素到桶中
    for (int i = 0; i < arr.size(); ++i) 
    {
        int bucketIndex = (arr[i] - minValue) / bucketSize;
        buckets[bucketIndex].push_back(arr[i]);
    }
 
    // 对每个桶进行排序
    for (int i=0; i<buckets.size(); i++) 
    {
        std::vector<int>& bucket=buckets[i];
        std::sort(bucket.begin(), bucket.end());
    }
 
    // 合并桶回原数组
    arr.clear();
    for (int i=0; std::vector<int>& bucket=buckets[i]; i++) 
    {
        int value;
        for (int j=0; j<bucket.size(); j++)
         {
            arr.push_back(bucket[j]);
        }
    }
}
 
int main() 
{
    std::vector<int> data = {5, 3, 1, 2, 8, 7, 6, 4};
    int bucketSize = 2; // 可以根据实际情况调整桶的大小
    bucketSort(data, bucketSize);
 
    for (int num : data) {
        std::cout << num << " ";
    }
 
    return 0;
}