前面的文章中 我们详细介绍了排序的概念，插入排序，交换排序与选择排序，大家可以通过下面的链接再去学习：
这篇文章就详细介绍一下另一种排序算法：归并排序。
一，基本概念
归并：将两个或两个以上的有序表组合成一个新有序表
2-路归并排序
排序过程
初始序列看成n个有序子序列，每个子序列长度为1
两两合并，得到 ë n/2 û 个长度为2或1的有序子序列
再两两合并，重复直至得到 一个 长度为 n 的有序序列为止例：
将两个顺序表合成一个有序表
两个有序子序列的归并
设两个有序表存放在同一数组中相邻的位置上：R[low..mid]和R[mid + 1..high]
每次分别从两个表中取出一个记录进行关键字的比较，将较小者放入T[1ow..high]中
重复 此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到 T 中在代码中实现：
void Merge(RedType R[],RedType &T[],int low,int mid,int high)
{ i=low;j=mid+1;k=low;
while(i<=mid&&j<=high) //将R中记录由小到大地并入T中
{ if(R[i].key<=R[j].key) T[k]=R[i++];
else T[k]=R[j++]; }
while(i<=mid) T[k++]=R[i++]; //将剩余的R[low..mid]复制到T中
while(j<=high) T[k++]=R[j++];//将剩余的R[j.high]复制到T中
}
归并排序的递归
2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时，递归结束，否则：
① 将当前序列一分为二，求出分裂点mid = (low+high)/2；
② 对子序列R[low..mid]递归，结果放入S[low..mid]中；
③ 对子序列R[mid + 1..high]递归，结果放入S[mid + 1..high]中；
④ 调用算法 Merge ，将 S[ low..mid ] 和 S[mid + 1..high] 归并 T[ low..high ] 。具体的代码实现递归过程：
void MSort(RedType R[],RedType &T[],int low,int high)
{ if(low==high) T[low]=R[low];
else
{
mid=(low+high)/2; //将当前序列一分为二，求出分裂点mid
MSort(R,S,low,mid); //R[low..mid]递归，结果放入S[low..mid]
MSort(R,S,mid+1,high);//R[mid+1..high]递归，结果放入S[mid+1..high]
Merge(S,T,low,mid,high);//将S[low..mid]和S[mid+1..high]归并到T[low..high]
}
}
下面是一段完整的归并排序实例：
#include <stdio.h>
// 合并两个子数组的函数
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1; // 左子数组的大小
int n2 = r - m; // 右子数组的大小
int L[n1], R[n2]; // 创建临时数组
// 复制数据到临时数组 L[] 和 R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// 合并临时数组回 arr[l..r]
i = 0; // 初始化第一个子数组的索引
j = 0; // 初始化第二个子数组的索引
k = l; // 初始化合并后的子数组的索引
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制 L[] 的剩余元素（如果有的话）
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制 R[] 的剩余元素（如果有的话）
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序的主函数
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // 计算中间点
mergeSort(arr, l, m); // 递归排序左半部分
mergeSort(arr, m + 1, r); // 递归排序右半部分
merge(arr, l, m, r); // 合并左右两部分
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("给定的数组是 ：");
for (int i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
mergeSort(arr, 0, arr_size - 1); // 对整个数组进行归并排序
printf("排序后的数组是： ");
for (int i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
return 0;
}
算法分析
时间效率：O(nlog2n)
空间效率：O（n）
稳 定 性：稳定
到此归并排序就结束了， 如果文章对你有用的话请点个赞支持一下吧！
标签：归并,..,int,mid,high,low,排序 From： https://blog.csdn.net/Blusher1/article/details/140396637