【算法学习】分治法应用—归并排序

归并排序是分治思想的运用。

文章目录

- 🤯基本思想：分治之美
- 💻核心算法
- - ✂️分治流程：
  - 📽️过程演示
- ⌛分步实现
- ⌨️完整代码
- 🚀 性能分析
- ❓常见问题
- 💡优化建议

🤯基本思想：分治之美

将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

归并排序（Merge Sort）是分治思想的经典应用。其核心理念是：

分解：将复杂的大问题分割成简单的小问题
解决：逐步解决小问题
合并：将解决后的小问题结果组合成最终解

💡 核心口诀：分、治、合！

💻核心算法

✂️分治流程：

分割阶段：将待排序数组递归地分成两个大小近似的子数组
排序阶段：分别对这两个子数组进行排序
合并阶段：将已排序的子数组合并成一个有序数组

// 归并排序
void MergeSort(Type a[], int left, int right){if (left<right) //至少有2个元素{ int i=(left+right)/2;  // 取中点mergeSort(a, left, i); // 处理左半边mergeSort(a, i+1, right); // 处理右半边merge(a, b, left, i, right);  // 合并到数组bcopy(a, b, left, right);      // 复制回数组a}}

📽️过程演示

⌛分步实现

确定分界点

// 确定分界点int mid = (l + r) >> 1; // 求中点坐标

归并排序每次都是分成大致相同的两部分，所以分界点是 $\dfrac {1}{2}$ 处。

💡 小技巧：使用右移运算符>>代替除法，计算更高效

递归处理子问题

  // 递归处理子问题mergeSort(a, l, mid); // 处理半左区间mergeSort(a, mid + 1, r); // 处理半右区间

分治法都是通过递归处理子问题。

💡 递归精髓：将大问题不断拆分，直到问题足够小（通常是1-2个元素）

合并子问题

 // 合并子问题int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r) // 直到有一半区间遍历完{if (a[i] <= a[j])temp[k++] = a[i++];elsetemp[k++] = a[j++];}// 扫尾：将剩余的元素加到中间数组后while (i <= mid)temp[k++] = a[i++];while (j <= r)temp[k++] = a[j++];

💡 合并技巧：总是选择两个子数组中最小的元素

经过步骤2对左右区间进行递归处理后，左右两个子区间都是有序的，这里通过两个指针i和j分别遍历左右子区间，比较当前元素大小，把较小的元素依次放入临时数组temp。最后，把左右子区间剩余的元素也都放入temp。
故扫尾时直接将剩余的元素加到中间数组后

  // 将合并后的数组赋值给原数组for (int i = l, j = 0; i <= r; ++i, ++j)a[i] = temp[j];
}

注意：这里复制的赋值是从递归的起始位置l开始的，因为每次排序只是针对l到r这个范围的区间进行的

⌨️完整代码

#include <iostream>using namespace std;const int N = 100005; // 最大n的范围
int n;
int a[N], temp[N]; // 待排序数组和中间数组void mergeSort(int a[], int l, int r)
{// 递归结束条件：到达原子问题if (l >= r)return;// 确定分界点int mid = (l + r) >> 1;// 递归处理子问题mergeSort(a, l, mid);mergeSort(a, mid + 1, r);// 合并子问题int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r){if (a[i] <= a[j])temp[k++] = a[i++];elsetemp[k++] = a[j++];}// 扫尾while (i <= mid)temp[k++] = a[i++];while (j <= r)temp[k++] = a[j++];// 将合并后的数组赋值给原数组: 注意这里的赋值是从递归的起始位置l开始的，因为每次排序只是针对l到r这个范围的区间进行的for (int i = l, j = 0; i <= r; ++i, ++j)a[i] = temp[j];
}int main()
{cin >> n;for (int i = 0; i < n; ++i)cin >> a[i];mergeSort(a, 0, n - 1); // 归并排序：从0开始，到n-1结束for (int i = 0; i < n; ++i){cout << a[i] << ' ';}return 0;
}