C语言手撕归并——递归与非递归实现（附动画及源码）

🤖💻👨‍💻👩‍💻🌟🚀

🤖🌟 欢迎降临张有志的未来科技实验室🤖🌟

专栏：数据结构 

👨‍💻👩‍💻 先赞后看，已成习惯👨‍💻👩‍💻

👨‍💻👩‍💻 创作不易，多多支持👨‍💻👩‍💻

🚀 启动创新引擎，揭秘C语言的密码🚀

🧠目录

归并排序概述

核心步骤

动画演示

归并排序的性能

递归代码实现

函数签名

逻辑流程

函数签名

逻辑流程

        非递归代码实现

msort函数解析

归并排序概述

归并排序的基本思想是将待排序的序列分成若干个子序列，每个子序列都是有序的。然后再合并这些子序列形成最终的排序序列。这个过程可以递归地进行，直到所有的子序列都只包含一个元素为止。

核心步骤

1. 分解：将序列分为两半。

2. 解决：递归地对每一半进行排序。

3. 合并：将两个已排序的子序列合并成一个单一的有序的序列

动画演示

归并排序的性能

• 最佳情况: 𝑂(𝑛log⁡𝑛)O(nlogn)
• 平均情况: 𝑂(𝑛log⁡𝑛)O(nlogn)
• 最差情况: 𝑂(𝑛log⁡𝑛)O(nlogn)
• 空间复杂度: 𝑂(𝑛)O(n)
• 稳定性: 归并排序是稳定的排序算法，即相等的元素在排序前后保持原有的相对顺序。

递归代码实现

函数签名

• void merge(int arr[], int tempArr[], int left, int right, int mid)

int arr[]: 待排序的数组。

int tempArr[]: 一个临时数组，用于存储合并过程中产生的有序子数组。

int left: 左侧子数组的起始索引。

int right: 右侧子数组的结束索引。

int mid: 中间索引，用于分割数组。

逻辑流程

• 初始化指针

int l_pos = left;

• 初始化左侧子数组的指针 l_pos

int r_pos = mid + 1;

• 初始化右侧子数组的指针 r_pos

int pos = left;

• 初始化临时数组 tempArr 的指针 pos

• 合并左右子数组

while (l_pos <= mid && r_pos <= right)

在 l_pos 和 r_pos 都没有超过各自子数组边界的情况下，比较左侧和右侧的元素。

如果左侧元素小于右侧元素，则将左侧元素放入 tempArr 中，并移动左侧指针；

否则，将右侧元素放入 tempArr 中，并移动右侧指针。

• 处理左侧剩余元素

while (l_pos <= mid)

如果左侧子数组还有未处理的元素，则将这些元素依次放入 tempArr 中。

• 处理右侧剩余元素

while (r_pos <= right)

如果右侧子数组还有未处理的元素，则将这些元素依次放入 tempArr 中。

• 复制结果回原数组

for (int i = left; i <= right; i++)

将 tempArr 中的有序结果复制回原数组 arr 中对应的位置。

void merge(int arr[], int tempArr[], int left, int right, int mid)
{
	int l_pos = left;
	int r_pos = mid+1;
	int pos = left;

	while (l_pos <= mid && r_pos <= right){
		if (arr[l_pos] < arr[r_pos])
			tempArr[pos++] = arr[l_pos++];
		else
			tempArr[pos++] = arr[r_pos++];
	}

	while (l_pos <= mid) {
		tempArr[pos++] = arr[l_pos++];
	}

	while (r_pos <= right)
	{
		tempArr[pos++] = arr[r_pos++];
	}

	for (int i = left; i <= right; i++)
	{
		arr[i] = tempArr[i];
	}
}

函数签名

void msort(int arr[], int tempArr[], int left, int right)

• int right: 数组的结束索引。
• int left: 数组的起始索引。
• int tempArr[]: 一个临时数组，用于存储中间结果，以便在合并阶段使用。
• int arr[]: 待排序的数组。

逻辑流程

• 递归终止条件

   if (right > left) 

• 分割数组

 int mid = (left + right) / 2;

计算中间位置 mid，用来分割数组。这里使用 (left + right) / 2 来找到中间点。

• 递归调用

msort(arr, tempArr, left, mid);

• 对左边的子数组进行递归排序。

msort(arr, tempArr, mid + 1, right);

• 对右边的子数组进行递归排序。

• 合并排序后的子数组

merge(arr, tempArr, left, right, mid);

• 调用 merge 函数来合并已经排序好的左右两个子数组。这个函数将两个已排序的子数组 arr[left...mid] 和 arr[mid+1...right] 合并成一个有序的数组。

void msort(int arr[], int tempArr[], int left, int right)
{
	if (right > left)
	{
		int mid = (left + right) / 2;
		msort(arr, tempArr, left, mid);
		msort(arr, tempArr, mid + 1, right);
		merge(arr, tempArr, left, right, mid);
	}
}

非递归代码实现

merge函数与上述类似，这里不再赘述

msort函数解析

• 初始化步长

  • int gap = 1;
    • 初始化步长 gap，表示每次分割的子数组长度。

• 外层循环

  • while (gap < right)
    • 在步长大于整个数组长度之前，继续进行循环。

• 内层循环

  • for (int begin = 0; begin < right - gap; begin += 2 * gap)
    • 从数组的起始位置开始，每次增加 2 * gap，来遍历整个数组。
    • 这样做是为了确保每次合并的子数组不会重叠。

• 确定子数组边界

  • int mid = begin + gap - 1;
    • 确定左侧子数组的结束位置 mid。
  • int end = (begin + 2 * gap - 1) < right ? begin + 2 * gap - 1 : right;
    • 确定右侧子数组的结束位置 end。如果 begin + 2 * gap - 1 小于 right，则取 begin + 2 * gap - 1；否则取 right。

• 调用 merge 函数

  • merge(arr, tempArr, begin, mid, end);
    • 调用 merge 函数来合并已排序的子数组。

• 更新步长

  • gap *= 2;
    • 每次循环结束后，将步长翻倍，这样可以逐渐增加合并的子数组的大小。

  void msort(int* arr, int* tempArr, int left, int right)
  {
  	int gap = 1;
  	while (gap < right)
  	{
  		for (int begin = 0; begin < right - gap; begin += 2 * gap)
  		{
  			int mid = begin + gap - 1;
  			int end = (begin + 2 * gap - 1) < right ? begin + 2 * gap - 1 : right;
  			merge(arr, tempArr, begin, mid, end);
  		}
  		gap *= 2;
  	}
  }