java动画演示归并排序_【图解数据结构】一组动画演示归并排序

迈不过友情╰ 2022-11-10 00:57 172阅读 0赞

前言

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

归并排序

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

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

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

自下而上的迭代；

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

算法步骤

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

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

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

重复步骤 3 直到某一指针达到序列尾；

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

算法演示

![73bbbe2e3386?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][73bbbe2e3386_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

image

排序动画过程解释

首先，将数字分割成两片区域

将数字分割成两片区域

。。。。。。

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

分割完成

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

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

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

比如在动画中，比较开头的 4 和 3

其中 4 大于 3， 因此移动 3

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

4 小于 7 ，所以移动 4

。。。。。。

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

完成 归并排序 啦~

代码实现

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

C++代码实现

![73bbbe2e3386?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][73bbbe2e3386_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

C++代码实现

Java代码实现

![73bbbe2e3386?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][73bbbe2e3386_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

Java代码实现

Python代码实现

![73bbbe2e3386?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][73bbbe2e3386_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

Python代码实现

JavaScript代码实现

![73bbbe2e3386?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][73bbbe2e3386_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

JavaScript代码实现

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

如果你想获取高清的动画演示，在 五分钟学算法 公众号里回复 归并排序 即可。

[73bbbe2e3386_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]: /images/20221023/d1a1e352eb91412f966a931386a0bc01.png

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关动画 | 什么是归并排序？

点击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![format_png][] 来源 | 算法无遗策归并排序的归并这两个字和递归没有

阳光穿透心脏的1/2处/ 2023年06月23日 12:52/ 0 赞/ 38 阅读

相关图解归并排序

基本思想　　归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divid

痛定思痛。/ 2023年06月13日 09:20/ 0 赞/ 13 阅读

相关看动画学算法之:排序-归并排序

文章目录简介归并排序的例子归并排序算法思想归并排序的java实现归并排序的时间复杂度简介归并排序简称Merge sor

比眉伴天荒/ 2023年02月28日 01:44/ 0 赞/ 30 阅读

相关【数据结构】归并排序

1 基本思想归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有

心已赠人/ 2023年02月26日 04:21/ 0 赞/ 43 阅读

相关 java动画演示归并排序_【图解数据结构】一组动画演示归并排序

前言由于LeetCode上的算法题很多涉及到一些基础的数据结构，为了更好的理解后续更新的一些复杂题目的动画，推出一个新系列 -----《图解数据结构》，主要使用动画来描述常

迈不过友情╰/ 2022年11月10日 00:57/ 0 赞/ 173 阅读

相关 java动画演示归并排序_分而治之，归并排序的动画演示

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

冷不防/ 2022年11月10日 00:56/ 0 赞/ 178 阅读

相关数据结构 — 归并排序

归并排序基本思想归并排序是建立在二路归并和分治法的基础上的一个高效排序算法, 将已有序的子

秒速五厘米/ 2022年06月09日 06:52/ 0 赞/ 266 阅读

相关图解"数据结构--内部排序算法"----归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成

叁歲伎倆/ 2022年05月18日 01:51/ 0 赞/ 290 阅读

相关数据结构-归并排序

　　归并排序的基本思想：首先，将R\[0..n-1\]看成是n个长度为1的有序表，将相邻的有序表进行归并，得到n/2个长度为2的有序表；然后，再将这些有序表成对归并，得到n/4

Love The Way You Lie/ 2021年11月19日 14:06/ 0 赞/ 368 阅读

相关数据结构（十一）：归并排序

利用递归与分治技术将数据序列划分成越来越小的半子表，在对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列直接插入排序例子流程：

青旅半醒/ 2021年09月10日 06:14/ 0 赞/ 487 阅读