前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >动画 | 什么是归并排序?

动画 | 什么是归并排序?

作者头像
我脱下短袖
修改2019-12-27 11:52:09
6560
修改2019-12-27 11:52:09
举报
文章被收录于专栏:算法无遗策

归并排序的归并这两个字和递归没有关系,归并是将两个有序的数组归并成一个更大的有序数组,但整个排序算法是有可能跟递归有关系的。因为归并排序算法可以按照递归方式去解决,也可以按照迭代方式去解决。

递归方式是自顶向下的归并排序,迭代方式是自底向上的归并排序。这两种归并排序虽然实现方式不同,但是都是调用了核心的方法:归并操作。

归并操作merge

我们可以声明一个方法merge(数组对象, low, mid, high),假设array[low>>>mid]和array[mid+1>>>high]这两个序列都是有序的,在merge之前创建一个和array数组长度相同的空的辅助数组aux,然后在merge之后将原数组中的待排序列[low>>>high]拷贝到辅助数组aux,设置两个游标i和j分为位于aux[low>>>mid]和aux[mid+1>>>high]的起始位置。

辅助数组aux的任务有两项:根据游标i和j比较元素的大小;并在aux中逐个取得有序的元素放入原数组array相应的位置中。

如果aux的两段序列aux [low>>>mid]和aux [mid+1>>>high]中,其中一段已经全部放到原数组array中了,那么另一段剩余的序列直接放到原数组array的末尾。

动画

http://mpvideo.qpic.cn/0a78kidtzezfaciiaudq6dyjbehvhv75m5kovqfzaqeqabqbb4ga.f10002.mp4?dis_k=89418f862286ce13209f8607dadd31d6&dis_t=1577418578

Code

根据merge方法代码里条件,有4个判断情形:

1.左半边用尽,取右边的元素;

2.右半边用尽,取左边的元素;

3.右半边的当前元素小于左半边的当前元素,取右半边的当前元素;

4.右半边的当前元素大于等于左半边的当前元素,取左半边的当前元素。

自顶向下的归并排序(递归法)

自顶向下的归并排序的基于递归的,递归终止的条件是子序列长度为1。递归终止的条件是可以改的,如果在使用递归进行归并排序算法中,可能会遇到大量数据导致递归的使用过于频繁,从而导致性能消耗太大。

所以递归终止条件可以改为子序列长度为N(适量),然后这个子序列可以进行插排或者其它更合适的排序。

基于递归的归并排序算法的思想可以分为3个过程:

分解:将当前待排序列array[low>>>high]一分为二,分裂点在mid=low + (high - low) / 2;

递归:递归分解array[low>>>mid]和array[mid+1>>>high];

归并:达到终止条件后,可以进行归并操作,将两个已排序子序列归并成一个新的有序序列。

动画

http://mpvideo.qpic.cn/0af2oiibz45faayfbybqqbybbmafhwhwnvp7ae3uaebq6badbqda.f10002.mp4?dis_k=41af57f36a412b8120b17b3ce812b0b2&dis_t=1577418578

Code

Result

初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]

归并 [9, 13, 15, 11, 3, 7, 17, 5, 1]

归并 [9, 13, 15, 3, 11, 7, 17, 5, 1]

归并 [3, 9, 11, 13, 15, 7, 17, 5, 1]

归并 [3, 9, 11, 13, 15, 7, 17, 1, 5]

归并 [3, 9, 11, 13, 15, 1, 5, 7, 17]

归并 [1, 3, 5, 7, 9, 11, 13, 15, 17]

[1, 3, 5, 7, 9, 11, 13, 15, 17]

优化:对小规模子数组使用插排

如果数据量太大,可以进行更改递归终止条件,改为处理小规模的问题,这种方法可以改进大多数递归算法的性能

Code

优化:merge之前测试数组是否已经有序

达到递归终止条件后,进行归并操作之前,还少了一个判断的条件。如果array[mid]要小于等于array[mid+1],说明array[low>>>high]本身就是有序的了,可以直接跳过归并操作。这个改动不会影响递归的调用。

Code

自底向上的归并排序(迭代法)

自底向上的归并排序是基于循环的,它不像递归那样将一个大问题分割成一个个能解决的小问题,然后用所有小问题的答案来解决这个大问题。基于循环的算法是从无到有,从能解决的小问题开始,慢慢解决大问题。

基于迭代的归并排序可以分为两个过程:

归并:从子序列长度为1(length)开始,进行两两归并,得到2*length的有序序列;

循环:子序列长度改为2*length开始,进行两两归并,终止条件是直到原数组已经归并完毕。

动画

http://mpvideo.qpic.cn/0af2ygvmyu3f6cagaybqcbylbaff7vxrmnopso6rbaaaocqobudq.f10002.mp4?dis_k=335284abaaabaf6c67a4656e245fb9f1&dis_t=1577418578

Code

Result

初始状态 [13, 9, 15, 11, 3, 7, 17, 5, 1]

归并 [9, 13, 15, 11, 3, 7, 17, 5, 1]

归并 [9, 13, 11, 15, 3, 7, 17, 5, 1]

归并 [9, 13, 11, 15, 3, 7, 17, 5, 1]

归并 [9, 13, 11, 15, 3, 7, 5, 17, 1]

归并 [9, 11, 13, 15, 3, 7, 5, 17, 1]

归并 [9, 11, 13, 15, 3, 5, 7, 17, 1]

归并 [3, 5, 7, 9, 11, 13, 15, 17, 1]

归并 [1, 3, 5, 7, 9, 11, 13, 15, 17]

[1, 3, 5, 7, 9, 11, 13, 15, 17]

——END——

推荐阅读:

动画 | 什么是堆排序?

动画 | 什么是选择排序?

动画 | 什么是希尔排序?

动画 | 什么是插入排序?

动画 | 什么是快速排序?

动画 | 冒泡排序只是简单的冒泡排序吗?

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-12-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法无遗策 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档