分治策略下的归并排序：数据结构中的经典排序方法
归并排序：分治思想的精彩展现
基本思想
归并排序（Merge Sort）是分治法（Divide and Conquer）的典型应用，由计算机科学领域的先驱约翰·冯·诺依曼在1945年提出。它的核心思路是：把一个大的问题拆分成多个小问题，解决完小问题后再将结果合并起来。
算法的流程包含两个关键阶段：
- 分解（Divide） ：通过递归的方式将当前的数组分割成两个子数组，直到每个子数组里仅仅包含一个元素（此时子数组天然就是有序的）
- 治理（Conquer） ：把两个已经有序的子数组合并成一个全新的有序数组
归并排序的核心操作是合并两个有序数组：每次比较两个数组的首元素，把较小的那个元素放到新数组中，直到所有元素都合并完成。
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
void _MergeSort(int* a, int* tmp, int begin, int end)
{
// 递归终止条件：当子数组只有一个元素时
if (begin == end)
{
return;
}
// 计算中间点
int mid = (begin+end)/2;
//如果[begin,mid]和[mid+1,end]有序就可以进行归并了 这里区间不能分为[begin,mid-1][mid,end] 这是个坑 比如2 3 6 7
_MergeSort(a,tmp, begin,mid);//把一组分成左右两个区间
_MergeSort(a, tmp, mid+1, end);
//归并
int begin1 = begin, end1 = mid ;
int begin2 = mid+1, 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, (end - begin + 1) * sizeof(int));//begin和end在变化不是一直从0开始 看动图
}
// 归并排序入口函数
void MergeSort(int* a, int n)
{
// 分配临时数组空间
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc fail");
return;
}
// 调用递归函数
_MergeSort(a, tmp, 0, n - 1);
// 释放临时数组
free(tmp);
tmp = NULL;
}
//测试案例
int main()
{
int a[] = { 2,3,5,4,7,1 };
MergeSort(a, 6);
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
printf("%d", a[i]);
}
return 0;
}
为何区间不能用[end,mid-1]与[mid,end]
解释为什么不能把区间划分成[begin,mid-1]和[mid,end]。例如有10个数据，下标从0到9，若按[begin,mid-1]和[mid,end]划分，假设mid-1=3，就会分成[0,3]和[4,9]两个区间。在[0,3]区间内，mid-1=0，又会分成[0,0]和[1,3]，[0,0]很快结束，而[1,3]的mid-1=1，再分成[1,1]和[2,3]，[2,3]的mid-1=1，又分成[2,1]和[1,3]，这显然是不合理的情况。
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 分解数组 | O(log n) | 递归深度 |
| 合并子数组 | O(n) | 每层需遍历所有元素 |
| 总复杂度 | O(n log n) | 稳定高效排序 |
空间复杂度
归并排序需要 O(n) 的额外空间：
- 用于存储合并过程中的临时数组
- 递归调用栈空间为 O(log n)，通常临时数组占主导地位
非递归归并
可理解为11归并是两组数据中每个子数组元素个数均为1，11归并完成后进行22归并，依此类推。
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//gap为每组归并数据的元素个数
int gap = 1;
for (int i = 0; i < n; i+=2*gap)//一整组归并含gap+gap个元素，i为每组归并起始位置
{
int begin1 = i, end1 = i+gap-1;
int begin2 = gap + i, end2 = i+2*gap-1;//begin2为begin1跳过一组数据后的起始位置，end2跳过两组数据
//第二组越界则跳过本次合并
if (begin2 >= n)
{
break;
}
//第二组未完全越界但部分越界，修正边界继续归并
if (end2 >= n)
{
end2 = n - 1;
}
int j=i;
while (begin1 <= end1 && begin2 <= end2)//一数组处理完则将另一数组剩余元素放新数组后
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];//放较小元素到临时数组
}
else
{
tmp[j++] = a[begin2++];
}
}
//处理剩余元素
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));//归并结果拷贝回原数组
}
free(tmp);
tmp = NULL;
}
10个数可能出现溢出情况，通过打印归并区间分析，主要有第二个子数组完全越界和部分越界两种情况。时间复杂度上，每层遍历n个元素，共logn层，故为n log n。空间复杂度为O(n)，因需额外临时空间。
非递归实现要点
- gap参数：控制当前归并子数组大小，从1开始，迭代时翻倍
- 边界处理：关键步骤，处理数组大小非2的幂情况：
- 第二组完全越界（begin2 ≥ n），跳过合并
- 第二组部分越界（end2 ≥ n），修正边界为n-1
- 迭代过程：
- 第一轮：11归并，子数组大小为1
- 第二轮：22归并，子数组大小为2
- 第k轮：2ᵏ归并，子数组大小为2ᵏ
归并排序特性总结
- 稳定排序：
- 元素相等时优先选左子数组元素，保持相等元素原始相对位置，适用于多关键字排序
- 时间复杂度：
- 最优、平均、最差均为O(n log n)，性能稳定
- 空间复杂度：
- 需O(n)额外空间，递归实现有O(log n)栈空间
- 外排序优势：
- 能高效处理外部存储数据，适合海量数据，流程为：分割大文件为内存块→内存排序→合并已排序块
结语
归并排序是分治思想的卓越体现，通过“分而治之”策略实现O(n log n)高效排序。其核心优势：
1. 稳定可靠：不受输入数据影响，性能稳定
2. 外排序能力：是处理海量磁盘数据的通用高效算法
3. 稳定排序：保持相等元素原始顺序
4. 并行潜力：天然适合并行化
虽需O(n)额外空间，但在现代系统中空间换时间策略可行。归并排序在数据库、大数据、外部排序等场景不可或缺，是程序员必掌握的经典算法。
相关文章
