[数据结构与算法]归并排序算法（merge sort）

前言：

归并排序算法，是10大经典排序算法之一，后续会更新其他的算法，本博客的全部代码以及图片实例都来里于b站，排序算法：归并排序【图解+代码】_哔哩哔哩_bilibili，但是本人已经理解了代码的所有内容，下面是我根据up主的视频自己的思考过程。我也看了其他人的代码，但是感觉这个up主的代码更能锻炼我最近所学的东西，由于时间复杂度和空间复杂度还没有深入接触，本文暂时先不写，后续会更新。

目录

? ? ? ? ?1：全部代码

2：归并排序的思想

3：递归算法的基本思路与关键

4:图解（详细去看上面b站的链接）

5：代码分析

1：全部代码

#include<stdio.h>
#include<stdlib.h>
void my_printf(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
//合并
void merge(int arr[], int tempArr[], int mid, int left, int right) {
	//标记左区域第一个未排序的元素
	int l_pos = left;
	//标记右区域第一个未排序的元素
	int r_pos = mid + 1;
	//辅助数组元素下标,只需从最左面开始即可
	int pos = left;
	//合并
	while (l_pos <= mid && r_pos <= right) {
		if (arr[l_pos] < arr[r_pos])
			tempArr[pos++] = arr[l_pos++];
		else
			tempArr[pos++] = arr[r_pos++];
	}

	//合并左区域剩余元素
	while (l_pos <= mid) {
		tempArr[pos++] = arr[l_pos++];
	}
	//合并右区域剩余元素
	while (r_pos <= right) {
		tempArr[pos++] = arr[r_pos++];
	}
	//将辅助数组中合并后的元素覆盖给原数组中
	/*while (left <= right) {
		arr[left] = tempArr[left];
		left++;
	}*/
	for (int i = 0; i <= right; i++) {
		arr[i] = tempArr[i];
	}
}
//归并排序之递归拆分
void msort( int arr[], int tempArr[],  int left, int right) {
	if (left < right) {

		int mid = left + (right - left) / 2;
		//将左区域递归拆分
		msort(arr, tempArr, left, mid);
		//将右区域递归拆分
		msort(arr, tempArr, mid + 1, right);
		//将左右合并
		merge(arr, tempArr, mid, left, right);
	}
}


//归并排序的入口
void merge_sort(int arr[], int n) {
	//构造辅助数组
	int* tempArr = (int*)malloc(n * sizeof(int));
	if (tempArr) {
		int left = 0, right = n - 1;
		msort(arr, tempArr,  left,right);
		//释放辅助数组
		free(tempArr);
	}
	else {
		printf("error,failed to creat a space!!!");
	}

}
int main() {
	int arr[] = { 9,5,2,7,12,4,3,1,11 };
	int n = 9;
	my_printf(arr, n);
	merge_sort(arr, n);
	my_printf(arr, n);
	return 0;
}

2：归并排序的思想

归并排序运用了，分治和递归的思想，通常来说，能分治一定能递归，但是能递归不一定能分治，但是这种说法并不准确，分治是一种算法，递归是具体的代码实现，所以像这样说会更好，分治算法一般用递归实现

这个博客里面讲的很好(37条消息) 分治算法详解_K神丶的专栏-CSDN博客

递归和分治都具有这样的特征：将一个大问题分解成若干个规模较小的相同问题

能否用分治的关键是，子问题的解是否可以合并成原问题的解

3：递归算法的基本思路与关键

1：需要一个新数组来存放已经排好的原数组里面的元素，这个数组可以用malloc函数开辟，新数组是在合并的时候才发挥作用

2：划分的时候需要折半递归，在这步中的关键是折半时候边界的问题

3：合并是这个算法的关键，在合并的过程中，需要比较左半区域和右半区域每个元素的大小，将较小的元素放入新数组中，但是总会有一个元素被剩下来（这个在代码分析中说），将剩下的元素放进新数组里。

4:图解（详细去看上面b站的链接）

?

5：代码分析

int main() {
	int arr[] = { 9,5,2,7,12,4,3,1,11 };
	int n = 9;
	my_printf(arr, n);
	merge_sort(arr, n);
	my_printf(arr, n);
	return 0;
}

这个是，打印数组元素的函数，都能看懂，这样写是因为可以少写一次打印函数的代码

void my_printf(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

下面就是主函数里面的第二个函数，这个函数的作用是开辟一个和原数组相同大小的空间，在msort函数调用结束后，释放掉用malloc函数开辟的空间（使用malloc函数要引用#include<stdlib.h>这个头文件或者其他的头文件）if语句的作用是判断开辟空间是否成功

在给msort函数传参的时候要将原数组，新数组，左下标，右下标，都传进去，（新数组要在合并过程中才能被用到），因为在接下来的折半递归中会用到下标

//归并排序的入口
void merge_sort(int arr[], int n) {
	//构造辅助数组
	int* tempArr = (int*)malloc(n * sizeof(int));
	if (tempArr) {
		int left = 0, right = n - 1;
		msort(arr, tempArr,  left,right);
		//释放辅助数组
		free(tempArr);
	}
	else {
		printf("error,failed to creat a space!!!");
	}

}

?这个就是折半递归函数的具体实现过程，用递归来实现，而递归最重要的就是结束条件，而结束条件就是left>=right

大于的时候，这个数组不存在

left=right时候，左下标和右下标指向同一个元素，证明数组里就一个元素，所以不能用这个函数

而left<right，代表这数组里面至少有两个元素，可以进行折半查找

在第一次折半递归的时候，左下标是left=0,右下标是right=n-1;

第二次的时候，左边区域的左下标是left=0,右下标是right=mid；（mid（中间元素下标）是向下取整的得到的，这个元素归左区域，所以右下标是mid）右边区域左下标是left=mid+1,右下标是right

......以此类推直到不满足递归条件

而函数merge是对已经拆分好的元素进行重新排序，我们需要把原数组和新数组，还有左右下标以及中间下标传进去，因为左右区域的第一个元素的下标需要用left,mid表示，而右下标代表着循环停止的条件（看下一个函数）

//归并排序之递归拆分
void msort( int arr[], int tempArr[],  int left, int right) {
	if (left < right) {

		int mid = left + (right - left) / 2;
		//将左区域递归拆分
		msort(arr, tempArr, left, mid);
		//将右区域递归拆分
		msort(arr, tempArr, mid + 1, right);
		//将左右合并
		merge(arr, tempArr, mid, left, right);
	}
}

?合并是归并排序算法的核心，而合并的关键在于，左区域和右区域的元素那个先放在新数组里

首先我们需要左区域第一个未排序元素的下标，右区域第一个未排序元素的下标，以及新数组第一个元素的下标

这些都定义好后，我们需要将左右区域的元素按照一定的顺序放到新数组里面，因此要判断谁先放进去，而每放一个新元素新数组的下标就要+1，而左右区域拿走元素的那个区域的下标也要+1，因此会出现循环体里面的代码。将上述的内容用代码实现放进一个while循环里面，而循环继续的条件是左区域或者右区域都要有元素，因为两边要比较嘛，所以在左右区域最总会剩下一个元素在原来的数组里，假设剩下的是右边的最后一个元素，此时他的下标是right，因为上一个右区域的元素放进新数组里后数组下标++了，将第一个while循环里面右边的条件构成一个新的条件，组成一个while循环，并将剩余的元素放进新数组里面。

注意后面的两个while只能有一个能够执行

最后就是将已经在新数组里面排好序的元素放进原先的数组里面

//合并
void merge(int arr[], int tempArr[], int mid, int left, int right) {
	//标记左区域第一个未排序的元素
	int l_pos = left;
	//标记右区域第一个未排序的元素
	int r_pos = mid + 1;
	//辅助数组元素下标,只需从最左面开始即可
	int pos = left;
	//合并
	while (l_pos <= mid && r_pos <= right) {
		if (arr[l_pos] < arr[r_pos])
			tempArr[pos++] = arr[l_pos++];
		else
			tempArr[pos++] = arr[r_pos++];
	}

	//合并左区域剩余元素
	while (l_pos <= mid) {
		tempArr[pos++] = arr[l_pos++];
	}
	//合并右区域剩余元素
	while (r_pos <= right) {
		tempArr[pos++] = arr[r_pos++];
	}
	//将辅助数组中合并后的元素覆盖给原数组中
	/*while (left <= right) {
		arr[left] = tempArr[left];
		left++;
	}*/
	for (int i = 0; i <= right; i++) {
		arr[i] = tempArr[i];
	}
}

这就是归并排序算法的具体实现过程