归并排序(Merge Sort)(递归写法)
归并排序（Merge Sort）知识点
1. 基本思想
归并排序是一种分治算法（Divide and Conquer），其核心思想是：
分解（Divide）：将待排序的数组递归地分成两个子数组，直到每个子数组只包含一个元素（此时自然有序）。
合并（Merge）：将两个已排序的子数组合并成一个有序的数组，直到所有子数组合并完成，最终得到完整的有序数组。
2. 算法步骤
递归分解：
计算数组的中间位置
mid，将数组分为左半部分[left, mid]和右半部分[mid+1, right]。递归地对左半部分和右半部分进行归并排序。
合并有序子数组：
使用双指针法，比较左右两个子数组的元素，按顺序合并到一个临时数组中。
将临时数组中的结果复制回原数组的对应位置。
3. 时间复杂度
最优、最差、平均时间复杂度均为
O(n log n)：分解过程是
O(log n)（递归深度）。合并过程是
O(n)（每次合并需要线性时间）。
空间复杂度
O(n)：需要一个临时数组存储合并后的结果。
4. 稳定性
归并排序是稳定的，因为在合并时，如果两个元素相等，可以优先取左子数组的元素，保持它们的相对顺序。
5. 适用场景
适用于大数据量的排序，因为它的时间复杂度稳定在
O(n log n)。适用于链表排序，因为归并排序对数据的随机访问要求较低（相比快速排序）。
代码
//归并排序
//子函数
void _MergeSort(int* num, int* temp, int begin, int end)
{
//不断二分使有序(最小子问题是两个区间，每个区间各一个，然后归并)
if (begin >= end) //也可以==，因为底下的区间分发注定begin不会大于end,只会等于
return;
int mid = (begin + end) / 2; //二分取中间
_MergeSort(num, temp, begin, mid); //必须这样分区间[begin , mid] [mid + 1 , end] 不然就会栈溢出
_MergeSort(num, temp, mid + 1, end);
//归并
//分左区间
int begin1 = begin;
int end1 = mid;
//分右区间
int begin2 = mid + 1;
int end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (num[begin1] < num[begin2])
{
temp[i++] = num[begin1++];
}
else
{
temp[i++] = num[begin2++];
}
}
//处理num余下元素
while (begin1 <= end1)
{
temp[i++] = num[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = num[begin2++];
}
//循环一次就赋一次值， 当然也可以整体赋，但是会很麻烦，这样写不麻烦，推荐这样写
memcpy(num + begin, temp + begin, (end - begin + 1) * sizeof(int));
}
//根函数
void MergeSort(int* num, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);
if (temp == NULL)
{
perror("malloc");
exit(1);
}
_MergeSort(num, temp, 0, n - 1);
free(temp);
temp = NULL;
}