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

小蚂蚁

❤️(​​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 <stdio.h>#include <string.h>#include <time.h>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("%d\t", 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 ms\n排序后：", t);  for (int i = 0; i < length; i++) {  printf("%d\t",arr[i]);  }  return 0;}

运行结果为：

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

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

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

作者：香芋味的猫丶