夸克之书

  • 首页
  • 科普
  • 笔记
  • C#
  • 物联网
  • 算法
  • Linux
  • 树莓派
夸克之内,别有洞天
  1. 首页
  2. 默认
  3. 正文

严肃一点的排序算法(4) – 桶排序

2019-01-07 813点热度 0人点赞 0条评论

其实这是一个很严肃的排序算法,在实际的编程当中,很有可能会用到。

这个算法就好比有11个桶,编号从0~10。每出现一个数,就将对应编号的桶中的放一个小旗子,最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子,表示2出现了一次;3号桶中有1个小旗子,表示3出现了一次;5号桶中有2个小旗子,表示5出现了两次;8号桶中有1个小旗子,表示8出现了一次。

严肃一点的排序算法(4) – 桶排序插图

现在你可以请尝试一下输入n个0~1000之间的整数,将他们从大到小排序。提醒一下如果需要对数据范围在0~1000之间的整数进行排序,我们需要1001个桶,来表示0~1000之间每一个数出现的次数,这一点一定要注意。另外此处的每一个桶a[i]的作用其实就是“标记”每个数出现的次数,因此我喜欢将之前的数组a换个更贴切的名字book(book这个单词有记录、标记的意思)。

最后来说下时间复杂度的问题。代码中第6行的循环一共循环了m次(m为桶的个数),第9行的代码循环了n次(n为待排序数的个数),第14和15行一共循环了m+n次。所以整个排序算法一共执行了m+n+m+n次。我们用大写字母O来表示时间复杂度,因此该算法的时间复杂度是O(m+n+m+n)即O(2*(m+n))。我们在说时间复杂度时候可以忽略较小的常数,最终桶排序的时间复杂度为O(m+n)。还有一点,在表示时间复杂度的时候,n和m通常用大写字母即O(M+N)。

最后通过代码来实践一下。

static void Main(string[] args)
{
    int[] nums = new[] { 1, 4, 7, 20, 14, 30, 124, 45 };
    List<int> bucket = new List<int>(); //很多很多的桶

    //初始化桶
    int max = GetMaxValue(nums);
    for (int i = 0; i < max + 1; i++)
    {
        bucket.Add(0);
    }
    //往桶里面倒水
    for (int i = 0; i < nums.Length; i++)
    {
        bucket[nums[i]]++;
    }
    //把桶搬出来
    for (int i = 0; i < bucket.Count; i++)
    {
        if (bucket[i] != 0)
        {
            for (int j = 0; j < bucket[i]; j++)
            {
                Console.Write(i + ",");
            }
        }
    }
    Console.WriteLine("rn");
    Console.ReadKey(false);
}

static int GetMaxValue(int[] nums)
{
    int max = nums[0];
    for (int i = 0; i < nums.Length; i++)
    {
        if (max < nums[i])
        {
            max = nums[i];
        }
    }
    return max;
}

其实简单来说,桶排序就是使用空间换取时间的一种排序算法。

摘抄来源:https://blog.csdn.net/YinhJiang/article/details/80397415

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020-12-13

afirefish

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

管理员

这个人很懒,什么都没留下

搜索文章
分类
  • C# (29)
  • Linux (3)
  • 树莓派 (13)
  • 物联网 (19)
  • 科普 (4)
  • 笔记 (30)
  • 默认 (46)
最新 热点 随机
最新 热点 随机
C#几种深拷贝方法探究及性能比较 获取访问IP信息接口(暂不开放) Vieu主题作者疑似跑路?这人品?!!! 树莓派PWM风扇控制 PVE重启后LVM Thin数据丢失,错误:Volume group "****" has insufficient free space (128 extents): 4048 required. OpenWrt配置SmartDNS OpenWrt x86安装Frpc Intel网卡开机显示Initializing Intel(R) Boot Agent GE v1.5.50
树莓派PWM风扇控制Error response from daemon: cannot stop container: ******: Cannot kill container *******:.....单机Docker搭建FastDFSC# Json序列化时将长整型(long)属性序列化为Json字符串使用淘宝npm以及安装cnpm免费本地解析域名(locallocal.cn),支持HTTPSIdentityServer4证书创建Intel网卡开机显示Initializing Intel(R) Boot Agent GE v1.5.50
PVE重启后LVM Thin数据丢失,错误:Volume group "****" has insufficient free space (128 extents): 4048 required. 树莓派.Net Core Iot入门系列篇(1):点亮一个LED灯 Ubuntu18.04安装Docker 将对象转化为Get请求字符串 Winform设置程序开机启动 近期学习计划整理 23种常见的设计模式(6):代理(委托)模式 Navicat 12 for MySQL激活
最近评论
发布于 3 周前(03月21日) function getCpuTemp() 函数结束之前使用close关闭 文件流 不关闭的话长...
发布于 3 周前(03月19日) 闹了半天找到问题了 原来是gpio版本问题 pi@raspberrypi:~/Desktop $ ...
发布于 3 周前(03月19日) sudo下执行 无法控制小风扇 普通用户却可以 这是可能是什么原因 :redface:
发布于 2 个月前(02月21日) 好的谢谢,那我只能通过kill杀死推流指令进程来实现了。
发布于 2 个月前(02月21日) 要用这个项目的话,你得自己拉代码来改了。做这玩意儿主要是考虑全天候的,没考虑过关[笑哭]
书签
  • 打赏
  • 毒鸡汤(有点意思)
  • 米店
  • 金鱼直播间
放松一下
https://www.quarkbook.com/wp-content/uploads/2020/09/Yanni-Nightingale.flac
用户您好!请先登录!
登录 注册

COPYRIGHT © 2020 夸克之书. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

蜀ICP备15036129号-9

登录
注册|忘记密码?