排序算法-桶排序

阳光穿透心脏的1/2处 2022-05-28 06:54 406阅读 0赞

Bucket sorting(桶排序)

理论讲解
  比如一场考试，分数从0-10；
2018033115440111

如果一个人得了3分，那么a[3]就+1，代表得3分的有一个人
这里写图片描述

如果一个人得了5分，那么a[5]就+1，代表得5分的有一个人
这里写图片描述

如果又有个人得了5分，那么a[5]就再+1，代表得5分的有2个人
这里写图片描述

如果又有个人得了8分，最终结果如下
这里写图片描述
依次输出即可

  1. #include "stdafx.h"
  2. #include "iostream"
  3. using namespace std;
  4. int main()
  5. {
  6.     int i,j,a[11] = {0};
  7.     for (i = 0; i < 5; i++)
  8.     {
  9.         cin >> j;//input
  10.         a[j] ++;//输入是多少就在a[多少]++
  11.     }
  13.     for (i = 10; i >=0; i--)//output from big to small
  14.     {
  15.         for (; a[i] > 0;a[i]--) cout << i;
  16.     }
  17.     return 0;
  18. }

这里写图片描述

总结

bucket sorting 实际中用的不多，有致命的缺点就是：如果我想比较范围很大 0-9999；那么我将定义a[10000]这么大的数组，假如我只想排几个数，太不值得。时间复杂度 O(N+M): N多少个数，M是数组范围。

或者我想排序里面有浮点数，那么久困难了。

发表评论

表情：
评论列表 （有 0 条评论，406人围观）

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

相关阅读

    相关 排序算法 - 桶排序

    前言 桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使

    骑猪看日落骑猪看日落/ 0 赞/ 185 阅读

    相关 算法：桶排序

    计数排序、桶排序、基数排序均为O(n)算法 桶排序可以看成是计数排序的升级版，它将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可

    本是古典 何须时尚本是古典 何须时尚/ 0 赞/ 88 阅读

    相关 排序算法-桶排序

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

    川长思鸟来川长思鸟来/ 0 赞/ 268 阅读

    相关 [算法]桶排序

    介绍 桶排序是分治算法的应用. 桶排序实际上就是把要排序的容器中的数据,分别按照大小跨度 分散在若干个桶中,如果桶中有一个以上的数据,则单独的桶进行 排序,最

    红太狼红太狼/ 0 赞/ 315 阅读