夸克之书

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

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

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

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

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

%title插图%num

现在你可以请尝试一下输入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

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

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

文章评论

您需要 登录 之后才可以评论
放松一下
https://www.quarkbook.com/wp-content/uploads/2021/05/凤凰传奇-海底(Live).flac
分类
  • .NET/C#
  • Linux
  • 树莓派
  • 物联网
  • 科普
  • 笔记
  • 算法
  • 默认
最新 热点 随机
最新 热点 随机
在代码中判断龙芯新旧世界平台 Windows获取固定后缀的IPv6地址 目前为止,你可能找不到第二台支持志强的1L小主机(P350 Tiny+W-1350+ECC+双NVME+PCIE扩展)!!! iKuai(爱快)实现成都移动IPTV IPoE拨号 Linux EXT4分区误删除后数据恢复 C#连接到巴法云
在代码中判断龙芯新旧世界平台
OpenWrt x86安装Frpc 批处理器(BAT)自动请求管理员权限 免费本地解析域名(locallocal.cn),支持HTTPS 近期学习计划整理 Winform设置程序开机启动 智能语音控制中心 - 树莓派、Nanopi、Orangepi语音识别控制
最近评论
Eagle 发布于 9 个月前(10月21日) 参考博主教程成功搞定了成都移动IPTV组播转单播,电脑、手机都可以播放了。但目前有个问题,原IPTV...
rundoze 发布于 11 个月前(08月31日) 牛逼
cc21216695 发布于 2 年前(09月27日) 试了一下,加入启动项也无效,压根没有用
afirefish 发布于 3 年前(11月28日) 非常感谢,非常棒!
》随缘《 发布于 3 年前(11月20日) 最新【一键处理】方法: https://github.com/MrXhh/VSTools/rele...
书签
  • 打赏
  • 毒鸡汤
  • 米店
  • 金鱼直播间

COPYRIGHT © 2023 quarkbook.com. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

蜀ICP备15036129号-9

登录
注册|忘记密码?