V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
CoderOnePolo
V2EX  ›  推广

五分钟看懂一个有意思的排序:桶排序

  •  
  •   CoderOnePolo · 2018-11-29 09:00:39 +08:00 · 4091 次点击
    这是一个创建于 2187 天前的主题,其中的信息可能已经有所发展或是发生改变。

    桶排序

    桶排序(Bucket sort)是一种基于计数的排序算法(计数排序可参考上节的内容),工作的原理是将数据分到有限数量的桶子里,然后每个桶再分别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)

    你可以关注公众号 五分钟学算法 获取更多排序内容。

    算法步骤

    1. 设置固定数量的空桶。

    2. 把数据放到对应的桶中。

    3. 对每个不为空的桶中数据进行排序。

    4. 拼接不为空的桶中数据,得到结果。

    算法演示

    动画演示 GIF 加载有点慢,请稍等片刻^_^

    排序动画过程解释

    1. 首先,设置固定数量的空桶,在这里为了方便演示,设置桶的数量为 5 个空桶

    2. 遍历整个数列,找到最大值为 56,最小值为 2,每个桶的范围为 ( 56 - 2 + 1 )/ 5 = 11

    3. 再次遍历整个数列,按照公式 floor((数字 – 最小值) / 11) 将数字放到对应的桶中

    4. 比如,数字 7 代入公式 floor((7 – 2) / 11) = 0 放入 0 号桶

    5. 数字 12 代入公式 floor((12 – 2) / 11) = 0 放入 0 号桶

    6. 数字 56 代入公式 floor((56 – 2) / 11) = 4 放入 4 号桶

    7. 当向同一个索引的桶,第二次插入数据时,判断桶中已存在的数字与新插入数字的大小,按照左到右,从小到大的顺序插入(可以使用前面讲解的插入排序)实现

    8. 比如,插入数字 19 时,1 号桶中已经有数字 23,在这里使用插入排序,让 19 排在 23 前面

    9. 遍历完整个数列后,合并非空的桶,按从左到右的顺序合并 0,1,2,3,4 桶。

    10. 这样就完成了 桶排序

    代码实现

    为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

    C++代码实现

    Java 代码实现

    JavaScript 代码实现

    你可以关注公众号 五分钟学算法 获取更多排序内容。

    9 条回复    2018-11-29 11:15:51 +08:00
    stevenbipt
        1
    stevenbipt  
       2018-11-29 09:40:43 +08:00 via Android   ❤️ 1
    点个赞~
    wysnylc
        2
    wysnylc  
       2018-11-29 10:19:49 +08:00
    桶的数量可以随样本的大小增加或者减少
    chanchan
        3
    chanchan  
       2018-11-29 10:22:45 +08:00   ❤️ 1
    不说说为什么这么排以及这么排的优点缺点吗
    Geraltt
        4
    Geraltt  
       2018-11-29 10:35:19 +08:00 via iPhone
    想知道时空复杂度的推导
    flowfire
        5
    flowfire  
       2018-11-29 10:57:07 +08:00 via iPhone
    这个排序方法最坏情况下的复杂度不是跟插入排序一样么……
    CoderOnePolo
        6
    CoderOnePolo  
    OP
       2018-11-29 11:01:13 +08:00 via iPhone
    @wysnylc 是的
    wysnylc
        7
    wysnylc  
       2018-11-29 11:07:59 +08:00   ❤️ 1
    @chanchan #3 可以分布式处理,避免在内存中一次加载超大量数据
    @flowfire #5 实际应用不只是考虑复杂度,要考虑生产环境的限制比如内存硬盘 CPU
    stevenbipt
        8
    stevenbipt  
       2018-11-29 11:12:52 +08:00   ❤️ 1
    @Geraltt #4 算法导论上有完整的推导
    stevenbipt
        9
    stevenbipt  
       2018-11-29 11:15:51 +08:00   ❤️ 1
    @flowfire #5 使用插入排序没问题的,只要数据满足:所有桶的大小的平方和与总的元素数呈线性关系,桶排序的期望运行时间为 O(N)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2613 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 04:41 · PVG 12:41 · LAX 20:41 · JFK 23:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.