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

冷不防 2022-11-10 00:56 238阅读 0赞

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

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

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

自下而上的迭代；

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

算法步骤

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

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

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

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

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

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

算法演示

![616e5df74445a5dafeee0bb56c289fd9.gif][]

排序动画过程解释

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

将数字分割成两片区域

。。。。。。

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

分割完成

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

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

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

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

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

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

4 小于 7 ，所以移动 4

。。。。。。

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

完成 归并排序

代码实现

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

C++代码实现

![747b341c15fb8b71e451ceda42efe481.png][]

Java代码实现

![b59ff4171af1a965fd1ce65f64488a10.png][]

Python代码实现

![21b9518e7f302bf418197d5f0c4973f4.png][]

JavaScript代码实现

![7586df043f973860ce6d7e5d8303e015.png][]

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

[616e5df74445a5dafeee0bb56c289fd9.gif]: /images/20221023/4ba98c6b068c474c92051d2eb7d5985f.png
[747b341c15fb8b71e451ceda42efe481.png]: /images/20221023/d9e7df5cc3bf445e8a4e3602d79750e3.png
[b59ff4171af1a965fd1ce65f64488a10.png]: /images/20221023/e37b7e75f14f477d8f6c441cec5624bf.png
[21b9518e7f302bf418197d5f0c4973f4.png]: /images/20221023/a6b761e429844339938e0b2a8b990e8f.png
[7586df043f973860ce6d7e5d8303e015.png]: /images/20221023/8bf664ccb3d44d2698962751b9be4387.png

发表评论取消回复

表情：

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

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

相关阅读

相关常见排序算法之归并排序——归并排序

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5L-d5oqk5bCP5ZGo4YOm_size_20_colo

Bertha 。/ 2023年10月03日 19:34/ 0 赞/ 116 阅读

相关二分查找、快速排序、归并排序（分而治之）

顺序查找 1. 如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。 2. 如果线性表有序，但采用链式存储结构

青旅半醒/ 2023年07月04日 08:35/ 0 赞/ 79 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关 java排序--归并排序

1.概念: 归并（Merge）[排序][Link 1]法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序

谁践踏了优雅/ 2022年09月20日 05:48/ 0 赞/ 295 阅读

相关排序-归并排序-Java

归并是利用二叉树的思想来实现将一个数组分成2个，再次分，再次分。一直分，然后再利用递归来实现。1个和另一个组成一个，两个再与另外两个有序的组成一个大的。一直进行下去。 !

女爷i/ 2022年06月15日 10:39/ 0 赞/ 366 阅读

相关归并类排序-----归并排序

/归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合

绝地灬酷狼/ 2022年05月03日 01:56/ 0 赞/ 389 阅读

相关归并排序——二路归并排序

/ 归并：指将两个或者两个以上的有序表合并成一个新的有序表二路归并算法思想：将长度为n的待排序数据表看

分手后的思念是犯贱/ 2022年03月20日 02:54/ 0 赞/ 436 阅读