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 <= 500
• nums.length == 2n
• 1 <= 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++];
	else
		tmp[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++];
		else
			tmp[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++];
		else
			tmp[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;
}

提交结果:

下篇文章讲讲非递归算法的代码