前言

在计算机科学中，分治算法（Divide and Conquer） 是一种经典且强大的算法设计范式。其核心思想是：“分而治之”——将一个复杂的大问题分解为若干个规模较小、结构相似的子问题，递归地解决这些子问题，最后将子问题的解合并得到原问题的解。

分治法广泛应用于排序（如快速排序、归并排序）、查找（如二分查找）、数值计算（如大整数乘法）、几何问题等领域。掌握分治思想，不仅能提升算法效率，更能培养“化繁为简”的编程思维。

本文将围绕7个典型分治算法演练展开，每个部分包含：

• 算法思想基础
• 实现思路详解
• 示意图辅助理解
• Python实战代码（含注释）

我们将从最简单的二分查找开始，逐步深入到复杂的整数划分问题，最终完成一个完整的分治算法实战指南。

1. 二分法找出有序列表指定值

算法思想基础

二分查找适用于已排序数组。每次比较中间元素与目标值，若相等则返回；若目标值小于中间值，则在左半部分继续查找；否则在右半部分查找。时间复杂度 O(log n)。

实现思路

1. 定义左右指针 left 和 right
2. 循环直到 left > right
3. 计算中点 mid = (left + right) // 2
4. 比较 arr[mid] 与目标值，调整搜索区间
5. 若未找到，返回 -1

示意图

初始: [1, 3, 5, 7, 9, 11, 13], target=7
      ↑         ↑         ↑
     left      mid      right

第一次: mid=3 → arr[3]=7 == target → 找到！

代码实现

# 文件名：binary_search.py

def binary_search(arr, target):
    """
    二分查找：在有序列表中查找目标值
    :param arr: 已排序的列表
    :param target: 要查找的目标值
    :return: 目标值索引，若不存在返回-1
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2  # 计算中点
        if arr[mid] == target:
            return mid  # 找到目标
        elif arr[mid] < target:
            left = mid + 1  # 在右半部分查找
        else:
            right = mid - 1  # 在左半部分查找
    
    return -1  # 未找到

# 测试
if __name__ == "__main__":
    data = [1, 3, 5, 7, 9, 11, 13]
    print(binary_search(data, 7))  # 输出: 3
    print(binary_search(data, 6))  # 输出: -1

2. 求顺序表中数据的最大值

算法思想基础

虽然最大值问题通常用线性扫描解决，但我们可以用分治法演示递归思想：将数组分为两半，分别求左右最大值，再取较大者。

实现思路

1. 若数组只有一个元素，直接返回该元素
2. 否则，分割数组为左右两部分
3. 递归求左右部分的最大值
4. 返回两者中的较大值

示意图

[3, 7, 2, 9, 1]
  ↙       ↘
[3,7]     [2,9,1]
  ↓         ↓
  7         9
  ↘       ↙
   max(7,9)=9

代码实现

# 文件名：max_divide_conquer.py

def find_max(arr, left, right):
    """
    分治法求数组最大值
    :param arr: 输入数组
    :param left: 左边界
    :param right: 右边界
    :return: 最大值
    """
    # 基本情况：只有一个元素
    if left == right:
        return arr[left]
    
    # 分割
    mid = (left + right) // 2
    
    # 递归求解左右部分
    left_max = find_max(arr, left, mid)
    right_max = find_max(arr, mid + 1, right)
    
    # 合并：返回较大值
    return max(left_max, right_max)

# 测试
if __name__ == "__main__":
    data = [3, 7, 2, 9, 1]
    print(find_max(data, 0, len(data)-1))  # 输出: 9

3. 查找列表中元素的最小值和最大值

算法思想基础

同时求最小值和最大值可以优化比较次数。传统方法需 2n-2 次比较，分治法可减少至约 3n/2 次。

实现思路

1. 若数组长度为1，min=max=该元素
2. 若长度为2，直接比较两个元素
3. 否则，分割数组，递归求左右部分的 min/max
4. 合并：全局 min = min(left_min, right_min)，全局 max = max(left_max, right_max)

示意图

[4, 1, 8, 3]
  ↙      ↘
[4,1]      [8,3]
  ↓           ↘
min=1,max=4   min=3,max=8
  ↓                  ↓
global_min=1, global_max=8

代码实现

# 文件名：min_max_divide_conquer.py

def find_min_max(arr, left, right):
    """
    分治法同时求最小值和最大值
    :param arr: 输入数组
    :param left: 左边界
    :param right: 右边界
    :return: (最小值, 最大值)
    """
    # 基本情况1：只有一个元素
    if left == right:
        return arr[left], arr[right]
    
    # 基本情况2：两个元素
    if right == left + 1:
        if arr[left] < arr[right]:
            return arr[left], arr[right]
        else:
            return arr[right], arr[left]
    
    # 分割
    mid = (left + right) // 2
    
    # 递归求解左右部分
    left_min, left_max = find_min_max(arr, left, mid)
    right_min, right_max = find_min_max(arr, mid + 1, right)
    
    # 合并
    global_min = min(left_min, right_min)
    global_max = max(left_max, right_max)
    
    return global_min, global_max

# 测试
if __name__ == "__main__":
    data = [4, 1, 8, 3]
    min_val, max_val = find_min_max(data, 0, len(data)-1)
    print(f"最小值: {min_val}, 最大值: {max_val}")  # 输出: 最小值: 1, 最大值: 8

4. 找出一组序列中的第k小（大）的元素

算法思想基础

使用快速选择算法（Quickselect），基于快速排序的分区思想。平均时间复杂度 O(n)，最坏 O(n²)。

实现思路

1. 选择一个基准值（pivot）
2. 分区：将数组分为小于 pivot、等于 pivot、大于 pivot 三部分
3. 根据 k 所在区间，递归处理对应部分
4. 当 pivot 位置正好是 k-1 时，返回 pivot

示意图

数组: [3, 2, 1, 5, 4], k=3 (第3小)
选pivot=3 → 分区: [2,1] [3] [5,4]
k=3 > len([2,1])+1 → 在右部分找第 k-len(left)-1=1 小
右部分: [5,4] → 选pivot=4 → 分区: [] [4] [5]
k=1 → 返回4

代码实现

# 文件名：kth_element.py

import random

def partition(arr, left, right):
    """
    分区函数：以最后一个元素为基准
    :param arr: 数组
    :param left: 左边界
    :param right: 右边界
    :return: 基准值的最终位置
    """
    pivot = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i + 1

def quick_select(arr, left, right, k):
    """
    快速选择：找第k小的元素（k从1开始）
    :param arr: 数组
    :param left: 左边界
    :param right: 右边界
    :param k: 第k小
    :return: 第k小的元素
    """
    if left == right:
        return arr[left]
    
    # 随机选择基准以避免最坏情况
    pivot_index = random.randint(left, right)
    arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
    
    pivot_pos = partition(arr, left, right)
    
    # k的位置相对于当前区间的偏移
    rank = pivot_pos - left + 1
    
    if k == rank:
        return arr[pivot_pos]
    elif k < rank:
        return quick_select(arr, left, pivot_pos - 1, k)
    else:
        return quick_select(arr, pivot_pos + 1, right, k - rank)

# 测试
if __name__ == "__main__":
    data = [3, 2, 1, 5, 4]
    print(quick_select(data.copy(), 0, len(data)-1, 3))  # 输出: 3
    print(quick_select(data.copy(), 0, len(data)-1, 1))  # 输出: 1
    print(quick_select(data.copy(), 0, len(data)-1, 5))  # 输出: 5

5. 快速排序

算法思想基础

快速排序是分治法的经典应用。通过“分区”操作将数组分为两部分，左边都小于基准，右边都大于基准，然后递归排序左右部分。

实现思路

1. 选择基准值（pivot）
2. 分区：重排数组，使左边≤pivot，右边≥pivot
3. 递归对左右子数组进行快速排序
4. 基准值已在正确位置，无需额外操作

示意图

[3, 6, 8, 10, 1, 2, 1]
选pivot=1 → 分区: [1,1] [3,6,8,10,2] 
递归左: [1,1] → 已有序
递归右: [3,6,8,10,2] → 选pivot=2 → 分区: [2] [3,6,8,10]
...
最终: [1,1,2,3,6,8,10]

代码实现

# 文件名：quick_sort.py

def partition(arr, low, high):
    """
    分区函数：以最后一个元素为基准
    :param arr: 数组
    :param low: 起始索引
    :param high: 结束索引
    :return: 基准值的最终位置
    """
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

def quick_sort(arr, low, high):
    """
    快速排序主函数
    :param arr: 待排序数组
    :param low: 起始索引
    :param high: 结束索引
    """
    if low < high:
        # 获取分区点
        pi = partition(arr, low, high)
        
        # 递归排序左右部分
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# 测试
if __name__ == "__main__":
    data = [3, 6, 8, 10, 1, 2, 1]
    quick_sort(data, 0, len(data)-1)
    print(data)  # 输出: [1, 1, 2, 3, 6, 8, 10]

6. 实现归并排序

算法思想基础

归并排序采用“分治+合并”策略。先将数组不断二分直到单个元素，然后两两合并有序子数组，最终得到完整有序数组。时间复杂度稳定 O(n log n)。

实现思路

1. 若数组长度≤1，直接返回
2. 分割数组为左右两半
3. 递归排序左右两半
4. 合并两个有序子数组

示意图

[38, 27, 43, 3, 9, 82, 10]
       ↙            ↘
[38,27,43,3]       [9,82,10]
  ↙     ↘         ↙     ↘
[38,27] [43,3]    [9,82]  [10]
  ↓       ↓         ↓       ↓
[27,38] [3,43]    [9,82]  [10]
   ↘    ↙          ↘    ↙
  [3,27,38,43]     [9,10,82]
       ↘             ↙
     [3,9,10,27,38,43,82]

代码实现

# 文件名：merge_sort.py

def merge(left, right):
    """
    合并两个有序数组
    :param left: 左半部分
    :param right: 右半部分
    :return: 合并后的有序数组
    """
    result = []
    i = 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):
    """
    归并排序主函数
    :param arr: 待排序数组
    :return: 排序后的新数组
    """
    # 基本情况：数组长度≤1
    if len(arr) <= 1:
        return arr
    
    # 分割
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    # 合并
    return merge(left_half, right_half)

# 测试
if __name__ == "__main__":
    data = [38, 27, 43, 3, 9, 82, 10]
    sorted_data = merge_sort(data)
    print(sorted_data)  # 输出: [3, 9, 10, 27, 38, 43, 82]

7. 整数划分

算法思想基础

整数划分是指将正整数 n 表示为一系列正整数之和，且不考虑顺序（即 3+2+1 与 1+2+3 视为同一种）。本题要求计算“最大加数为 m”的划分数。

这是一个经典的动态规划或递归问题。我们定义函数 p(n, m) 表示将 n 划分为最大加数不超过 m 的方案数。

递推关系

• 若 n=1 或 m=1，只有一种划分方式
• 若 n<m，等价于 p(n, n)
• 若 n=m，包含 n 本身这一种，加上 p(n, n-1)
• 一般情况：p(n, m) = p(n, m-1) + p(n-m, m)
  • 不包含 m：p(n, m-1)
  • 包含至少一个 m：p(n-m, m)

示意图（以 n=6, m=2 为例）

p(6,2) = p(6,1) + p(4,2)
       = 1 + [p(4,1) + p(2,2)]
       = 1 + [1 + (p(2,1) + p(0,2))]
       = 1 + [1 + (1 + 1)] = 4

具体划分：
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1

代码实现

# 文件名：integer_partition.py

def count_partitions(n, m):
    """
    计算将整数n划分为最大加数不超过m的方案数
    :param n: 要划分的整数
    :param m: 最大允许的加数
    :return: 划分方案数
    """
    # 基本情况
    if n == 0:
        return 1  # 空划分算一种
    if n < 0 or m == 0:
        return 0
    
    # 递归关系
    # 不使用m作为加数 + 使用至少一个m作为加数
    return count_partitions(n, m-1) + count_partitions(n-m, m)

# 优化版本：带记忆化的递归
def count_partitions_memo(n, m, memo=None):
    """
    带记忆化的整数划分计数
    :param n: 要划分的整数
    :param m: 最大允许的加数
    :param memo: 记忆化字典
    :return: 划分方案数
    """
    if memo is None:
        memo = {}
    
    key = (n, m)
    if key in memo:
        return memo[key]
    
    # 基本情况
    if n == 0:
        return 1
    if n < 0 or m == 0:
        return 0
    
    # 递归计算
    result = count_partitions_memo(n, m-1, memo) + count_partitions_memo(n-m, m, memo)
    
    # 存储结果
    memo[key] = result
    return result

# 测试：题目要求计算整数6最大加数是2时的划分数量
if __name__ == "__main__":
    n = 6
    m = 2
    result = count_partitions_memo(n, m)
    print(f"整数{n}最大加数为{m}时的划分数量: {result}")
    # 输出: 整数6最大加数为2时的划分数量: 4
    
    # 验证：列出所有划分
    print("\n具体划分:")
    # 手动列举（用于验证）
    partitions = [
        "2+2+2",
        "2+2+1+1",
        "2+1+1+1+1",
        "1+1+1+1+1+1"
    ]
    for p in partitions:
        print(p)

小结

本文系统介绍了7个典型的分治算法实战案例，涵盖了查找、排序、极值求解和组合数学等多个领域：

1. 二分查找 —— 高效定位有序数据
2. 最大值查找 —— 分治思想的入门实践
3. 最小最大值同步求解 —— 优化比较次数
4. 第k小元素 —— 快速选择算法的应用
5. 快速排序 —— 分治排序的经典代表
6. 归并排序 —— 稳定高效的分治排序
7. 整数划分 —— 递归与动态规划的完美结合

通过本文的学习，你不仅掌握了这些算法的实现细节，更重要的是理解了“分而治之”的核心思想。在实际开发中，面对复杂问题时，不妨尝试将其拆解为更小的子问题，往往能事半功倍。

提示：对于大规模数据，建议优先使用内置函数或标准库（如 sorted(), bisect），但在面试、竞赛或学习场景中，手写分治算法仍是必备技能。

欢迎收藏、转发、点赞！如有任何问题或改进建议，欢迎留言讨论 😊