❤️C语言归并排序算法 (超精炼写法)❤️

本篇介绍一种不同于插入排序和选择排序的排序方法——归并排序，其排序的实现思想是先将所有的记录完全分开，然后两两合并，在合并的过程中将其排好序，最终能够得到一个完整的有序表。

例如对于含有 n 个记录的无序表，首先默认表中每个记录各为一个有序表（只不过表的长度都为 1），然后进行两两合并，使 n 个有序表变为 ⌈n/2⌉ 个长度为 2 或者 1 的有序表（例如 4 个小有序表合并为 2 个大的有序表），通过不断地进行两两合并，直到得到一个长度为 n 的有序表为止。这种归并排序方法称为：2-路归并排序。

例如对无序表{49，38，65，97，76，13，27}进行 2-路归并排序的过程如图 1 所示：

#define _CRT_SECURE_NO_WARNINGS 1

#include 
#include 
#include 

void  merge(int arr[], int L, int M, int R) {//归并左右两侧数组
	int* a = (int*)malloc((R - L + 1) * sizeof(int));//新建一个空数组
	int i = 0;
	int p1 = L;
	int p2 = M + 1;
	while (p1 <= M && p2 <= R) {//左右依次比较将小数放入新数组中
		a[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= M) {//如果左侧没全部放入则依次全部放入
		a[i++] = arr[p1++];
	}
	while (p2 <= R) {//如果右侧侧没全部放入则依次全部放入
		a[i++] = arr[p2++];
	}
	for (i = 0; i < R - L + 1; i++) {//将排序好后的数组复制到原数组
		arr[L + i] = a[i];
	}
}

 void process(int arr[],int L,int R) {//递归排序
	 if (L == R) {
		 return;
	 }
	 int mid = L + ((R - L) >> 1);//取出中间位置
	 process(arr, L, mid);//左侧排序
	 process(arr, mid+1, R);//右侧排序
	 merge(arr, L, mid, R);//调用归并排序
 }

 void mergeSort(int arr[], int length) {//程序主入口
	 if (length < 2) {
		 return;
	 }
	 process(arr, 0, length - 1);//调用递归程序
 }
int main() {
	int arr[] = {49,38,65,97,76,13,27 };
	int length = sizeof(arr) / sizeof(arr[0]);
	printf("排序前：");
	for (int i = 0; i < length; i++) {
		printf("%dt", arr[i]);
	}
	time_t start_t = time(NULL);//开始执行时间
	mergeSort(arr, length);
	time_t end_t = time(NULL);
	int t = time(&end_t) - time(&start_t);
	printf("n执行耗时：%d msn排序后：", t);
	for (int i = 0; i < length; i++) {
		printf("%dt",arr[i]);
	}
	return 0;
}

运行结果为：

提示： ：归并排序算法在具体实现时，首先需要将整个记录表进行折半分解，直到分解为一个记录作为单独的一张表为止，然后在进行两两合并。整个过程为分而后立的过程。

归并排序算法的时间复杂度为O(nlogn)。该算法相比于堆排序和快速排序，其主要的优点是：当记录表中含有值相同的记录时，排序前和排序后在表中的相对位置不会改变。

例如，在记录表中记录 a 在记录 b 的前面（记录 a 和 b 的关键字的值相等），使用归并排序之后记录 a 还在记录 b
的前面。这就体现出了该排序算法的稳定性。而堆排序和快速排序都是不稳定的。

作者：香芋味的猫丶

>>相关阅读
《❤️Leetcode1. 两数之和（C语言/Java）❤️》
《❤️Leetcode 7. 整数反转（C语言）❤️》
《❤️Leetcode 9. 回文数（C语言 ）❤️》
《Java选择排序算法》
《Java冒泡排序算法》