125.【C语言】数据结构之归并排序递归解法
目录
1.前置知识
题目:重新排列数组
代码
提交结果
2.归并排序算法
复制的细节说明
时间复杂度
递归算法代码
1.二分区间,一一往下递归
2.两区间归并
3.返回条件
4.完整代码
递归调用展开图
5.思考题:如果元素的总个数不是偶数个
1.前置知识
题目:重新排列数组
https://leetcode.cn/problems/shuffle-the-array/description/
给你一个数组
nums，数组中有2n个元素，按[x1,x2,...,xn,y1,y2,...,yn]的格式排列。请你将数组按
[x1,y1,x2,y2,...,xn,yn]格式重新排列，返回重排后的数组。示例 1：
输入：nums = [2,5,1,3,4,7], n = 3 输出：[2,3,5,4,1,7] 解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]示例 2：
输入：nums = [1,2,3,4,4,3,2,1], n = 4 输出：[1,4,2,3,3,2,4,1]示例 3：
输入：nums = [1,1,2,2], n = 2 输出：[1,2,1,2]提示：
1 <= n <= 500nums.length == 2n1 <= nums[i] <= 10^3
代码
直译题目即可,选择另外开辟空间存储重新排列好的结果,之后拷贝回去的算法
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* shuffle(int* nums, int numsSize, int n, int* returnSize)
{int* arr=(int*)malloc(sizeof(int)*2*n);int i=0;int j=0;while(i<n){arr[j]=nums[i];arr[j+1]=nums[i+n];j+=2;i++;}*returnSize=numsSize;return arr;
}提交结果
2.归并排序算法
归并(Merge)含义:合并,而归并排序(Merge-Sort)是建立在归并操作上的一种排序算法.
算法的核心是分而治之(Divide and Conquer),即先使每个子序列有序,再使子序列段间有序,最后将已有序的子序列合并.得到完全有序的序列
例如给定一个无序含偶数个元素的数组arr={10,6,7,1,3,9,4,2},要求排升序,采用归并算法
发现数组有偶数个元素,因此可以均分,这种归并算法相对于含奇数个元素的数组较容易处理
均分的子序列分别为 {10,6,7,1}、{3,9,4,2}
但是拆分后的子序列并不有序,于是继续均分(递归)(不建议使用插入排序,速度太慢)
均分的子序列分别为 {10,6}、{7,1}、{3,9}、{4,2}
但是拆分后的子序列并不有序,于是继续均分
均分的子序列分别为 {10}、{6}、{7}、{1}、{3}、{9}、{4}、{2}
只含一个元素的子序列认为是有序的,于是停止均分
接着回归: 将子序列的左右的有序(左区间有序和右区间有序)部分合并成有序子序列,方法:依次比较,小的尾插到新空间(开一个临时数组,将归并的结果复制回去)
(调整顺序后合并,后将临时数组中的数据拷贝回原数组)
再
一个元素和一个元素归并-->两个元素和两个元素归并-->四个元素和四个元素归并-->......
可以看到整体的思路是先分解再合并
复制的细节说明
时间复杂度
每一层需要将归并好的结果尾插到临时开辟的空间,需要操作N个数,递归的层数为logN,两者相乘即为
递归算法代码
因为是递归,所以需要用到子函数,大致的框架为
#include <stdio.h>
void _mergesort(int* arr, int* tmp,int begin,int end)//要排序的闭区间[begin,end]
{//......
}void mergesort(int* arr, int size)
{//动态开辟临时数组int* tmp = (int*)malloc(sizeof(int) * size);if (tmp == NULL){perror("malloc fail");return;}_mergesort(arr,tmp,0,size-1);//传递要排序的闭区间[0,size-1]free(tmp);tmp = NULL;
}int main()
{int arr[] = {10,6,7,1,3,9,4,2};mergesort(arr, sizeof(arr) / sizeof(int));return 0;
}下面重点实现子函数_mergesort:
核心思想:先递归后归并
1.二分区间,一一往下递归
void _mergesort(int* arr, int* tmp,int begin,int end)//要排序的闭区间[begin,end]
{//返回条件://...... //二分区间,mid为分完后两区间的边界int mid = (begin + end) / 2;//[begin,mid]和[mid+1,end],下面递归两区间_mergesort(arr, tmp, begin, mid);_mergesort(arr, tmp, mid + 1, end);//归并//......
}2.两区间归并
初始化时,设指针begin1和end1分别指向第一个区间的首尾元素;指针begin2和end2分别指向第二个区间的首尾元素,可画图为:
利用前置知识讲的重新排列数组的算法,将归并的结果先拷贝到临时数组中,再将临时数组中的结果拷贝回原数组
先拷贝到临时数组中:
设指针i遍历原数组
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;//<=的原因:是闭区间.当begin1==end1或begin2==end2时,闭区间有一个元素
//可能存在左右区间有一个提前结束的情况,因此写的是&&
while (begin1 <= end1 && begin2 <= end2)
{if (arr[begin1] < arr[begin2])tmp[i++] = arr[begin1++];elsetmp[i++] = arr[begin2++];
}//不知道上个循环因为什么条件退出,因此判断两次
while (begin1 <= end1)tmp[i++] = arr[begin1++];
while (begin2 <= end2)tmp[i++] = arr[begin2++];再将临时数组中的结果拷贝回原数组:
因为是闭区间[begin,end],所以一共有end - begin + 1个元素需要拷贝
//注意必须要+begin,位置要对应上,不一定begin为0!
memmove(arr+begin, tmp+begin, sizeof(int) * (end - begin + 1));3.返回条件
当begin >= end时,函数返回,注意不是begin>end!!
if (begin >= end)return;如果begin==end仍然循环,计算出来的mid=(begin+end)/2=(2*begin)/2=begin
两个区间为[begin,begin]和[begin+1,begin],第二个区间是不存在的!
4.完整代码
代码添加了一些调试信息,利于分析复杂的多层递归
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void _mergesort(int* arr, int* tmp,int begin,int end)//要排序的闭区间[begin,end]
{//返回条件:if (begin >= end)return;//二分区间,mid为分完后两区间的边界int mid = (begin + end) / 2;printf("递推: [%d,%d] [%d,%d]\n", begin, mid, mid+1, end);//[begin,mid]和[mid+1,end],下面递归两区间_mergesort(arr, tmp, begin, mid);_mergesort(arr, tmp, mid + 1, end);//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;printf("回归: [%d,%d] [%d,%d]\n", begin1, end1, begin2, end2);//<=的原因:是闭区间.当begin1==end1或begin2==end2时,闭区间有一个元素//可能存在左右区间有一个提前结束的情况,因此写的是&&while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[i++] = arr[begin1++];elsetmp[i++] = arr[begin2++];}//不知道上个循环因为什么条件退出,因此判断两次while (begin1 <= end1)tmp[i++] = arr[begin1++];while (begin2 <= end2)tmp[i++] = arr[begin2++];memmove(arr+begin, tmp+begin, sizeof(int) * (end - begin + 1));//拷贝回原数组}void mergesort(int* arr, int size)
{//动态开辟临时数组int* tmp = (int*)malloc(sizeof(int) * size);if (tmp == NULL){perror("malloc fail");return;}printf("debug info:\n");_mergesort(arr,tmp,0,size-1);//传递要排序的闭区间[0,size-1]free(tmp);tmp = NULL;
}int main()
{int arr[] = {10,6,7,1,3,9,4,2};mergesort(arr, sizeof(arr)/sizeof(int));for (int i = 0; i < sizeof(arr) / sizeof(int); i++)printf("%d ", i);return 0;
}运行结果:
递归调用展开图
依照debug info的内容可以画出递归调用展开图,设递推用蓝色箭头,回归用绿色箭头
如果是16个数(为2的次方)排序,例如:int arr[] = {10,6,7,1,3,9,4,2,234,565,4,2,89,12,78,324};
结果为:
5.思考题:如果元素的总个数不是偶数个
仍然可以归并排序,只不过是不完全二分(可以理解为近似二分)
将代码提交到LeetCode的912. 排序数组题上:
void _mergesort(int* arr, int* tmp,int begin,int end)
{if (begin >= end)return;int mid = (begin + end) / 2;_mergesort(arr, tmp, begin, mid);_mergesort(arr, tmp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[i++] = arr[begin1++];elsetmp[i++] = arr[begin2++];}while (begin1 <= end1)tmp[i++] = arr[begin1++];while (begin2 <= end2)tmp[i++] = arr[begin2++];memmove(arr+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}void mergesort(int* arr, int size)
{int* tmp = (int*)malloc(sizeof(int) * size);_mergesort(arr,tmp,0,size-1);
}int* sortArray(int* nums, int numsSize, int* returnSize)
{*returnSize=numsSize;mergesort(nums,numsSize);return nums;
}
提交结果:
下篇文章讲讲非递归算法的代码