第15课：归并排序

1. 学习目标

完成本课学习后，你将能够：

1. 理解“分而治之”（Divide and Conquer）的核心思想。
2. 描述归并排序算法的工作原理和步骤。
3. 分析归并排序的时间复杂度、空间复杂度和稳定性。
4. 编写一个完整的归并排序函数。
5. 将归并排序的思想应用于解决类似问题。

2. 核心概念

归并排序是分治思想的经典应用。它的策略非常直观：“分而治之，有序合并”。我们可以把它想象成整理一副混乱的扑克牌：

1. 分 (Divide)：将一副牌尽可能平均地分成两半。
2. 治 (Conquer)：分别对这两半牌进行排序（如果一半还是乱的，就继续对它进行“分”）。
3. 合 (Merge)：当左右两半牌都各自有序后，将它们合并成一副完全有序的牌。合并时，只需从两堆牌的顶部依次比较，取出较小的那张放到新堆里，直到所有牌都取出。

这个过程的关键在于“合并”两个已经有序的数组。这就像拉上衣服的拉链，只要两边的链齿都是按顺序排好的，就能轻松地合拢。

算法步骤：

1. 递归分解：将当前数组从中间一分为二，对左右两个子数组递归地进行归并排序，直到子数组的长度为1（天然有序）。
2. 合并有序子数组：将两个有序的子数组合并成一个新的有序数组。

重要特性：

• 稳定性：归并排序是稳定的排序算法。在合并过程中，如果两个元素相等，我们可以确保在原始数组中靠前的元素，在合并后的数组中依然靠前。
• 时间复杂度：O(n log n)。无论最好、最坏还是平均情况，时间复杂度都是 O(n log n)。分解需要 O(log n) 层，每层合并需要 O(n) 的时间。
• 空间复杂度：O(n)。它需要额外的数组空间来存储合并过程中的临时数据，这是它相较于原地排序算法（如快速排序）的主要代价。

3. 代码示例

下面是一个用Python实现的归并排序算法。代码清晰地分离了“分解”和“合并”两个逻辑。

def merge_sort(arr):
    """
    归并排序主函数
    :param arr: 待排序的列表
    :return: 排序后的新列表 (非原地排序)
    """
    # 递归基准情况：当列表长度小于等于1时，直接返回（已有序）
    if len(arr) <= 1:
        return arr
    
    # 1. 分解 (Divide)：找到中间点，分成左右两半
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # 2. 递归治理 (Conquer)：对左右两半分别进行归并排序
    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)
    
    # 3. 合并 (Merge)：将两个有序子数组合并
    return merge(sorted_left, sorted_right)


def merge(left, right):
    """
    合并两个有序数组
    :param left: 有序左子数组
    :param right: 有序右子数组
    :return: 合并后的有序数组
    """
    merged = []
    i = j = 0  # i, j 分别是 left 和 right 的指针
    
    # 比较两个数组的当前元素，将较小的放入结果数组
    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


# 测试代码
if __name__ == "__main__":
    # 测试用例
    test_cases = [
        [38, 27, 43, 3, 9, 82, 10],
        [],
        [1],
        [5, 4, 3, 2, 1],
        [1, 2, 3, 4, 5]  # 已有序数组
    ]
    
    for arr in test_cases:
        original = arr.copy()
        sorted_arr = merge_sort(arr)
        print(f"原始数组: {original}")
        print(f"排序后:   {sorted_arr}")
        print("-" * 30)

输出结果：

原始数组: [38, 27, 43, 3, 9, 82, 10]
排序后:   [3, 9, 10, 27, 38, 43, 82]
------------------------------
原始数组: []
排序后:   []
------------------------------
原始数组: [1]
排序后:   [1]
------------------------------
原始数组: [5, 4, 3, 2, 1]
排序后:   [1, 2, 3, 4, 5]
------------------------------
原始数组: [1, 2, 3, 4, 5]
排序后:   [1, 2, 3, 4, 5]
------------------------------

4. 实践练习

练习1：手动模拟合并过程

给定两个已排序的子数组：left = [1, 5, 8] 和 right = [2, 4, 7]。请手动写出 merge(left, right) 函数每一步的执行过程，并给出最终合并结果。 预期输出： [1, 2, 4, 5, 7, 8]

练习2：实现降序归并排序

修改上面的归并排序代码，使其能够将数组按从大到小的顺序排序。 要求：只需修改 merge 函数中的比较逻辑。 测试输入：[3, 1, 4, 1, 5, 9, 2, 6] 预期输出：[9, 6, 5, 4, 3, 2, 1, 1]

练习3：统计逆序对（进阶）

逆序对定义：对于数组 [i, j]，如果 i < j 但 arr[i] > arr[j]，则称 (arr[i], arr[j]) 为一个逆序对。例如，[2, 4, 1, 3, 5] 中有 (2,1), (4,1), (4,3) 共3个逆序对。 归并排序在合并过程中可以高效地统计逆序对数量。请修改归并排序代码，使其在排序的同时，统计并返回原数组中逆序对的总数。 测试输入：[2, 4, 1, 3, 5] 预期输出：排序后 [1, 2, 3, 4, 5]，逆序对数量：3

5. 常见错误

1. 切片索引错误：

   • 错误：mid = len(arr) / 2 （在Python 3中得到浮点数），或错误使用切片 arr[mid:]。
   • 正确：使用整数除法 mid = len(arr) // 2，并理解切片 [:mid] 和 [mid:] 是左闭右开区间。

2. 合并时遗漏剩余元素：

   • 错误：只写了一个 while i < len(left) and j < len(right) 循环，循环结束后没有处理 left 或 right 中剩余的元素。
   • 正确：循环结束后，必须用 merged.extend(left[i:]) 和 merged.extend(right[j:]) 将剩余元素加入结果。因为其中一个数组已空，这两行代码最多只有一行会实际添加元素。

3. 递归基准情况遗漏：

   • 错误：忘记处理数组长度为0或1的情况，导致无限递归或索引错误。
   • 正确：函数开头必须包含 if len(arr) <= 1: return arr。

4. 混淆稳定性的条件：

   • 错误：在 merge 函数中使用 if left[i] < right[j]。
   • 正确：使用 if left[i] <= right[j]。当元素相等时，先取左边的元素，这是保证稳定性的关键。

6. 小结

• 核心思想：归并排序完美体现了分治策略——将问题分解为更小的子问题，递归解决，再合并结果。
• 关键步骤：“分”（递归地一分为二）-> “治”（递归地排序子数组）-> “合”（合并两个有序数组）。
• 算法分析：
  • 时间复杂度：O(n log n)，非常稳定，不受输入数据初始顺序影响。
  • 空间复杂度：O(n)，需要与原数组等大的额外空间。
  • 稳定性：稳定。
• 适用场景：当对稳定性有要求，或者数据是链表结构（链表的归并排序空间复杂度可优化至 O(1)）时，归并排序是非常好的选择。它也是外部排序（数据太大无法全部载入内存）的基础算法。
• 与希尔排序的对比：希尔排序是基于插入排序的改进，其时间复杂度取决于增量序列，最坏情况为 O(n²)。归并排序则提供了稳定的 O(n log n) 保证。
• 下一站：我们将学习另一种经典的分治排序算法——快速排序，它在平均情况下通常比归并排序更快，但最坏情况下的时间复杂度较差，并且是不稳定的。