归并排序详解
思路
归并排序的总思想是分而治之，把数组分成一小块一小块排序，然后再有序地排成一个大数组。
它的分块有点像二分查找那样，从中间分开数组，然后在剩下一半的数组中继续分，直到分成二个元素为止，就开始比较这两个元素，从小到大排列。两个元素排列完之后又回到4个元素的状态,继续排序,直到慢慢恢复成整个数组排序.
在排序的时候,有序的部分会先放到临时的temp数组,然后再放回原数组.
图解
归并排序有递归和非递归两种写法，下面我们逐一介绍
递归写法
下面有两个函数, _MergeSort函数是具体的归并过程, MergeSort函数则提供了一个实现归并排序的框架.
代码中有具体注释,大家请看...
//传参:原数组,临时数组,数组头,数组尾
void _MergeSort(int* a, int* temp, int begin, int end)
{
//结束递归的条件:当数组中只有一个元素时,即begin==end 时,无法排序,就可以结束递归了
if (begin >= end)
{
return;
}
//把数组分成两半,mid是数组的中间下标
int mid = (end + begin) / 2;
//开始递归
_MergeSort(a, temp, begin, mid);//数组前半部分
_MergeSort(a, temp, mid + 1, end);//数组后半部分
//数组前半部分的头和尾
int begin1 = begin, end1 = mid;
//数组后半部分的头和尾
int begin2 = mid+1, end2 = end;
//这里有讲究,end1不能写成等于mid-1, begin2不能写成mid,
//i用于temp数组放入数据
int i = begin;
//开始排序
while (begin1 <= end1 && begin2 <= end2)
{
//谁小放谁
if (a[begin1] <= a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
//跳出循环之后,要么两组数据都放完到temp数组了,要么还有一组的数据没有放完,我们还要接着放
//下面两个循环,只会进入一个
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
//把数据搬到原数组
memcpy(a + begin, temp + begin, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* a, int n)
{
//开辟临时数组
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail");
}
//调用归并排序函数
_MergeSort(a, temp, 0, n - 1);
//释放临时数组,并置空
free(temp);
temp = NULL;
}注意事项
解释一下, 为什么在分数组的时候, end1不能写成等于mid-1, begin2不能写成mid.
假设我们使用这一种分割数组的方式
//数组前半部分的头和尾
int begin1 = begin, end1 = mid-1;
//数组后半部分的头和尾
int begin2 = mid, end2 = end;如下图:
分到后面就会陷入死循环,大家可以自己计算mid,自己分割一下数组感受一下.
非递归写法
void MergeSortNonR(int* a, int n)
{
//开辟临时数组
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc fail");
}
//gap的作用就是分割数组,从小块到大块
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i+=2*gap)
{
//其实当gap=1的时候,begin1=end1,begin2=end2,不会进行排序,真正的排序从gap=2开始
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//j的作用是记录temp数组数据的存放
int j = i;
//结束本次排序的条件
if (begin2 >= n)
{
break;
}
//分到最后,万一数组的尾部不是gap的倍数,就要改变end2,让end2等于数组的最后一个元素
if (end2 >= n)
{
end2 = n - 1;
}
//开始比较排序, 把有序数据放进temp数组
while (begin1 <= end1 && begin2<= end2)
{
if (a[begin1] <= a[begin2])
{
temp[j++] = a[begin1++];
}
else
{
temp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[j++] = a[begin2++];
}
//把有序后的数据移回原数组
memcpy(a + i, temp + i, sizeof(int) * (end2 - i + 1));
}
//gap的范围扩大,数组的有序程度会增大,直到彻底排好序
gap *= 2;
}
free(temp);
temp = NULL;
}
原文地址：https://blog.csdn.net/2301_79894844/article/details/143960684
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！