​归并排序的核心就是将分割后的有序子序列合并成一个有序的序列。

给定一个无序的序列,分割成2段子序列,分割后,要开始合并2段子序列。而合并子序列的前提是子序列必须都是有序的,如果存在无序的子序列,那么将无序的子序列递归分割成更小的子序列,直到子序列有序。

分割后的子序列有序的条件是子序列只有一个元素,所以只有将无序序列的每个元素分割成一个序列,那么才可以开始合并。

 

所以归并排序的核心思路就是:

1.将无序的序列分成两部分

2.分割后的两段序列是否都是有序的

a.都有序,把两段序列合并成一个有序的序列

b.不全是有序,把无序的序列重复步骤1和步骤2,直到将无序序列分割后的子序列都有序为止(分割后的子序列有序只能是序列只有一个元素)。

 

合并2段子序列的思路:

1.申请一个临时数组,数组大小为能够容纳2段子序列,设置2个指针i,j,分别指向2段子序列的起始位置;

2.如果指针i指向的元素小于j指向的元素,把i指向的元素放入临时数组,i++,否则把j指向的元素放入临时数组,j++。直到其中一个指针已经遍历到序列的尾部才结束序列的元素比较。

3.结束比较后,如果其中某个指针尚未移至序列尾部,那么将序列剩下的元素放入数组中,完成合并。

 

所以代码就可以这么写。

 

 

推荐阅读:

堆排序其实没那么难

5分钟搞定快速排序

 

版权声明:本文为chicaizhangrou原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/chicaizhangrou/p/12181310.html