算法导论：c++桶排序

客官°小女子只卖身不卖艺 2022-06-04 04:29 166阅读 0赞

![这里写图片描述][SouthEast]

### 代码实现 ###

桶排序是按照桶的概念把元素往里面放，然后桶内还有一个排序，桶内排序可以用比较排序也可以用计数排序递归使用桶排序也可以。我这里比较懒，直接用了sort函数。直接就三步，仍然用vector实现。

> 1.  建桶
> 2.  放桶
> 3.  连接桶

vector<double> bucket_sort(vector<double> array) {
        vector<vector<double>> output(10);//建立十个桶
        for (int i = 0; i < array.size(); i++) 
        {
            int temp = array[i] * 10;  //根据小数点第一位放入不同的桶中
            output[temp].push_back(array[i]);
        }
        array.clear(); //清除原无序数组
        for (auto vec:output)
        {
            if (!vec.empty()) {
                sort(vec.begin(),vec.end()); //对非空桶进行排序
                array.insert(array.end(),vec.begin(), vec.end()); //按桶的顺序放入原数组
            }
        }
        return array;
    }
    
    int main()
    {
    
        vector<double> array = {
       0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68 };
        array=bucket_sort(array);
        for (double f:array)
        {
            cout << f << " ";
        }
    }

测试的例子与书本相同，输出：  
![这里写图片描述][SouthEast 1]

[SouthEast]: /images/20220604/d6bd217b663e413396a83edd89e4abe0.png
[SouthEast 1]: /images/20220604/1753406870d4477fa85b5bf92e418ca3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关桶排序算法——C/C++

桶排序 1. 算法思想桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里，每个桶再分别排序（大部分是在分桶时，即

浅浅的花香味﹌/ 2022年12月26日 08:23/ 0 赞/ 76 阅读

相关排序算法——桶排序

排序算法——桶排序 > 桶排序的工作原理是将数组分到有限数量的桶里，每个桶再分别排序。桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的(arr\[i\

「爱情、让人受尽委屈。」/ 2022年12月23日 12:27/ 0 赞/ 144 阅读

相关排序算法-桶排序

先创建若干个桶，每个桶存放不同范围的数据桶和桶之间的跨度=(数据最大值-数据最小值)/ (桶的数量 - 1) 假设有一个数组：1.2，0.5，4.5，2.6，2.7

川长思鸟来/ 2022年10月18日 12:42/ 0 赞/ 126 阅读

相关算法导论之排序：快速排序、归并排序、计数排序、基数排序、桶排序

问题描述：输入：一个n个数的序列<a1,a2,a3,a4,a5,……,an>。输出：输入序列的一个排列<a1',a2',a3',a4',……,an'>。相关知识：

怼烎@/ 2022年07月28日 05:06/ 0 赞/ 186 阅读

相关算法导论：c++桶排序

![这里写图片描述][SouthEast] 代码实现桶排序是按照桶的概念把元素往里面放，然后桶内还有一个排序，桶内排序可以用比较排序也可以用计数排序递归使用桶排序也可

客官°小女子只卖身不卖艺/ 2022年06月04日 04:29/ 0 赞/ 167 阅读

相关算法导论：c++计数排序

区别于比较排序需要元素进行相互比较，计数排序仅仅通过元素个数确定它在排序结果中的位置。 ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast

今天药忘吃喽~/ 2022年06月04日 02:54/ 0 赞/ 153 阅读

相关算法导论：c++归并排序

基本思想就是把数组一直分成两半，然后对这两半进行排序归并。先分成左右两半，然后合并时比较左右两半一直选最小的替代原数组。这种排序是非原址的，需要额外的空间。伪代码非

偏执的太偏执、/ 2022年06月04日 02:53/ 0 赞/ 154 阅读

相关算法导论：c++快速排序

快速排序也采用分治的思想，以最后一个元素为基准把其分成大于它和小于它的两部分，关键在于确定分割点。算法思想 ![这里写图片描述][SouthEast] 一趟快排

客官°小女子只卖身不卖艺/ 2022年06月04日 02:26/ 0 赞/ 180 阅读

相关排序算法-桶排序

Bucket sorting(桶排序) 理论讲解比如一场考试，分数从0-10； ![2018033115440111][] 如果一个人得了3分，

阳光穿透心脏的1/2处/ 2022年05月28日 06:54/ 0 赞/ 232 阅读

相关排序算法c语言描述---桶排序

十一。桶排序一。个人理解桶排序是另外一种以O(n)或者接近O(n)的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组

蔚落/ 2021年10月30日 05:30/ 0 赞/ 369 阅读