写给前面：
生活是活给自己看的，你有多大成色，世界才会给你多大脸色。——《人民日报》李
文章目录递归实现归并排序 归并排序基本思想
- 递归实现归并排序
- 归并排序基本思想
- 动图演示归并过程
- 参考代码
- ⏱️复杂度分析
- 非递归版本
- 分析
- ⏳注意细节
- 参考代码
- ⏱️复杂度分析
归并排序的基本思想就是：分治法
即：先使每一个子区间有序，然后再使这两个子区间合起来有序
所谓归并就是：
有两个数组，利用两个标记去遍历两个数组，每一次都把小的拿到第三个数组
最后得到的第三个数组就是一个升序数组
归并排序的方法类似于二叉树的后序遍历
-
分区间
- 找一个mid表示数组的中间位置把数组分为左右子区间
- 左右子区间递归找mid去不断分区间
- 直到区间长度为1，完成分区键
-
归并
- 从最小的子区间，把左右区间归并排序
- 然后返回上一层，把左右区间归并
- 反复如此
// 先划分区间 去递归左，然后递归右，最后再回来处理本层
// 归并的递归主要是完成区域的划分
// 排序是在最后的那一部分
void PartSort(int* a, int begin, int end, int* tmp)
{
//如果划分区间只有一个 就不需要再分割了，直接回去合并
if (begin >= end)
{
return;
}
//首先划分左右区间
int mid = (begin + end) / 2;
//[begin,mid],[mid+1,end]
PartSort(a, begin, mid,tmp);//[0,0]
PartSort(a, mid + 1, end,tmp);//[1,1]
//归并
//对[begin,mid]数组 和[mid+1,end]两个数组归并
//j为下一次放到tmp数组中的位置，应和这一次的区间的起始位置相同
int j = begin;
int begin1 = begin;//第一个数组的起始位置
int end1 = mid;//第一个数组的终止位置
int begin2 = mid + 1;//第二个数组的起始位置
int end2 = end;//第二个数组的终止位置
while(begin1<=end1 && begin2<=end2)//有一个数组走完就跳出循环
{
if (a[begin1] <= a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
//来到这说明有一个数组走完了
//如果数组1没走完，就继续把数组1的元素拿到tmp数组
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
//如果数组2没走完，就继续把数组2的元素拿到tmp数组
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
//最后把这一次归并后的数据 拷贝回a
//归并的哪部分就拷贝哪部分
//a的起始位置 tmp起始位置 此次数组的长度
memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
//首先开辟一个额外数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
exit(-1);
}
//进行排序
PartSort(a, 0, n-1, tmp);
//最后free掉tmp数组
free(tmp);
}
⏱️复杂度分析
时间复杂度
归并排序每一次都是直接找中间位置，然后进行划分左右子区间
所以基本上每一次都是二分
递归log N层
每一层划分多个子区间，一层的所有子区间合计为N的时间复杂度
所以总计时间复杂度为 O(N*logN)
空间复杂度
归并排序需要借助一个 辅助数组 来进行归并
所以额外空间为O(N)
即空间复杂度为O(N)
我们知道快速排序是可以利用栈的性质来进行非递归的改版的
但是归并不一样！
归并属于后序方式遍历
所以不适合用栈
因为栈适合前序，处理完当前就扔了，递归左右子区间
但是后序的话，通过栈可以把区间分出来，但是 如果返回去的时候，如何找到上一个较大的区间来进行归并呢？
如：[0,0] ,[1,1]无法再分区间了，开始需要对[0,1]进行归并排序，找不回去了！
那么归并的非递归如何实现呢？
我们可以利用直接分组
：归并无非就是每一次把两个小数组进行排序然后合并到原数组中
- 我们利用一个gap标识每一次小数组的长度，gap从1开始，即每一次对两个长度为1的数组归并
- 第一个小数组:[begin1,end1],第二个小数组:[begin2,end2]
- 利用begin1来遍历数组，把每一对小数组都进行归并，并拷贝到tmp数组
- 然后gap*2，改变两个小数组的长度，重复上面的过程
- 直到gap>=数组长度n,此时已经把全部元素归并了
画图分析：
我们以gap==1和gap==2为例
- gap==1
- gap==2
划分完子区间之后，有这样四个值
[begin1, end1]
[begin2,end2]
end1 = begin1 + gap-1 :因为[begin1,end1]之间有gap个元素
begin2 = begin1 + gap :因为begin1与begin2之间隔着一个gap个元素的数组
end2 = begin2 + gap-1 :同理因为[begin2,end2]之间有gap个元素
因为begin1在for循环内部
所有begin1的范围一定是[0,n-1]之间
但是 end1，begin2，end2 都有可能越界
所以 麻烦就在这里：需要对不同情况进行判断和处理
我们需要对边界进行修正：谁越界了修正谁
- begin2越界
如果begin2越界那么 end2也一定越界了，只需要让该数组2不存在即可
如图：
2.end1越界
如果end1越界，说明begin2，end2也一定越界了
那么只需要让end1改为数组最后一个坐标
然后让begin2>end2 使第二个数组不存在即可
如图
3. end2越界
如果end2越界，说明第一个数组是没有问题的，数组2越界
只需要修改一下数组2的终止位置为n-1即可，让数组2合法
//归并排序 非递归版本1
void MergeSortNoRe(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
exit(-1);
}
int gap = 1;
while (gap
for (int i = 0; i < n; i+=2*gap)
{
int begin1 = i;//i为左数组的起始位置
int end1 = begin1 + gap - 1;//每一组有gap个元素，gap-1是为了 不算begin1位置
int begin2 = begin1 + gap;//begin1与begin2之间有 gap个元素
int end2 = begin2 + gap - 1;//第二组也有gap个元素
//修正区间
if (end1 >= n)
{
end1 = n - 1;
begin2 = n;
end2 = n - 1;//让数组2不存在
}
else if (begin2 >= n)
{
end2 = n - 1;//让数组2不存在
}
else if (end2 >= n)
{
end2 = n - 1;
}
//分完区间之后，归并
int j = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
}
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
free(tmp);
}
⏱️复杂度分析
由于非递归版本每一次其实并不是完美的二分
所以时间复杂度略有差异
但是总体还是O(N*logN)
✨感谢阅读~ ✨
❤️码字不易，给个赞吧~❤️
