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

十大经典排序算法动画,看我就够了!

  •  9
     
  •   CoderOnePolo · 2018-12-03 08:59:13 +08:00 · 8595 次点击
    这是一个创建于 1942 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在前面的章节中详细的讲解分析了十大经典排序算法,本文将进行一个大总结同时分析它们的时间复杂度与稳定性。

    排序算法是《数据结构与算法》中最基本的算法之一。

    排序算法可以分为内部排序外部排序

    内部排序是数据记录在内存中进行排序。

    而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

    用一张图概括:

    image

    关于时间复杂度:

    1. 平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。
    2. 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;
    3. O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序
    4. 线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

    关于稳定性:

    1. 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

    2. 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

    1. 冒泡排序

    image

    2. 选择排序

    image

    3. 插入排序

    image

    4. 希尔排序

    image

    5. 归并排序

    image

    6. 快速排序

    image

    7. 堆排序

    image

    8. 计数排序

    image

    9. 桶排序

    image

    10. 基数排序

    image

    Tip 为了演示更加清楚,本文中所有的动画都放慢了速度,因此 GIF 大小对比之前会有所增大,图片加载速度会变慢,如果你想获取所有的超清动画,在公众号 五分钟学算法 回复 v2ex 可获得资料。

    第 1 条附言  ·  2018-12-03 09:36:27 +08:00

    修正堆排序:

    第 2 条附言  ·  2018-12-03 12:31:46 +08:00
    没想到能有这么多收藏,感谢各位大佬支持,感兴趣的话可以关注一波公众号^_^
    40 条回复    2018-12-03 20:26:43 +08:00
    singlepig
        1
    singlepig  
       2018-12-03 09:22:48 +08:00   ❤️ 1
    楼主,7 堆排序和 6 的图是一样的
    CoderOnePolo
        2
    CoderOnePolo  
    OP
       2018-12-03 09:28:35 +08:00
    @singlepig 不好意思,上传错了
    RyougiShiki
        3
    RyougiShiki  
       2018-12-03 09:31:22 +08:00   ❤️ 1
    不错。编程领域需要设计,图明白多了。
    CoderOnePolo
        4
    CoderOnePolo  
    OP
       2018-12-03 09:35:42 +08:00
    @RyougiShiki 感谢肯定。也是因为之前学这个的时候太抽象了,感觉还是具体化就好理解了。
    zxgfy12
        5
    zxgfy12  
       2018-12-03 09:52:44 +08:00   ❤️ 1
    这个很不错,特别是给入门的看。
    话说这种动图,是用什么工具来做呢?
    richzhu
        6
    richzhu  
       2018-12-03 09:55:07 +08:00
    我前几天下载这个 APP 啦,哈哈哈~
    mogami95
        7
    mogami95  
       2018-12-03 09:58:16 +08:00   ❤️ 1
    漂亮!
    thfurior
        8
    thfurior  
       2018-12-03 09:59:57 +08:00   ❤️ 1
    不错,很清楚
    jingyulong
        9
    jingyulong  
       2018-12-03 10:01:46 +08:00
    从初学者的角度来写,不错的👍
    CoderOnePolo
        10
    CoderOnePolo  
    OP
       2018-12-03 10:04:37 +08:00
    @zxgfy12 都是自己用 PPT 做的,做的目的就是给初学者入门用的,希望能更好的理解。
    CoderOnePolo
        11
    CoderOnePolo  
    OP
       2018-12-03 10:05:47 +08:00
    @richzhu 是哪个 APP,我下载下来学习参考一下^_^
    CoderOnePolo
        12
    CoderOnePolo  
    OP
       2018-12-03 10:06:33 +08:00
    @jingyulong
    @thfurior
    @mogami95
    感谢肯定,欢迎一起学习!
    richzhu
        13
    richzhu  
       2018-12-03 10:11:47 +08:00   ❤️ 1
    @CoderOnePolo 苹果商店搜 “算法动画图解” 😀
    CoderOnePolo
        14
    CoderOnePolo  
    OP
       2018-12-03 10:17:06 +08:00
    @richzhu 收到,感谢!!!
    vanishcode
        15
    vanishcode  
       2018-12-03 10:20:05 +08:00 via Android   ❤️ 1
    楼主这个也挺好的。我之前学数据结构的时候用的 visualgo https://visualgo.net/zh
    trait
        16
    trait  
       2018-12-03 10:21:22 +08:00   ❤️ 1
    楼主画个 timsort 吧,算是比较快的,好多语言的内置算法
    ilunny
        17
    ilunny  
       2018-12-03 10:26:58 +08:00 via Android
    为什么冒泡排序最好情况是 O(n)
    IdJoel
        18
    IdJoel  
       2018-12-03 11:27:01 +08:00   ❤️ 1
    非常棒 感谢
    CoderOnePolo
        19
    CoderOnePolo  
    OP
       2018-12-03 11:30:55 +08:00
    @vanishcode
    @IdJoel 感谢肯定,欢迎收藏关注。


    @trait 我研究一下


    @ilunny O(n)已经是很快的
    hxz6688
        20
    hxz6688  
       2018-12-03 11:52:41 +08:00   ❤️ 1
    感觉不错的
    daweii
        21
    daweii  
       2018-12-03 11:55:49 +08:00 via iPhone   ❤️ 1
    我的流量。。。
    CoderOnePolo
        22
    CoderOnePolo  
    OP
       2018-12-03 11:59:08 +08:00
    @hxz6688 谢谢肯定

    @daweii 流量是有点大,尴尬
    reself
        23
    reself  
       2018-12-03 13:24:30 +08:00 via Android   ❤️ 1
    @ilunny 至少要遍历一次数组才能知道是否有序
    KingHL
        24
    KingHL  
       2018-12-03 13:28:09 +08:00
    赞一个
    Mexion
        25
    Mexion  
       2018-12-03 13:28:50 +08:00
    先马克
    jevirs
        26
    jevirs  
       2018-12-03 13:36:09 +08:00
    内容不错哦,附上代码印象更加深刻
    CoderOnePolo
        27
    CoderOnePolo  
    OP
       2018-12-03 13:42:25 +08:00 via iPhone
    @jevirs 在公众号系列里每一个排序动画都配上了几种语言的代码实现,可以关注看看🤔
    loading
        28
    loading  
       2018-12-03 14:06:19 +08:00 via Android   ❤️ 1
    谷歌市场的算法动画的 app 是楼主的?

    我设置三大金刚键后,底下按钮被挡。
    CoderOnePolo
        29
    CoderOnePolo  
    OP
       2018-12-03 14:10:06 +08:00 via iPhone
    @loading 不是,我还没做过类似的 APP
    anonymous256
        30
    anonymous256  
       2018-12-03 14:25:25 +08:00 via Android
    有小地方想要较真一下。
    我们说一个算法的时间复杂度是一个关于问题规模的函数,大 O 的表示法已经是它最坏的情况(忽略系数)。如果要准确的计算一个算法再最好 /平均 /最坏的表现,应该用函数表示,不应该直接用 O 符号。参考算法导论的 T(n)表示法。
    anonymous256
        31
    anonymous256  
       2018-12-03 14:28:08 +08:00 via Android   ❤️ 1
    感觉每个图做成一个专题,旁边附上伪码(pseudocode),下面写上该算法的各种语言实现方式。一定很受学习者欢迎~
    CoderOnePolo
        32
    CoderOnePolo  
    OP
       2018-12-03 14:38:05 +08:00
    @anonymous256 目前每个图已经做成一个专题,这十个经典排序算法都用几种语言实现了,并且还配了伪码动画思路。文章在公众号里面可以看到^_^
    zwh2698
        33
    zwh2698  
       2018-12-03 15:49:32 +08:00 via Android   ❤️ 1
    赞👍
    hei1000
        34
    hei1000  
       2018-12-03 16:12:10 +08:00
    不写成文章吗,这个不好放到 pocket 里面去啊
    stebest
        35
    stebest  
       2018-12-03 17:17:16 +08:00   ❤️ 1
    归并排序实际上有两种方式,时间复杂度一致。但比如在对于处理链表排序时候,两种方式的空间复杂度分别为 O(nlogn)和 O(1)
    azhangbing
        36
    azhangbing  
       2018-12-03 17:29:44 +08:00 via iPhone   ❤️ 1
    不错不错
    july1995
        37
    july1995  
       2018-12-03 18:07:10 +08:00   ❤️ 1
    优秀,考研党正在复习数据结构的查找与排序。
    rayjoy
        38
    rayjoy  
       2018-12-03 20:20:36 +08:00
    做的很用心了,收藏一下。
    CoderOnePolo
        39
    CoderOnePolo  
    OP
       2018-12-03 20:24:31 +08:00 via iPhone
    @hei1000 文章都在微信公众号里面,以前发了几篇文章在这里,但感觉有点不好,就没全发。
    CoderOnePolo
        40
    CoderOnePolo  
    OP
       2018-12-03 20:26:43 +08:00
    @rayjoy
    @azhangbing 感谢肯定
    @july1995 希望对你有帮助,公众号里还有其他类似的数据结构分析,有时间也可以看看~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   961 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 21:16 · PVG 05:16 · LAX 14:16 · JFK 17:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.