数据结构与算法 / 系统课时

归并排序

归并排序

归并排序通过“先拆分、后合并”稳定地完成排序。本课将用一个可运行示例说明递归如何缩小问题、合并如何保持有序,以及为什么它始终具有 O(nlog⁡n)O(n\log n) 的时间复杂度但需要额外空间。

学习目标

  • 说明归并排序的拆分、递归与合并过程
  • 编写稳定的归并排序并验证结果
  • 分析时间复杂度、空间开销与适用场景

核心思路

归并排序把数组持续二分,直到每个子数组至多包含一个元素。单个元素天然有序,随后再逐层合并两个有序子数组。合并时只比较两侧当前元素,因此每一层都只需线性扫描全部数据。

相等元素出现时,若优先取左侧元素,它们在排序前后的相对顺序不会改变,因此归并排序可以保持稳定。数组版本通常需要一个长度为 nn 的辅助空间;链表则可通过调整指针完成合并,更适合使用归并思想。

归并排序拆分与合并过程

主示例

下面的实现返回一个新数组,不修改原输入。merge 负责合并两个已有序列表,merge_sort 负责递归拆分。

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

    # 相等时优先取左侧,保留稳定性。
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 其中一侧耗尽后,另一侧剩余部分已经有序。
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(values):
    if len(values) <= 1:
        return values.copy()

    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    return merge(left, right)

data = [38, 27, 43, 3, 9, 82, 10]
sorted_data = merge_sort(data)

print("原数组:", data)
print("排序结果:", sorted_data)

预期输出:

text
原数组: [38, 27, 43, 3, 9, 82, 10]
排序结果: [3, 9, 10, 27, 38, 43, 82]

复杂度与边界

数组在每一层合并时共处理 nn 个元素,递归树高度约为 log⁡n\log n,因此最好、平均和最坏时间复杂度都是 O(nlog⁡n)O(n\log n)。示例中的切片和合并结果需要 O(n)O(n) 额外空间,递归栈还需要 O(log⁡n)O(\log n) 空间。

空数组和单元素数组会直接返回。工程实现可复用一个辅助数组,并用下标区间代替切片,从而减少临时对象和复制开销。遗漏剩余元素、缺少递归终止条件,或在相等时先取右侧,都是常见错误。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

归并排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通