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

五分钟学会一个有意思的排序:计数排序

  •  1
     
  •   CoderOnePolo · 174 天前 · 2751 次点击
    这是一个创建于 174 天前的主题,其中的信息可能已经有所发展或是发生改变。

    由于 LeetCode 上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

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

    计数排序

    计数排序是一种非基于比较的排序算法,其空间复杂度和时间复杂度均为 O(n+k),其中 k 是整数的范围。基于比较的排序算法时间复杂度最小是 O(nlogn)的。该算法于 1954 年由 Harold H. Seward 提出。

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数

    算法步骤

    1. 花 O(n)的时间扫描一下整个序列 A,获取最小值 min 和最大值 max

    2. 开辟一块新的空间创建新的数组 B,长度为 ( max - min + 1)

    3. 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数

    4. 最后输出目标整数序列,具体的逻辑是遍历数组 B,输出相应元素以及对应的个数

    算法演示

    排序动画过程解释

    1. 首先,扫描一下整个序列

    2. 获得最小值为 2,最大值为 7

    3. 新建数组包含 2~7 的元素

    4. 再次扫描序列,将序列的值放置在新建数组中

    5. 扫描数字 5,数组中 index 为 3 的值为 5,次数为 1

    6. 扫描数字 3,数组中 index 为 1 的值为 3,次数为 1

    7. 扫描数字 4,数组中 index 为 2 的值为 4,次数为 1

    8. 扫描数字 7,数组中 index 为 5 的值为 7,次数为 1

    9. 扫描数字 2,数组中 index 为 0 的值为 2,次数为 1

    10. 扫描数字 4,数组中 index 为 2 的值为 4,次数为 2

    11. 扫描数字 3,数组中 index 为 1 的值为 3,次数为 2

    12. 按照这种节奏,扫描结束后,新建数组中存放了整个序列以及每个数字出现的次数

    13. 最后输出目标整数序列

    14. 输出数字 2,同时数组中 index 为 0 的值为 2 的元素次数变为 0

    15. 输出数字 3,同时数组中 index 为 1 的值为 3 的元素次数变为 1

    16. 同样的操作,整个序列就完全输出了

    代码实现

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

    Go 代码实现

    Java 代码实现

    Python 代码实现

    JavaScript 代码实现

    如果你是 iOS 开发者,可以在 GitHub 上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

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

    33 回复  |  直到 2018-11-27 23:27:24 +08:00
        1
    TreStone   174 天前
    之前项目里一个排序使用了这个思想,现在终于知道她的名字了
        2
    fairyto2   174 天前 via iPhone
    桶排序
        3
    Exploreloop2   174 天前   ♥ 1
    这个好像也叫桶排序?
        4
    co3site   174 天前 via Android
    就是桶排序嘛
        5
    mritd   174 天前   ♥ 8
    不好意思 我们只会睡眠排序
        6
    stevenbipt   174 天前 via Android
    学算法导论有这个算法,不过那个写得比较简洁,被数组的[]弄得特别晕,不过慢慢调试看下来就发现本质了。
        7
    CoderOnePolo   174 天前
    @fairyto2 桶排序跟这个类似,区别在于桶排序是有个桶,里面是一些整数的范围区间
        8
    CoderOnePolo   174 天前
    @TreStone 这个有时候还是挺好用的
        9
    CoderOnePolo   174 天前
    @mritd 我今天正在写一篇名为 《不知道睡眠排序,还谈什么排序算法》 ^_^
        10
    CoderOnePolo   174 天前
    @stevenbipt 是呀,都得慢慢调试,我发现我做完动画后理解就更深刻了
        11
    hardman   174 天前 via Android
    我咋看着像桶排序
        12
    xiaohuangya   174 天前 via Android
    我记得有个网站也是可视化的讲排序,也有动画,蛮像的,可我不记得网址了(@_@;)
        13
    wasmir   174 天前   ♥ 2
        14
    CoderOnePolo   174 天前
    @wasmir
        15
    CoderOnePolo   174 天前
    @hardman 我后天更新一波桶排序,就可以发现区别了😂
        16
    rabbbit   174 天前
    这个动画不错,哪啥做的
        17
    rabbbit   174 天前
    哪 -> 拿
        18
    CoderOnePolo   174 天前
    @rabbbit 都是用 PPT 动画做的,其他的排序算法也用 PPT 动画做好了,感兴趣的话可以关注一下看看😂
        19
    xiaohuangya   174 天前 via Android
    @wasmir 是这个。
        20
    kljsandjb   174 天前 via iPhone   ♥ 1
    桶子😂
        21
    stevenbipt   174 天前
    计数排序伪代码:
    //A:需要排序的数组
    //B:排好序数组
    //C[0...K]临时存储空间
    counting-sort(A,B,k)
    let C[0...k] be a new array
    for i=0 to k
    C[i]=0
    for j=1 to A.length
    C[A[j]]=C[A[j]]+1
    for i-=1 to k
    C[i]=C[i]+C[i-1]
    for j=A.length downto 1
    B[C[A[j]]]=A[j]
    C[A[j]]=C[A[j]]-1
    '''
    当初被这“[]”弄得头都大了,不过慢慢调试出来发现其实挺简单的,桶排序和这个区别好像在于桶是一个区间而不是一个数,在桶里面的元素需要进一步排序,通常会使用相对较快的比较排序方法对每个桶里面的元素进行排序,当输入数据满足:所有桶的大小的平方和与总的元素数呈线性关系。桶排序的期望运行时间还是 O(n)
        22
    wysnylc   174 天前
    说得好,我选择桶排序
        23
    ejq   173 天前 via Android
    我一般管它叫统(计)排(序)

    反正跟桶排差不多,这样叫也没啥问题(
        24
    CoderOnePolo   173 天前 via iPhone
    @wysnylc 酒桶么🤔
        25
    CoderOnePolo   173 天前 via iPhone
    @stevenbipt 大佬
        26
    CoderOnePolo   173 天前 via iPhone
    @ejq 那基数排序岂不是叫鸡排🐶
        27
    xml123   173 天前   ♥ 1
    重力排序了解一下,sqrt(n)的复杂度
        28
    CoderOnePolo   173 天前
    @xml123 可否详情解释一下🙏,最近在收集睡眠排序、猴子排序等逗比排序的时间复杂度,打算写一写这些。
        29
    xml123   173 天前
    wiki 上叫珠排序
    zh.wikipedia.org/wiki/珠排序
    直接看那两张图就懂了
        30
    Tony042   173 天前 via iPhone
    如果是浮点数 这个算法是不是就没法用了?
        31
    qiayue   173 天前
    楼主可以透露一下这个公众号粉丝到了哪个量级吗?
    千、万、十万?
        32
    CoderOnePolo   173 天前
    @Tony042 是的,题目要求整数才行
        33
    XiaoxiaoPu   173 天前
    @Tony042 浮点数用基数排序,不过需要研究下 IEEE 754,特殊处理下
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3118 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 27ms · UTC 10:40 · PVG 18:40 · LAX 03:40 · JFK 06:40
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1