分治

本章目标：掌握分治三步范式，理解主定理，能写出归并排序和快速排序。

你将学到

• 分治三步：分解 → 解决 → 合并
• 归并排序的实现与逆序对计数
• 快速排序与快速选择
• 主定理分析递归复杂度
• 分治在最大子数组问题上的应用

1. 概念

分治法的核心思想：把大问题分解为结构相同的子问题，递归求解后合并结果。

三个步骤：

1. 分解（Divide）：将问题分成规模更小的子问题
2. 解决（Conquer）：递归求解子问题（足够小时直接求解）
3. 合并（Combine）：将子问题的解组合成原问题的解

分治是很多高效算法的基础：归并排序 O(n log n)、快速排序 O(n log n) 平均、Karatsuba 乘法、最近点对 O(n log n)。理解分治的关键是正确分析递归关系 T(n) = aT(n/b) + f(n) 并用主定理求解。

2. 核心模板

归并排序

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):
    result = []
    i, j = 0, 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

快速排序

import random

def quick_sort(arr, lo, hi):
    """快速排序：分治 + 原地"""
    if lo >= hi:
        return
    # 随机选 pivot 避免最坏情况
    pivot_idx = random.randint(lo, hi)
    arr[lo], arr[pivot_idx] = arr[pivot_idx], arr[lo]
    pivot = arr[lo]
    i, j = lo, hi
    while i < j:
        while i < j and arr[j] >= pivot:
            j -= 1
        arr[i] = arr[j]
        while i < j and arr[i] <= pivot:
            i += 1
        arr[j] = arr[i]
    arr[i] = pivot
    quick_sort(arr, lo, i - 1)
    quick_sort(arr, i + 1, hi)

复杂度

• 归并排序：时间 O(n log n)，空间 O(n)，稳定
• 快速排序：平均 O(n log n)，最坏 O(n²)，空间 O(log n)，不稳定

3. 经典题目精讲

LeetCode 169 · 多数元素

题意：找数组中出现次数超过 n/2 的元素。

思路：分治——将数组分成两半，多数元素一定是某一半的多数元素。也可用 Boyer-Moore 投票法 O(n) O(1)。

def majorityElement(nums):
    """Boyer-Moore 投票法"""
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

LeetCode 53 · 最大子数组和（分治解法）

题意：找连续子数组使和最大。

思路：分治——最大子数组要么全在左半，要么全在右半，要么横跨中点。

def maxSubArray(nums):
    def divide(lo, hi):
        if lo == hi:
            return nums[lo]
        mid = (lo + hi) // 2
        # 左半最大子数组和
        left_max = divide(lo, mid)
        # 右半最大子数组和
        right_max = divide(mid + 1, hi)
        # 横跨中点的最大子数组和
        left_sum = float('-inf')
        cur = 0
        for i in range(mid, lo - 1, -1):
            cur += nums[i]
            left_sum = max(left_sum, cur)
        right_sum = float('-inf')
        cur = 0
        for i in range(mid + 1, hi + 1):
            cur += nums[i]
            right_sum = max(right_sum, cur)
        cross_max = left_sum + right_sum
        return max(left_max, right_max, cross_max)

    return divide(0, len(nums) - 1)

LeetCode 315 · 计算右侧小于当前元素的个数

题意：对每个元素，统计其右侧比它小的元素个数。

思路：归并排序过程中，当右半元素先被放入结果时，说明它比当前左半元素小，计数。

def countSmaller(nums):
    """归并排序统计逆序对变体"""
    n = len(nums)
    arr = list(enumerate(nums))  # (原始下标, 值)
    count = [0] * n

    def merge_sort(arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = merge_sort(arr[:mid])
        right = merge_sort(arr[mid:])
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i][1] <= right[j][1]:
                count[left[i][0]] += j  # right 中有 j 个比它小
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        while i < len(left):
            count[left[i][0]] += j
            merged.append(left[i])
            i += 1
        merged.extend(right[j:])
        return merged

    merge_sort(arr)
    return count

4. 易错点

• ⚠️ 快速排序最坏情况 O(n²)（已排序数组 + 选端点为 pivot），用随机 pivot 避免
• ⚠️ 归并排序合并时 <= 和 < 的选择影响稳定性
• ⚠️ 分治递归深度可能很深，Python 默认递归深度限制约 1000

5. 推荐刷题清单

题号	题名	难度	关键
169	多数元素	Easy	Boyer-Moore
23	合并 K 个升序链表	Hard	分治/堆
315	计算右侧小于当前元素的个数	Hard	归并计数
53	最大子数组和	Medium	分治/DP

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS) 第 4 章