【数据结构】八大排序之归并排序：分治思想的完美演绎

归并排序：分治思想的完美演绎

基本思想

归并排序（Merge Sort）是**分治法（Divide and Conquer）**的经典应用，由计算机科学先驱约翰·冯·诺依曼于1945年提出。其核心思想是：将大问题分解为小问题，解决小问题后合并结果。

算法流程分为两个核心阶段：

1. 分（Divide）：递归地将当前数组分割成两个子数组，直到每个子数组只包含一个元素（天然有序）
2. 治（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]

假设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(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 + 1, end2 = i+2*gap-1;//begin2是begin1跳过一组数据，也就是跳过gap个 所以是gap+i;end2要跳过两组.
          //第二组越界不存在.这一组就不需要归并了
        if (begin2 >= n)
        {
            break;
        }
        //第二组的begin2没越界,end2越界了，需要修正一下，继续 归并
        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个数就会出现溢出

把归并区间打印出来分析一下 就上图者三种情况

但也可以分为两种 第一种是begin2溢出 第二种是begin2不溢出,end2溢出

时间复杂度

不能看循环层数

每一层都是n 一共logn层

所以时间复杂度是nlongn

空间复杂度是O(n) 因为要再开一块空间

非递归实现要点

1. gap参数：控制当前归并的子数组大小，从1开始，每次迭代翻倍
2. 边界处理：关键步骤，处理数组大小不是2的幂的情况：
   • 当第二个子数组完全越界（begin2 ≥ n），跳过本次合并
   • 当第二个子数组部分越界（end2 ≥ n），修正其边界为n-1
3. 迭代过程：
   • 第1轮：11归并 → 每个子数组大小为1
   • 第2轮：22归并 → 子数组大小为2
   • 第k轮：2ᵏ归并 → 子数组大小为2ᵏ

归并排序特性总结

1. 稳定排序：

   • 当两个元素相等时，归并排序优先选择左子数组的元素
   • 保持相等元素的原始相对位置不变
   • 适用于需要稳定性的场景（如多关键字排序）

2. 时间复杂度：

   • 最优：O(n log n)
   • 平均：O(n log n)
   • 最差：O(n log n)
   • 不受输入数据影响，性能稳定

3. 空间复杂度：

   • O(n) 额外空间
   • 递归实现还有 O(log n) 的栈空间

4. 外排序优势：

   • 归并排序是少数能高效处理外部存储（如硬盘）数据的排序算法

   • 特别适合处理超过内存容量的海量数据

   • 工作流程：

     1. 将大文件分割为能放入内存的小块

     2. 在内存中排序每个小块

     3. 合并已排序的小块

结语

归并排序是分治思想的完美体现，通过"分而治之"的策略达到O(n log n)的高效排序。其核心优势在于：

1. 稳定可靠：不受输入数据影响，始终保证O(n log n)性能
2. 外排序能力：唯一能高效处理海量磁盘数据的通用排序算法
3. 稳定排序：保持相等元素的原始顺序
4. 并行潜力：天然适合并行化实现

尽管需要O(n)额外空间，但在现代计算机系统中，空间换时间的策略往往是值得的。归并排序在数据库系统、大数据处理、外部排序等场景中发挥着不可替代的作用，是每个程序员必须掌握的经典算法之一。