❤️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>voidmerge(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 = arr <= arr ? arr : arr;}while (p1 <= M) {//如果左侧没全部放入则依次全部放入 a = arr;}while (p2 <= R) {//如果右侧侧没全部放入则依次全部放入 a = arr;}for (i = 0; i < R - L + 1; i++) {//将排序好后的数组复制到原数组 arr = a;}} 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);printf("排序前：");for (int i = 0; i < length; i++) { printf("%d\t", arr);}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);}return 0;}运行结果为：
提示： ：归并排序算法在具体实现时，首先需要将整个记录表进行折半分解，直到分解为一个记录作为单独的一张表为止，然后在进行两两合并。整个过程为分而后立的过程。
总结
归并排序算法的时间复杂度为O(nlogn)。该算法相比于堆排序和快速排序，其主要的优点是：当记录表中含有值相同的记录时，排序前和排序后在表中的相对位置不会改变。
例如，在记录表中记录 a 在记录 b 的前面（记录 a 和 b 的关键字的值相等），使用归并排序之后记录 a 还在记录 b
的前面。这就体现出了该排序算法的稳定性。而堆排序和快速排序都是不稳定的。
作者：香芋味的猫丶
https://blog.51cto.com/u_14284202/4773084
页:
[1]