动画 | 什么是归并排序？

阳光穿透心脏的1/2处 2023-06-23 12:52 17阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

来源 | 算法无遗策

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

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

归并操作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的末尾。

动画

Code

![format_png 1][]

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

1.左半边用尽，取右边的元素；

2.右半边用尽，取左边的元素；

3.右半边的当前元素小于左半边的当前元素，取右半边的当前元素；

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

自顶向下的归并排序（递归法）

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

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

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

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

递归：递归分解array\[low>>>mid\]和array\[mid+1>>>high\]；

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

动画

Code

![format_png 2][]

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

![format_png 3][]

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

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

Code

![format_png 4][]

自底向上的归并排序（迭代法）

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

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

归并：从子序列长度为1（length）开始，进行两两归并，得到2\*length的有序序列；

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

动画

Code

![format_png 5][]

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, 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\]

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 6][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKa1ZJVm1DS1BNQ2pCNktLSjd6WTBQZHcxZlJCSjc3OWpEUjNFWXNWM0thRTd3aWJ4aWMzWnUxYmZFejdjc0NURWljcDZpYzM0TG54RW1TYncvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKa1ZJVm1DS1BNQ2pCNktLSjd6WTBQZDZ0RHRyWEY4UUJKdWY5bm5Oemhxd2M4UVJqTXJvaWJpYW5IYTlOVGtFNUJVQkNkV2ljWGxPVUszdy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKa1ZJVm1DS1BNQ2pCNktLSjd6WTBQZGVGU1k4b29ZS3YzSGVtZGszeExaaEsxc1JFRG14MXh4NWxMZVZRbkpZVE1laWNnRWliT1FiVlRBLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKa1ZJVm1DS1BNQ2pCNktLSjd6WTBQZGd3VnVWTzkyaWJxV2dKaWN2WVB6bHBsYmVHUmZxaHU3NzdyRXdiS3JpYmlidjVibWVXeUVKOEpHR0EvNjQw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKa1ZJVm1DS1BNQ2pCNktLSjd6WTBQZENIR3dLWm9XNkd0a0NpYVFaM0JXelZNaWN3ZkFWdWlhUmRibG92dUpnNE1SZWZySk1yWnNDcGRkQS82NDA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png