分治算法

分治框架

分治三步：Divide（将问题拆成独立子问题）→ Conquer（递归求解）→ Combine（合并子问题结果）。关键性质是子问题相互独立（与 DP 不同，DP 有重叠子问题）。

主定理（Master Theorem）

T(n) = aT(n/b) + f(n)，其中 a 个子问题，规模 n/b，合并代价 f(n)。三种情形：若 f(n) = O(n^log_b(a) / log^k n)，则 T(n) = Θ(n^log_b(a) * log^(k+1) n)（均摊情形）；工程中最常遇到的是 a=2,b=2,f(n)=O(n) → T(n)=O(n log n)（归并排序）。

常见算法复杂度

适用场景

• 问题可拆成规模相近的独立子问题
• 合并步骤是整个算法的核心逻辑
• 需要稳定排序（归并）或精确中位数（Quick Select 随机化）

归并排序 & 逆序对

归并排序：拆成左右两半，递归排序，然后双指针合并两个有序子数组。稳定，O(n log n) 最坏，但需要 O(n) 额外空间。逆序对计数可在合并步骤中 O(1) 额外计算：右半的元素比左半当前元素小时，左半剩余元素个数即逆序对数。

// Merge Sort + count inversions
long long mergeCount(vector<int>& a, int l, int r) {
    if (r - l <= 1) return 0;
    int mid = (l + r) / 2;
    long long cnt = mergeCount(a, l, mid) + mergeCount(a, mid, r);
    vector<int> tmp;
    int i = l, j = mid;
    while (i < mid && j < r) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else { cnt += mid - i; tmp.push_back(a[j++]); } // all a[i..mid) > a[j]
    }
    while (i < mid) tmp.push_back(a[i++]);
    while (j < r)   tmp.push_back(a[j++]);
    copy(tmp.begin(), tmp.end(), a.begin() + l);
    return cnt;
}

典型题目

• 912. 排序数组（归并实现）
• 315. 计算右侧小于当前元素的个数（逆序对变体）
• 493. 翻转对（自定义逆序对条件：nums[i] > 2*nums[j]）
• 23. 合并 K 个升序链表（K 路归并，见堆章节）

稳定性：归并排序是稳定排序（相等元素保持原有相对顺序），快速排序默认不稳定。若需稳定且 O(n log n)，选归并。

Quick Select

Quick Select 找第 k 小（大）元素。随机选 pivot，划分后只递归 pivot 所在的一侧，期望 O(n)，最坏 O(n²)（随机 pivot 可几乎消除最坏情形）。

算法步骤

1. 随机选 pivot，将数组划分为 [< pivot][pivot][> pivot]
2. 若 pivot 下标 == k，直接返回
3. 否则只递归 k 所在的一侧（不需要两侧都处理）

// Quick Select — kth smallest (0-indexed)
int quickSelect(vector<int>& nums, int l, int r, int k) {
    if (l == r) return nums[l];
    int pivot = nums[l + rand() % (r - l + 1)];
    int i = l, j = r;
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) swap(nums[i++], nums[j--]);
    }
    // after partition: nums[l..j] <= pivot <= nums[i..r]
    if (k <= j) return quickSelect(nums, l, j, k);
    if (k >= i) return quickSelect(nums, i, r, k);
    return pivot;
}

典型题目

• 215. 数组中的第 K 个最大元素（Quick Select 或堆）
• 347. 前 K 个高频元素（统计频次后 Quick Select）

vs 堆：Quick Select 期望 O(n)，适合只需一个 Kth 值且不需要前 K 个都有序的情形；堆 O(n log k) 且前 K 个可按顺序弹出。