本课时有配套视频讲解，购买后即可观看（永久有效）
归并排序
一、课上练习
编程练习
- 数组排序：L3111
二、知识总结
✨ 核心思想
归并排序用于对一组线性存储的数据进行排序，是一种基于分治法的经典排序算法。
归并排序的核心思想是将一个大数组分解成两个小数组去解决。然后递归地排序这两个小数组，最后将排序好的小数组合并成一个大数组。归并排序的效率来自于它合并两个已排序数组的能力——合并操作只需线性时间即可完成。
✨ 算法原理
归并排序的三个步骤：
- 分解：从中间将待排序的数组分割成两部分，直到每个子数组只包含一个元素（递归基）。单个元素天然有序，无需排序。
- 解决：递归地对这两个子数组进行归并排序，直到每个子部分被排序。
- 合并：将两个排序好的子数组合并成一个最终的排序数组。合并过程需要额外的空间来临时存储这两个数组，然后按顺序选取两个数组中的元素填充到原数组中。
示例
考虑数组 [3, 1, 4, 1, 5, 9, 2, 6] 的排序过程：
分解阶段：
- [3, 1, 4, 1] 和 [5, 9, 2, 6]
- 进一步分解为 [3, 1] 和 [4, 1]，以及 [5, 9] 和 [2, 6]
- 最后分解到单个元素
合并阶段：
- 合并 [3] 和 [1] 得到 [1, 3]
- 合并 [4] 和 [1] 得到 [1, 4]
- 合并 [1, 3] 和 [1, 4] 得到 [1, 1, 3, 4]
- 类似地，[5, 9] 和 [2, 6] 合并为 [2, 5, 6, 9]
- 最后，合并 [1, 1, 3, 4] 和 [2, 5, 6, 9] 得到 [1, 1, 2, 3, 4, 5, 6, 9]
✨ 代码实现
以下是归并排序的完整实现，包含合并函数和递归排序函数：
归并排序代码示例
1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// 合并两个有序数组段的函数
11void merge(int a[], int left, int mid, int right) {
12 int t[105] = {0}; // 创建一个临时数组用于存储合并后的有序序列
13 int lp = left; // lp是左半部分的起始索引
14 int rp = mid + 1; // rp是右半部分的起始索引
15 int si = left; // si是用于追踪当前要插入元素到临时数组t的索引
16
17 // 遍历左右两部分，直到一个达到终点
18 while (si <= right) {
19 // 如果左半部分已完全处理完毕，或者右半部分当前元素小于左半部分当前元素
20 if (lp > mid || (rp <= right && a[lp] > a[rp])) {
21 t[si] = a[rp]; // 将右半部分当前元素拷贝到临时数组
22 rp++; // 移动右半部分的索引
23 }
24 else {
25 t[si] = a[lp]; // 否则，将左半部分当前元素拷贝到临时数组
26 lp++; // 移动左半部分的索引
27 }
28 si++; // 移动临时数组的索引
29 }
30
31 // 将临时数组中排序后的元素拷贝回原数组a
32 for (int i = left; i <= right; i++) {
33 a[i] = t[i];
34 }
35}
36
37// 归并排序的递归实现
38void merge_sort(int a[], int left, int right) {
39 if (right <= left) {
40 return; // 如果当前数组段的长度为1或0，直接返回
41 }
42 int mid = (left + right) / 2; // 找到中点，将数组分成两半
43 merge_sort(a, left, mid); // 递归排序左半部分
44 merge_sort(a, mid + 1, right); // 递归排序右半部分
45 merge(a, left, mid, right); // 合并两个有序的半部分
46}
47
48int main() {
49 int n = 0;
50 cin >> n;
51 for (int i = 0; i < n; i++) {
52 cin >> a[i];
53 }
54 merge_sort(a, 0, n - 1);
55 for (int i = 0; i < n; i++) {
56 cout << a[i] << ' ';
57 }
58 cout << endl;
59 return 0;
60}✨ 执行示例
以数组 [5, 2, 8, 1, 9, 3] 为例，展示完整的归并排序递归分解和合并过程：
第一阶段：递归分解
1merge_sort([5, 2, 8, 1, 9, 3], 0, 5)
2├── merge_sort([5, 2, 8], 0, 2) ← 左半部分
3│ ├── merge_sort([5, 2], 0, 1)
4│ │ ├── merge_sort([5], 0, 0) ← 基案，直接返回
5│ │ └── merge_sort([2], 1, 1) ← 基案，直接返回
6│ │ → merge([5], [2]) = [2, 5] ★ 合并
7│ └── merge_sort([8], 2, 2) ← 基案，直接返回
8│ → merge([2, 5], [8]) = [2, 5, 8] ★ 合并
9└── merge_sort([1, 9, 3], 3, 5) ← 右半部分
10 ├── merge_sort([1, 9], 3, 4)
11 │ ├── merge_sort([1], 3, 3) ← 基案，直接返回
12 │ └── merge_sort([9], 4, 4) ← 基案，直接返回
13 │ → merge([1], [9]) = [1, 9] ★ 合并
14 └── merge_sort([3], 5, 5) ← 基案，直接返回
15 → merge([1, 9], [3]) = [1, 3, 9] ★ 合并
16→ merge([2, 5, 8], [1, 3, 9]) = [1, 2, 3, 5, 8, 9] ★ 最终合并第二阶段：详细展示最后一次合并过程
合并 [2, 5, 8] 和 [1, 3, 9]：
| 步骤 | 比较 | 选取 | 结果数组 | 左指针lp | 右指针rp |
|---|---|---|---|---|---|
| 1 | 2 vs 1 | 取右边的1 | [1] | 0 | 1 |
| 2 | 2 vs 3 | 取左边的2 | [1,2] | 1 | 1 |
| 3 | 5 vs 3 | 取右边的3 | [1,2,3] | 1 | 2 |
| 4 | 5 vs 9 | 取左边的5 | [1,2,3,5] | 2 | 2 |
| 5 | 8 vs 9 | 取左边的8 | [1,2,3,5,8] | 3(越界) | 2 |
| 6 | 左边用完 | 取右边的9 | [1,2,3,5,8,9] | - | 3(越界) |
✨ 算法评价
归并排序的复杂度和特性如下：
- 时间复杂度：O(n log n)。归并排序需要进行大约 log n 次的分解步骤，每次合并操作最多需要 O(n) 时间。无论最好、最坏还是平均情况，时间复杂度都是 O(n log n)，这是归并排序的一大优势。
- 空间复杂度：O(n)。合并过程需要额外的临时数组来存储中间结果。
- 稳定性：稳定排序。相等元素的相对顺序在排序后不会改变，这在某些应用场景中非常重要。
✨ 解题步骤详解
使用归并排序解决问题时：
- 确认场景：归并排序适用于需要稳定排序或需要利用合并过程统计信息的场景（如求逆序对数量）。
- 写分解函数：递归地将数组从中间切分，直到每段只有一个元素。
- 写合并函数：这是归并排序的核心。使用双指针分别指向左右两段的起始位置，每次取较小的元素放入临时数组。
- 注意拷贝回原数组：合并完成后，临时数组中的有序结果需要拷贝回原数组的对应位置。
- 扩展应用：求逆序对时，在合并过程中，当右边元素小于左边元素时，左边剩余的所有元素都与它构成逆序对，可以直接计数。
✨ 常见错误
- 临时数组大小不够：合并时需要临时数组，其大小应至少能容纳当前合并段的所有元素。代码中
t[105]应根据实际数据规模调整。 - 合并时指针越界：在比较
a[lp]和a[rp]之前，必须先检查lp和rp是否已经越界。如果一边已经用完，应该直接取另一边的元素。 - 拷贝回原数组时范围错误：应该从
left拷贝到right，不是从 0 到right-left。 - mid 的计算：建议用
mid = left + (right - left) / 2而非mid = (left + right) / 2，后者在 left 和 right 很大时可能整数溢出。 - 稳定性被破坏：合并时，当左右两边元素相等时，应该优先取左边的元素，这样才能保证稳定性。如果优先取右边，相等元素的顺序会被打乱。
三、课后练习
编程练习
- 单词排序：L3112