归并排序（建议收藏）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

前言

在编程和算法领域，排序算法是数据处理的基础工具之一。无论是处理用户数据、优化搜索结果，还是实现复杂的数据结构，排序算法的性能直接影响系统的整体效率。归并排序（Merge Sort）作为经典的分治算法，凭借其稳定的性能和简洁的实现逻辑，在编程实践中占据重要地位。本文将从零开始，深入剖析归并排序的原理、实现步骤、代码示例以及实际应用场景，帮助读者建立系统化的理解。

一、归并排序的基本概念

1.1 什么是归并排序？

归并排序是一种基于“分治法”思想的排序算法。其核心思想可以比喻为“分而治之”：将一个大问题（如排序一个无序数组）拆解为若干小问题（排序小数组），再通过合并有序的小数组，最终得到完整的有序结果。这一过程类似于将一叠杂乱的卡片分成小叠整理，再逐步合并成完整有序的卡片堆。

1.2 归并排序的特点

• 稳定性：归并排序是稳定的排序算法，即相等元素的相对顺序在排序后保持不变。
• 时间复杂度：无论数据初始状态如何，归并排序的时间复杂度始终为 O(n log n)，这使其在大规模数据排序中表现优异。
• 空间复杂度：需要额外的存储空间（通常为 O(n)），这在内存资源有限的场景中可能需要权衡。

二、归并排序的实现原理

2.1 分治法的核心思想

归并排序的实现分为三个步骤：

1. 分解（Divide）：将原始数组递归地拆分为两个子数组，直到每个子数组的长度为 1（或更小）。
2. 解决（Conquer）：对每个子数组进行排序（当子数组长度为 1 时，它本身已经是有序的）。
3. 合并（Merge）：将两个有序的子数组合并成一个更大的有序数组。

2.2 合并两个有序数组的细节

合并是归并排序的关键步骤。假设我们有两个已排序的数组 left 和 right，合并过程如下：

• 使用两个指针 i 和 j 分别指向 left 和 right 的起始位置。
• 比较当前元素的大小，将较小的元素放入结果数组，并移动对应的指针。
• 当其中一个数组遍历完毕后，将另一个数组的剩余元素直接追加到结果数组中。

形象比喻：合并过程类似于两个人在整理两叠已排序的纸牌，两人轮流将较小的纸牌放到新堆中，最终得到一叠完整的有序纸牌。

三、归并排序的代码实现

3.1 Python 实现示例

以下是归并排序的 Python 代码，包含详细注释：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 分解：将数组拆分为两半
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 合并有序子数组
    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0

    # 比较并合并元素
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # 追加剩余元素
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

3.2 代码逻辑解析

• 递归终止条件：当子数组长度为 1 时，直接返回该数组（递归基）。
• 分解过程：通过 mid 将数组分为左右两部分，递归调用 merge_sort 对子数组排序。
• 合并过程：merge 函数通过双指针法高效合并两个有序数组，时间复杂度为 O(n)。

四、归并排序的时间与空间复杂度分析

4.1 时间复杂度

• 最佳/平均/最坏时间复杂度：
  归并排序的性能对输入数据的初始顺序不敏感，其时间复杂度始终为 O(n log n)。
  • 分解阶段：递归拆分的时间复杂度为 O(log n)（二分拆分直到子数组长度为 1）。
  • 合并阶段：每次合并操作的时间复杂度为 O(n)，总共有 log n 层合并操作。
    因此，总时间复杂度为 O(n log n)。

4.2 空间复杂度

归并排序的空间复杂度为 O(n)，主要原因是每次合并操作需要额外的存储空间来保存中间结果。这一特性在内存资源有限的场景中可能成为瓶颈，但换来了稳定的性能表现。

五、归并排序的实战案例与对比

5.1 实战案例：排序学生成绩

假设我们有一个学生成绩的数组：

scores = [82, 65, 93, 48, 74, 55, 91, 32]
sorted_scores = merge_sort(scores)
print(sorted_scores)  # 输出：[32, 48, 55, 65, 74, 82, 91, 93]

5.2 与快速排序的对比

归并排序与快速排序（Quick Sort）是两种经典的 O(n log n) 算法，但它们的实现方式和适用场景不同：
| 特性 | 归并排序 | 快速排序 | |------------------|----------------------------|----------------------------| | 稳定性 | 稳定 | 不稳定 | | 空间复杂度 | O(n) | O(log n)（递归栈空间） | | 最坏时间复杂度 | O(n log n) | O(n²) | | 适用场景 | 内存资源充足时的高效排序 | 内存有限且平均性能优先的场景 |

选择建议：当数据量较大且需要保证稳定性时，归并排序是更优的选择；而快速排序在平均情况下性能更优，但需要处理最坏情况的优化（如随机选择主元）。

六、归并排序的进阶优化与应用场景

6.1 优化方向

• 减少空间开销：可以通过“原地合并”优化，但实现复杂度较高。
• 提前终止条件：当子数组本身有序时，可以跳过合并步骤，提升效率。

6.2 典型应用场景

1. 大规模数据排序：如数据库中的海量记录排序。
2. 稳定性要求高的场景：例如排序包含重复键值的记录（如学生成绩按分数排序，但需保留同分学生的原始顺序）。
3. 外部排序：当数据无法一次性加载到内存时，归并排序的分治思想可扩展到磁盘排序。

结论

归并排序凭借其稳定的性能和清晰的实现逻辑，成为编程和算法学习中不可或缺的工具。通过分治法将复杂问题拆解为简单子问题，再通过合并策略高效整合结果，这一设计思想不仅适用于排序，也为解决其他复杂问题提供了启发。对于编程初学者，理解归并排序的递归逻辑和合并过程是掌握算法设计的关键；而中级开发者则可以通过优化空间复杂度或结合其他算法，进一步提升其实战能力。

掌握归并排序不仅是对一种算法的学习，更是对“分而治之”这一核心算法思想的深刻理解。在后续的算法学习中，这一思想将帮助你更从容地应对复杂问题的挑战。