目录
一、什么是归并排序
二、递归实现
2.1 思路
2.2 C语言源码
三、非递归实现
3.1 思路
3.2 C语言源码
一、什么是归并排序
归并排序是一种基于分治思想的排序算法。它的基本思想是将原始的待排序序列不断地分割成更小的子序列，直到每个子序列中只有一个元素，然后逐步将这些子序列合并为一个有序的序列。
具体来说，归并排序的操作流程如下：
- 分割阶段：将待排序序列不断地二分为更小的子序列，直到每个子序列只包含一个元素。
- 合并阶段：将相邻的子序列两两合并，合并过程中按照大小顺序排列元素，直到所有的子序列合并为一个有序序列。
归并排序由于是自上而下的递归排序，每次合并操作都需要额外的空间来存储临时的序列，因此归并排序的空间复杂度较高。但由于合并操作是稳定的，因此归并排序是一种稳定的排序算法。
归并排序的时间复杂度为 O(nlogn)，其中 n 为待排序序列的长度，因此归并排序在时间上具有较高的效率。由于其稳定性和高效性，归并排序通常被用于需要稳定性的排序场景，或者对于大数据量的排序。
可以看出，归并排序类似于快速排序的思想，都是基于分治法的二叉树思路实现。但是二者存在区别：
- 快速排序是一种类似前序的思路-先排序大区间再排序小区间
- 归并排序是一种类似后序的思路-先排子区间再排大区间最后合并
这样的区别会体现在代码实现中递归代码的位置上。
二、递归实现
2.1 思路
核心思路：将每个小区间数组在新数组上排序，然后复制回原数组上。重复递归，由小区间到大区间，直至排序完成
- 考虑单次
- 比较逻辑：两个区间分别初始化两个指针指向起始位置，逐个元素遍历比较，按照大小顺序放入新数组中。
- 收尾逻辑：区间内或许存在顺序已经排好的序列，比较逻辑结束后将他们放入新数组中
- 最后将新数组拷贝到原数组中，一个区间排序完成
- 考虑递归
- 每次计算区间的中点进行二分法
- 传入[起始位置，中点] 以及 [中点的下一个位置，结束位置] 进行重复递归
- 递归结束的条件是，子区间仅有一个元素（意味着不需要排列）
注意事项：
实际写代码的过程中，每次开辟空间的做法大大降低了程序执行的效率。更好的处理方法是：开辟于要排序数组等大的空间，每次小区间复制只需传入区间的起始位置，区间的大小就可以避免空间的重复开辟。
2.2 C语言源码
//递归版本
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);
//归并
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
//收尾
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//复制到指定位置
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");
exit(1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
三、非递归实现
3.1 思路
与快速排序的非递归实现思路类似，本质上仍然是要控制每次传入的区间。但是前文有讲二者的细微差别，所以实现方式不尽相同。本文采用二路循环方式的方式实现。
采用自底向上的思路讲解
比较的主题逻辑依然是采用上述递归思路的逻辑，所以仍然需要两个指针指向两个组，gap变量表示每组处理的数据。
- 考虑一次处理：
gap=1，两路，处理的是两个数据。排序后将中间数组复制到原数组的指定位置 - 考虑一层处理：因为二路处理一次只能有限个数据，需要再来一次循环处理掉该层的所有数据。结束条件很明显要小于数组的大小，每次循环起始位置都是原位置+2*gap
- 考虑循环处理：一层结束后，下一层gap要变成原来的2倍。很明显循环结束条件是gap小于数组大小。
注意事项：
上述图解的元素个数恰好是偶数，若出现奇数个的情况，在求区间时一定会发生数组越界的情况。需要找到特殊情况然后进行修正
- 由于begin1指针由数组大小循环来控制，所以不可能造成越界。
- 考虑end1越界：那么后续的两个指针同样越界，此时区间内只有一个元素无需排序，跳出循环即可
- 考虑begin2越界：此时区间内有两个元素，在上一层排序中二者已经为有序，所以跳出循环即可。
- 考虑end2越界：此时第二个组中仅有一个元素，依然需要比较排序。所以需要将end2的下标进行修正。
3.2 C语言源码
//非递归版本
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc");
exit(1);
}
int gap = 1; // 每组归并的数据个数
while (gap < n)
{
for (int j = 0; j < n; j += 2 * gap)
{
int begin1 = j, end1 = begin1 + gap - 1;
int begin2 = end1 + 1, end2 = begin2 + gap - 1;
//特殊情况控制
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
//开始排序
int i = j;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
//收尾
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//每组结束复制
memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));
}
//循环
gap *= 2;
}
}
