分治：归并、快排与主定理

分治的核心思想

分治（Divide & Conquer）= 分解 + 递归求解 + 合并

分治三步骤：
1. Divide   — 将问题分解为若干规模更小的子问题
2. Conquer  — 递归求解子问题（子问题足够小时直接解）
3. Combine  — 合并子问题的解，得到原问题的解

与一般递归的区别：分治强调子问题相互独立且与原问题结构相同。

归并排序——分治的经典实现

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;           // base case：单个元素
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);           // 分：左半
    mergeSort(arr, mid + 1, right);      // 分：右半
    merge(arr, left, mid, right);        // 治：合并
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid)  tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    System.arraycopy(tmp, 0, arr, left, tmp.length);
}

复杂度：T(n) = 2T(n/2) + O(n) → O(n log n)，稳定排序，空间 O(n)

快速排序——原地分治

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

private 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) {
            swap(arr, ++i, j);
        }
    }
    swap(arr, i + 1, right);
    return i + 1;
}

复杂度：平均 O(n log n)，最坏 O(n²)（已排序数组 + 固定基准）

优化手段：随机化基准、三路分区（处理大量重复元素）、小数组用插入排序

主定理（Master Theorem）

用于快速分析分治算法的时间复杂度：

$$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$

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

经典分治应用

数组中的逆序对（归并思路）

// 在归并过程中统计逆序数
private long mergeCount(int[] arr, int left, int mid, int right) {
    // 当右半部分 arr[j] < 左半部分 arr[i] 时
    // arr[i..mid] 全部与 arr[j] 构成逆序对
    long count = 0;
    int i = left, j = mid + 1;
    // ...（标准merge，在选右侧元素时 count += mid - i + 1）
    return count;
}

最接近的点对

在 n 个点中找距离最近的两点：

• 暴力 O(n²)
• 分治 O(n log n)：左右各找，再考虑跨越中线的点对

大整数乘法（Karatsuba）

A = a·10^(n/2) + b,  B = c·10^(n/2) + d
A×B = ac·10^n + (ad+bc)·10^(n/2) + bd
Karatsuba: 3次乘法代替4次
  p = ac, q = bd, r = (a+b)(c+d) - p - q = ad+bc
复杂度 O(n^1.585)

分治 vs 动态规划

核心优化实践