摘要：归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
本文分享自华为云社区《一看就懂 ！ 图解归并排序》，作者： bigsai 。
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序的主要思想是分治法。主要过程是：
1. 将n个元素从中间切开，分成两部分。
2. 将剩下的数组通过递归的方式一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了。
3. 从最底层开始逐步合并两个排好序的数列。把两个数组大小为1的合并成一个大小为2的有序数列，再把两个大小为2有序数列的合并成4的有序数列 … 直到全部小的数组合并起来。
那么如何将两个有序数列合成一个有序的数列呢？
我们举个栗子把，一看就懂啦。
例如有数组 arr [3,7,8,10,2,4,6,9]; 我们可以把这个数组分成两个有序的子序列。
分别为 [3, 7, 8, 10] 和 [2, 4, 6, 9]，并将其合并为有序序列[2,3,4,6,7,8,9,10]。
把这两个小的数组拆分为 left 数组和 right 数组。如下图所示，使用 i 指向 left 的第一个元素， 使用 j 指向 right 的第一个元素。
建立一个空数组 arr ,使用 k 指向数组第一个元素。
比较 i 和 j 所指数字，将小的数字放在 k 所指位置。同时将小的数字所指位置和 k 所指位置向右移一位。
2 < 3 , 将 2 填入 arr 数组 ，同时右移 j 和 k。
3 < 4 , 将 3 填入 arr 数组 ，同时右移 i 和 k。
4 < 7，将 4 填入 arr 数组，同时右移 j 和 k。
6 < 7，将 6 填入 arr 数组，同时右移 j 和 k。
7 < 9，将 7 填入 arr 数组，同时右移 i 和 k。
8 < 9，将 8 填入 arr 数组，同时右移 i 和 k。
10 > 9，将 9 填入 arr 数组，同时右移 j 和 k。
可以发现此时 right 数组已经填完了，所以此时只需要把 left 数组剩下的数字填入 arr 即可。
一顿操作猛如虎，这样就把两个有序的数组通过归并的方式排好顺序啦，是不是很赞。
那么问题来了，难道归并排序只能排这种有序的数组么？
那出现一个无序的数组该咋办呢？例如这个数组现在变为 arr [8,7,2,10,3,9,4,6];
此刻需要运用分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
其实上面第三部分就是治(conquer)的过程，将两个有序的序列合成为一个有序的序列。
#include <stdio.h>
void merge(int arr[], int L, int M, int R) {
int LEFT_SIZE = M - L;
int RIGHT_SIZE = R - M + 1;
int left[LEFT_SIZE];
int right[RIGHT_SIZE];
int i, j, k;
// 填充左边的数组
for (i=L; i<M; i++){
left[i-L] = arr[i];
}
// 填充右边的数组
for (i=M; i<=R; i++){
right[i-M] = arr[i];
}
// for (int i=0; i<LEFT_SIZE; i++){
// printf("%d\n",left[i]);
// }
//
// for (int i=0; i<RIGHT_SIZE; i++){
// printf("%d\n",right[i]);
// }
// 合并数组
i = 0; j = 0; k = L;
while (i < LEFT_SIZE && j < RIGHT_SIZE){
if (left[i] < right[j]){
arr[k] = left[i];
i++;
k++;
}else{
arr[k] = right[j];
j++;
k++;
}
}
while(i < LEFT_SIZE){
arr[k] = left[i];
i++;
k++;
}
while(j < RIGHT_SIZE){
arr[k] = right[j];
j++;
k++;
}
}
void mergeSort(int arr[], int L, int R){
if (L == R){
return;
}else{
int M = (L + R) / 2;
mergeSort(arr,L,M);
mergeSort(arr, M+1,R);
merge(arr, L, M+1,R);
}
}
int main(){
// int arr[] = {3,7,8,10,2,4,6,9};
int arr[] = {8,7,2,10,3,9,4,6};
int L = 0;
int M = 4;
int R = 7;
mergeSort(arr,L,R);
for (int i=0; i<=R; i++){
printf("%d\n",arr[i]);
}
}输出：
时间复杂度：O(nlogn)。
空间复杂度：O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序。
稳定性：稳定，因为交换元素时，可以在相等的情况下做出不移动的限制，所以归并排序是可以稳定的。
归并排序需要一个跟待排序数组同等空间的临时数组，因此，使用归并排序时需要考虑是否有空间上的限制。如果没有空间上的限制，归并排序是一个不错的选择。
微信关注我们
转载内容版权归作者及来源网站所有！
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。
为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。
Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。
Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。
扫码在手机上查看文章
扫描二维码，手机阅读更方便
有任何问题或合作意向欢迎联系我们
Email: 99873273@qq.com
QQ: 99873273