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

五分钟看会一个有意思的分治思想排序:归并排序

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

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

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

    归并排序( Merge sort )是建立在归并操作上的一种有效的排序算法。该算法是采用分治法( Divide and Conquer )的一个非常典型的应用。

    作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

    • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
    • 自下而上的迭代;

    和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

    算法步骤

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;

    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

    4. 重复步骤 3 直到某一指针达到序列尾;

    5. 将另一序列剩下的所有元素直接复制到合并序列尾。

    来源: https://github.com/hustcc/JS-Sorting-Algorithm

    算法演示

    排序动画过程解释

    1. 首先,将数字分割成两片区域

    2. 将数字分割成两片区域

    3. 。。。。。。

    4. 直到每片区域只有一个元素

    5. 分割完成

    6. 接下来,将分割的每片区域进行合并组合

    7. 合并时,按照数字的升序移动,使得合并后的数字在组内按升序排列

    8. 当合并包含多个数字的组时,比较开头的数字,移动其中较小的数字

    9. 比如在动画中,比较开头的 4 和 3

    10. 其中 4 大于 3, 因此移动 3

    11. 按照同样的逻辑去比较该列剩余的头数

    12. 4 小于 7,所以移动 4

    13. 。。。。。。

    14. 递归的重复组的合并操作,直到所有数字都在一个组中。

    15. 完成 归并排序 啦~

    代码实现

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

    C++代码实现

    C++代码实现

    Java 代码实现

    Java 代码实现

    Python 代码实现

    Python 代码实现

    JavaScript 代码实现

    JavaScript 代码实现 如果你是 iOS 开发者,可以在 GitHub 上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。 你可以关注公众号 五分钟学算法 获取更多排序内容。

    14 条回复    2018-12-03 20:28:16 +08:00
    labnotok
        1
    labnotok  
       2018-11-28 09:19:29 +08:00 via Android
    支持一下
    z0z
        2
    z0z  
       2018-11-28 09:25:43 +08:00
    多谢分享,已关注。
    CoderOnePolo
        3
    CoderOnePolo  
    OP
       2018-11-28 09:34:38 +08:00 via iPhone
    @labnotok 来一起学习,一起进步🤔
    CoderOnePolo
        4
    CoderOnePolo  
    OP
       2018-11-28 09:34:51 +08:00 via iPhone
    @z0z 谢谢🤝
    wysnylc
        5
    wysnylc  
       2018-11-28 10:31:09 +08:00
    分而治之
    pwstrick
        6
    pwstrick  
       2018-11-28 17:28:05 +08:00
    支持
    CoderOnePolo
        7
    CoderOnePolo  
    OP
       2018-11-28 17:36:01 +08:00 via iPhone
    @wysnylc 分久必合合久必分
    CoderOnePolo
        8
    CoderOnePolo  
    OP
       2018-11-28 17:36:32 +08:00 via iPhone
    @pwstrick 欢迎关注,一起学习
    stevenbipt
        9
    stevenbipt  
       2018-11-28 21:28:11 +08:00 via Android
    说好的桶排序呢~
    CoderOnePolo
        10
    CoderOnePolo  
    OP
       2018-11-28 23:03:03 +08:00 via iPhone
    @stevenbipt 明天早上 8 点 30 公众号更新🤔
    CoderOnePolo
        11
    CoderOnePolo  
    OP
       2018-11-29 09:01:34 +08:00
    @stevenbipt 老哥,我刚刚更新桶排序了,可以去看看
    stevenbipt
        12
    stevenbipt  
       2018-11-29 09:36:03 +08:00 via Android
    labnotok
        13
    labnotok  
       2018-11-29 14:39:07 +08:00 via Android
    能否用加入控件实现单步执行的效果呢
    应该会比 GIF 好很多
    CoderOnePolo
        14
    CoderOnePolo  
    OP
       2018-12-03 20:28:16 +08:00
    @labnotok 目前动画都是 PPT 实现的,之前有考虑过单步执行,也写过小程序,但发现做下去效率太低了,遂放弃。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3188 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 14:27 · PVG 22:27 · LAX 07:27 · JFK 10:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.