一、分治算法：化整为零，逐个击破

分治算法，说白了就是四个字——分而治之。我刚开始学算法时，总觉得这名字挺唬人。后来做项目多了才发现，这其实就是我们日常处理复杂问题的本能：遇到一个大麻烦，先拆成几个小麻烦，小麻烦还解决不了？那就再拆。拆到能直接搞定为止。

嗯，这里要注意：不是所有问题都能用分治。能分治的问题，子问题之间必须相互独立，不能有重叠。你想想看，如果子问题之间互相依赖，那拆了也白拆。

1.1 分治算法的适用条件

我在项目中遇到过不少同学，一上来就「分治！分治！」。但分治不是万能的。它有几个硬性条件：

• 可分解：问题能拆成相同类型的子问题
• 子问题独立：子问题之间没有公共子子问题（否则用动态规划更合适）
• 可合并：子问题的解能组合成原问题的解
• 规模足够小时可直接求解：也就是递归的终止条件

我曾经踩过一个坑：用分治去处理一个子问题高度重叠的优化问题，结果时间复杂度比暴力还高。后来换成动态规划，效率直接翻了几十倍。所以，选对算法比写好代码更重要。

1.2 分治的时间复杂度分析

分治算法的时间复杂度，通常可以用主定理（Master Theorem）来求解。假设递归式为：

T(n) = a * T(n/b) + f(n)

其中：

• a：子问题的个数
• n/b：每个子问题的规模
• f(n)：分解和合并的代价

条件	时间复杂度
f(n) < n^(log_b a)（多项式小于）	T(n) = Θ(n^(log_b a))
f(n) = n^(log_b a)（相等）	T(n) = Θ(n^(log_b a) * log n)
f(n) > n^(log_b a)（多项式大于）	T(n) = Θ(f(n))

我个人习惯先画递归树，再套主定理。这样不容易记错公式。

二、归并排序：分治的经典教科书

归并排序是我学分治时第一个手写的算法。它完美体现了分治三步走：

1. 分解：把数组从中间切成两半
2. 解决：递归地对左右两半排序
3. 合并：将两个有序数组合并成一个

2.1 归并排序代码实现

void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;  // 规模足够小，直接返回

    int mid = left + (right - left) / 2;  // 分解

    mergeSort(arr, left, mid);   // 解决左半
    mergeSort(arr, mid + 1, right);  // 解决右半

    merge(arr, left, mid, right);  // 合并
}

void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    // 拷贝回原数组
    for (int p = 0; p < temp.length; p++) {
        arr[left + p] = temp[p];
    }
}

2.2 归并排序的性能分析

指标	值
最坏时间复杂度	O(n log n)
最好时间复杂度	O(n log n)
平均时间复杂度	O(n log n)
空间复杂度	O(n)
稳定性	稳定

归并排序的优点是稳定、时间复杂度稳定。缺点是空间复杂度高。我建议在数据量较大且对稳定性有要求时使用它，比如数据库的排序操作。

三、快速排序：分治的实战派

快速排序，我个人觉得是分治算法里最「聪明」的一个。它不像归并那样老老实实从中间切，而是选一个「基准值」，把数组分成左右两拨——左边都比基准小，右边都比基准大。

3.1 快速排序的核心逻辑

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int pivotIndex = partition(arr, left, right);  // 分区

    quickSort(arr, left, pivotIndex - 1);   // 排左边
    quickSort(arr, pivotIndex + 1, right);  // 排右边
}

int partition(int[] arr, int left, int right) {
    int pivot = arr[right];  // 选最后一个元素作为基准
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }

    swap(arr, i + 1, right);
    return i + 1;
}

3.2 快速排序的性能分析

指标	值
最坏时间复杂度	O(n²)（每次选到最小/最大基准）
最好时间复杂度	O(n log n)（每次选到中位数基准）
平均时间复杂度	O(n log n)
空间复杂度	O(log n)（递归栈空间）
稳定性	不稳定

快排的平均性能非常好，实际应用中比归并排序更常用。但要注意：如果数据已经有序，且你每次都选第一个或最后一个元素做基准，快排会退化成 O(n²)。我建议用三数取中法选基准：取左端、中间、右端三个数的中位数。

四、经典例题：最大子数组和

这道题是分治算法的经典应用。题目很简单：给定一个整数数组，找出一个连续子数组，使得它的和最大。

举个例子：[-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大子数组是 [4, -1, 2, 1]，和为 6。

4.1 分治思路

用分治怎么解？把数组从中间切开，最大子数组只可能出现在三个位置：

1. 完全在左半部分
2. 完全在右半部分
3. 跨越中点

前两种情况递归求解。第三种情况，从中点向左右两边扩展，找到包含中点的最大子数组。

4.2 代码实现

int maxSubArray(int[] nums) {
    return maxSubArrayHelper(nums, 0, nums.length - 1);
}

int maxSubArrayHelper(int[] nums, int left, int right) {
    if (left == right) return nums[left];

    int mid = left + (right - left) / 2;

    int leftMax = maxSubArrayHelper(nums, left, mid);
    int rightMax = maxSubArrayHelper(nums, mid + 1, right);
    int crossMax = maxCrossingSubArray(nums, left, mid, right);

    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

int maxCrossingSubArray(int[] nums, int left, int mid, int right) {
    int leftSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }

    return leftSum + rightSum;
}

五、知识体系总览

下面这张图总结了本章的核心内容，我把它画成了 SVG，方便你对照复习：

六、总结与避坑

分治算法，说白了就是「大事化小，小事化了」。但有几个坑，我帮你提前踩一踩：

• 递归深度：分治通常用递归实现，递归太深会导致栈溢出。我建议在递归函数里加一个深度参数，超过一定阈值就切换成迭代。
• 合并代价：分解和合并的代价不能太高。如果 f(n) 是 O(n²)，那整体复杂度可能还不如暴力。
• 边界条件：写递归时，一定要先写终止条件。我见过太多人先写递归调用，最后才补终止条件，结果逻辑全乱。
• 不要滥用分治：如果子问题有重叠，用动态规划。如果数据规模小，用暴力可能更简单。

---

公众号:蓝海资料掘金营，微信deep3321