算法笔记之归并排序
本系列可作为算法学习系列的笔记，小编会将代码记录下来，大家复制下来就可以练习了，方便大家学习。小编作为新晋码农一枚，会定期整理一些写的比较好的代码，作为自己的学习笔记，会试着做一下批注和补充，如转载或者参考他人文献会标明出处，非商用，如有侵权会删改！欢迎大家斧正和讨论！
系列文章目录
计算矩阵的鞍点个数
算法-比较排序
为什么比较排序算法的时间复杂度下界是 Ω(n log n)？
算法笔记之堆排序
算法笔记之归并排序
目录
系列文章目录
1. 算法步骤
2. 示例
3. 伪代码
4. 时间复杂度
5. 稳定性
（1）稳定排序（Stable Sorting）
①. 为什么稳定性重要？
②. 稳定排序的判定示例
③. 常见稳定排序算法
④. 不稳定排序算法举例
⑤. 如何验证稳定性？
⑥. 实际应用场景
6. 优缺点
7. 应用场景
归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的高效排序算法，其核心思想是将数组递归地分成两半，分别排序后再合并。以下是其详细步骤和特性分析：
1. 算法步骤
-
分解（Divide）
- 将当前数组从中间分成两个子数组，直到每个子数组只剩一个元素（此时自然有序）。
-
解决（Conquer）
- 递归地对左右子数组进行归并排序。
-
合并（Merge）
- 将两个已排序的子数组合并为一个有序数组：
- 创建一个临时数组，依次比较两个子数组的首元素，将较小者放入临时数组。
- 将剩余未合并的元素直接追加到临时数组末尾。
- 将临时数组拷贝回原数组的对应位置。
- 将两个已排序的子数组合并为一个有序数组：
2. 示例
原始数组：[38, 27, 43, 3, 9, 82, 10]
分解过程：
[38, 27, 43, 3] 和 [9, 82, 10]
→ [38, 27], [43, 3], [9, 82], [10]
→ [38], [27], [43], [3], [9], [82], [10]（单元素数组已有序）合并过程：
- 合并
[38]和[27]→[27, 38] - 合并
[43]和[3]→[3, 43] - 合并
[27, 38]和[3, 43]→[3, 27, 38, 43] - 同理，右侧合并为
[9, 10, 82] - 最终合并为
[3, 9, 10, 27, 38, 43, 82]
3. 伪代码
def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left = arr[:mid]right = arr[mid:]merge_sort(left) # 递归排序左半部分merge_sort(right) # 递归排序右半部分# 合并i = j = k = 0while i < len(left) and j < len(right):if left[i] < right[j]:arr[k] = left[i]i += 1else:arr[k] = right[j]j += 1k += 1# 处理剩余元素while i < len(left):arr[k] = left[i]i += 1k += 1while j < len(right):arr[k] = right[j]j += 1k += 14. 时间复杂度
-
最优/最差/平均：均为 O(n log n)
- 分解：每次将数组分成两半，共 log n 层递归。
- 合并：每层需 O(n) 时间遍历所有元素。
-
空间复杂度：O(n)
- 需要额外临时数组存储合并结果（递归栈空间为 O(log n)）。
5. 稳定性
归并排序是稳定排序，因为合并时遇到相等元素会优先保留左子数组的元素（通过 left[i] < right[j] 的条件保证）。
补充：
（1）稳定排序（Stable Sorting）
稳定排序是指排序算法在排序前后，相等元素的相对顺序保持不变。换句话说，如果两个元素的值相同，排序后它们的先后顺序与排序前的原始顺序一致。
①. 为什么稳定性重要？
- 多条件排序：例如，先按年龄排序，再按姓名排序。如果排序算法是稳定的，相同年龄的人会保持姓名的原始顺序。
- 数据完整性：某些场景要求保留原始数据的相对顺序（如日志记录、交易记录等）。
②. 稳定排序的判定示例
原始数组：[ (3, "A"), (2, "B"), (3, "C"), (1, "D") ]（每个元素是一个 (数字, 字母) 对）
按数字排序后：
- 稳定排序结果：
[ (1, "D"), (2, "B"), (3, "A"), (3, "C") ]- 两个
3的顺序保持原始顺序（"A"仍在"C"前面）。
- 两个
- 不稳定排序结果：
[ (1, "D"), (2, "B"), (3, "C"), (3, "A") ]- 两个
3的顺序被颠倒（"C"跑到了"A"前面）。
- 两个
③. 常见稳定排序算法
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 归并排序 | O(n log n) | O(n) | ✔️ 稳定 |
| 冒泡排序 | O(n²) | O(1) | ✔️ 稳定 |
| 插入排序 | O(n²) | O(1) | ✔️ 稳定 |
| 计数排序 | O(n + k) | O(n + k) | ✔️ 稳定 |
| 基数排序 | O(d(n + k)) | O(n + k) | ✔️ 稳定 |
④. 不稳定排序算法举例
- 快速排序（Quick Sort）：分区过程中可能交换相等元素。
- 堆排序（Heap Sort）：堆的调整会破坏相等元素的顺序。
- 选择排序（Selection Sort）：交换非相邻元素可能导致顺序颠倒。
⑤. 如何验证稳定性？
- 构造一个包含重复键值的数据集（如
[ (2, "X"), (1, "Y"), (2, "Z") ]）。 - 排序后检查相同键值的元素是否保持原始顺序（
"X"是否仍在"Z"前面）。
⑥. 实际应用场景
- 数据库排序：
ORDER BY多列时需保持稳定性。 - 图形渲染：按深度排序后，相同深度的物体需保持绘制顺序。
- 版本控制：按时间戳排序时，相同时间的提交需保留原始提交顺序。
6. 优缺点
- 优点：
- 时间复杂度稳定为 O(n log n)，适合大规模数据。
- 适用于链表排序（无需随机访问）。
- 缺点：
- 需要额外空间，不适合内存受限的场景。
- 对小规模数据可能不如插入排序高效（可结合其他算法优化）。
7. 应用场景
- 需要稳定排序的场景（如数据库排序）。
- 外部排序（如大文件处理，因归并排序可分段加载数据）。
归并排序通过分治策略将问题分解为更小的子问题，是理解递归和分治思想的经典案例。