【数据结构】归并排序详解

1.基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。（有点像二叉树递归，大家可以联想二叉树理解）

在这里插入图片描述
下面是动图展示：

2.代码展示及讲解

讲解部分在注释中，配合上述两张图食用更佳

#include <stdio.h>void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end){return;}//递归返回的判断条件int mid = (begin + end) / 2;//作为数组递归的左边（类似于左子树）和右边（右子树）_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);//对数组递归，利用mid将数组分成左右两个数组，并分别不断递归，并将递归排列好的元素储存到辅助数组tmp中，然后用内存函数将tmp中的元素复制到原数组中int left1 = begin;int right1 = mid;int left2 = mid + 1;int right2 = end;//递归的左右边界int t = begin;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){tmp[t++] = a[left1++];}else{tmp[t++] = a[left2++];}}while (left1 <= right1){tmp[t++] = a[left1++];}while (left2 <= right2){tmp[t++] = a[left2++];}// 在递归的过程中对左右两边进行排序，如果上述排序方法一下子看不懂的话，//可以在纸上模拟一下，绝对简单，就是将两个数组中的元素按照从小到大依次放到辅助数组tmp中memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));//转移排好的元素
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);**//创建一个新数组作为辅助数组，储存递归的元素，并将其进行排序，//然后使用内存函数将辅助数组中的排列好的元素转移到原数组中**if (tmp == NULL){perror("malloc fail");return;}//判断空间是否开辟成功_MergeSort(a, 0, n - 1, tmp);//借助子函数开始递归
}int main()
{int a[10] = { 1,3,5,7,9,2,4,6,8,10 };MergeSort(a, 10);for (int i = 0; i < 10; i++){printf("%d ", a[i]);}return 0;
}