Python归并排序 - 五级 | C++ & Algorithm 编程研习社

用归并排序给成绩单排个序——Python实现详解

你有没有遇到过这样的情况：老师发下来一堆成绩单，让你按从低到高排好顺序？如果只有几张，你可以手动比较；但如果有一百张，手动排就会很累。今天我们要学一种叫做 归并排序 的方法，它就像整理两堆已经排好序的扑克牌，先把整堆牌拆成单张，再两两合并成有序的整堆。归并排序非常稳定、快速，而且思路清晰，特别适合用来理解分治思想。

什么是归并排序？

归并排序（Merge Sort）是一种利用“分治”策略的排序算法。它的核心思想是：

分解：把一个大数组从中间切成两半，然后对左右两半继续切分，直到每个小数组只剩一个元素（一个元素自然就是有序的）。
解决：当数组小到只有一个元素时，它已经是有序的，不用再排序。
合并：把两个已经有序的小数组合并成一个更大的有序数组。合并的方法是：每次比较两个数组的第一个元素，把较小的取出来放到结果中，直到其中一个数组取完，再把剩下的全部放进去。

经过反复的分解和合并，最终整个数组就变得有序了。

分步讲解：从拆牌到合牌

第一步：分解（Divide）

想象你手上有一堆乱序的扑克牌，比如数字牌：[38, 27, 43, 3, 9, 82, 10]。你想把它们从小到大排好。

首先，从中间把这堆牌分成两堆：[38, 27, 43, 3] 和 [9, 82, 10]。
然后每堆再分，直到每堆只有一张牌：
- [38, 27, 43, 3] → [38, 27] 和 [43, 3] → 再分 → [38], [27], [43], [3]
- [9, 82, 10] → [9], [82], [10]

现在，我们有7堆，每堆只有一张牌。一张牌当然是有序的（因为只有一张）。

第二步：合并（Merge）

现在开始合并。合并时，你需要两堆有序的牌，比较最上面的牌（最小的），把小的放到新堆里，直到两堆都放完。

先合并 [38] 和 [27]：比较 38 和 27，27 小，拿出 27；剩下 38，直接放后面。得到 [27, 38]。
合并 [43] 和 [3]：得 [3, 43]。
合并 [9] 和 [82]：得 [9, 82]。
接下来合并 [27, 38] 和 [3, 43]：比较两个堆的第一个元素，3 比 27 小，拿出 3；再比较 27 和 43，27 小，拿出 27；再比较 38 和 43，38 小，拿出 38；最后把剩下的 43 放进去。得到 [3, 27, 38, 43]。
同时合并 [9, 82] 和 [10]（注意右边只有一个元素，也可以看作有序）：比较 9 和 10，9 小拿出；再比较 82 和 10，10 小拿出；最后放 82。得到 [9, 10, 82]。
最后合并 [3, 27, 38, 43] 和 [9, 10, 82]，得到最终有序数组 [3, 9, 10, 27, 38, 43, 82]。

这个过程就像是我们把拆散的牌重新组合，但每次合并都保持了顺序。

生活中的例子：给班级成绩排序

假设你有一张数学考试成绩单，分数分别是：85, 92, 78, 90, 88。你想用归并排序把它们排好。

分解：
- 第一轮：[85, 92] 和 [78, 90, 88]
- 第二轮：[85], [92] 和 [78, 90], [88] → 再分 → [85], [92], [78], [90], [88]
合并：
- [85] + [92] → [85, 92]
- [78] + [90] → [78, 90]
- 然后合并 [78, 90] 和 [88] → 比较 78 和 88，78 小；剩下 90 和 88，88 小；最后放 90 → [78, 88, 90]
- 最后合并 [85, 92] 和 [78, 88, 90] → 得到 [78, 85, 88, 90, 92]

这样成绩就从小到大排好了！

Python代码实现

下面我们用 Python 写一个归并排序。代码分为两部分：一个辅助函数 merge 用来合并两个有序列表，另一个主函数 merge_sort 用来递归分解并调用合并。

def merge(left, right):
    """
    合并两个已经排好序的列表 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(arr):
    """
    归并排序主函数，参数 arr 是待排序列表，
    返回一个新的有序列表（不改变原列表）。
    """
    # 基准情况：如果列表长度小于等于1，它已经有序
    if len(arr) <= 1:
        return arr

    # 分解：找到中间位置，将列表切成左右两半
    mid = len(arr) // 2
    left_half = arr[:mid]    # 左半部分
    right_half = arr[mid:]   # 右半部分

    # 递归排序左、右两部分
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # 合并两个有序部分，并返回结果
    return merge(left_sorted, right_sorted)

# 测试一下：给成绩单排序
scores = [85, 92, 78, 90, 88]
print("原始分数：", scores)
sorted_scores = merge_sort(scores)
print("排序后分数：", sorted_scores)  # 输出：[78, 85, 88, 90, 92]

运行结果：

原始分数： [85, 92, 78, 90, 88]
排序后分数： [78, 85, 88, 90, 92]

归并排序的特点

特点	说明
稳定性	如果两个元素相等，合并时保持它们的原始顺序。这对某些需要保持相对顺序的场景（比如按成绩排，相同成绩按学号排）很有用。
时间复杂度	无论数据原本是乱序还是有序，归并排序总是先分解再合并，每次合并需要 O(n) 时间，共约 log₂(n) 层，所以总时间稳定为 O(n log n)。
空间复杂度	每次合并都会创建一个新的列表存放结果，所以需要额外的 O(n) 空间。这是它比快速排序稍“吃内存”的地方。
适用场景	数据量很大时，归并排序表现稳定；特别适合外部排序（比如硬盘上的大数据），但内存紧张时可能不如原地排序。

新手容易犯的 3 个常见错误

忘记处理剩余元素
在 merge 函数中，如果只写了 while 循环，没有在循环后添加 extend 剩余元素，那么当一边取完后，另一边剩下的所有元素都会丢失。结果：列表变短或漏掉元素。
递归基条件写错
有人可能会写成 if len(arr) == 0: 或 if len(arr) == 1:，但正确的条件是 if len(arr) <= 1。因为长度为零的数组也是有序的（空数组），用 <= 可以同时处理空列表和单元素列表，避免递归出错。
没有返回结果
merge_sort 是递归函数，每次调用必须 return 排序后的列表。如果忘记写 return，函数会返回 None，导致上层合并时出错。提示：确保每个分支都有 return。

完整可运行示例（包含所有代码）

下面是一个完整的程序，你可以直接复制到 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(arr):
    """归并排序"""
    if len(arr) <= 1:         # 基准情况：长度<=1时有序
        return arr

    mid = len(arr) // 2       # 中间位置
    left = merge_sort(arr[:mid])   # 排序左半
    right = merge_sort(arr[mid:])  # 排序右半
    return merge(left, right)      # 合并并返回

# 测试不同数据
test_list = [38, 27, 43, 3, 9, 82, 10]
print("原列表：", test_list)
print("排序后：", merge_sort(test_list))

# 成绩排序
grades = [85, 92, 78, 90, 88]
print("成绩排序：", merge_sort(grades))

# 空列表
print("空列表：", merge_sort([]))

运行输出：

原列表： [38, 27, 43, 3, 9, 82, 10]
排序后： [3, 9, 10, 27, 38, 43, 82]
成绩排序： [78, 85, 88, 90, 92]
空列表： []

学完归并排序，接下来可以学什么？

快速排序：也是分治思想，但它是原地排序，速度更快（平均情况下），不过不稳定。和归并排序对比学习，能加深对分治的理解。
二分查找：在有序数据中快速查找某个值，归并排序正好能为二分查找准备好有序数组。
分治算法：归并排序是分治的经典例子，你还可以了解求最大子数组和、棋盘覆盖等分治问题。

归并排序就像搭积木：先把大积木拆成小积木，再把小积木按规则拼回去。掌握了它，你就迈出了算法思维的重要一步！

例题精讲