【数据结构初阶系列】归并排序全透视：从算法原理全分析到源码实战应用

//归并排序
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	//[0,n-1]
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

//“分治法”实现
void _MergeSort(int* arr, int left, int right, int* temp)
{
	//当二分到个体时直接返回
	if (left >= right)
	{
		return;
	}

	//中间值,分为两个子序列
	int mid = (left + right) / 2;

	//递归分解
	_MergeSort(arr, left, mid, temp);//左
	_MergeSort(arr, mid + 1, right, temp);//右

	//开始分别排序、合并
	//防止边界变化，新定义子序列边界
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	int index = left;//下标

	//循环遍历比较--从个体开始
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			temp[index++] = arr[begin1++];
		}
		else
		{
			temp[index++] = arr[begin2++];

		}
	}

	//将子序列剩余的数组循环放入
	//序列1剩余
	while(begin1 <= end1)
	{
		temp[index++] = arr[begin1++];
	}

	//序列2剩余
	while (begin2 <= end2)
	{
		temp[index++] = arr[begin2++];
	}

	//拷贝到原数组
	for (int i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

//归并排序
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	//[0,n-1]
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

test01()
{
	//int arr[] = {6, 2, 7, 3};
	int arr[] = { 5,3,9,6,2,4, 7, 1, 8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("排序之前：");
	PrintArr(arr, n);
	QuickSort(arr, 0, n - 1); 
	//归并排序-递归
	MergeSort(arr, n);
	printf("排序之后：");
	PrintArr(arr, n);

}
int main()
{
	test01();
	return 0;
}

//非递归版--归并排序
void MergeSortNore(int* arr, int n)
{
	//开辟临时数组
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	//从个体开始
	int gap = 1;//代表一组就一个数据

	//根据gap开始分组
	while (gap < n)
	{
		//分组，两两比较合并
		for (int i = 0;i < n; i += 2*gap)//注意条件的设置
		{
			//子序列1
			int begin1 = i, end1 = i + gap - 1;
			//子序列2
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			//特殊情况--没配对
			if (begin2 >= n)//序列2没有
			{
				break;
			}
			if (end2 >= n)//单个
			{
				end2 = n - 1;
			}

			//两个序列进行比较合并
			int index = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[index++] = arr[begin1++];
				}
				else
				{
					temp[index++] = arr[begin2++];
				}
			}

			//将某序列剩余元素合并
			while (begin1 <= end1)
			{
				temp[index++] = arr[begin1++];
			}

			while (begin2 <= end2)
			{
				temp[index++] = arr[begin2++];
			}
			
			//导入到原数组
			memcpy(arr + i, temp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;//向上合并
	}
	free(temp);
}

//打印
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

test01()
{
	//int arr[] = {6, 2, 7, 3};
	int arr[] = { 5,3,9,6,2,4, 7, 1, 8 };
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("排序之前：");
	PrintArr(arr, n);
	//非递归--归并
	MergeSortNore(arr, n);
	printf("排序之后：");
	PrintArr(arr, n);
}
int main()
{
	test01();
	return 0;
}

🍓 我是晨非辰Tong！若这篇技术干货帮你打通了学习中的卡点：
👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长
❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量
⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用
💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑
🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解
技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！