分治思想：从归并排序到最近点对

图：分治的通用骨架——几乎所有 Θ(n log n) 算法都长这样

分治的通用骨架只有三步：分解（Divide）把大问题拆成相同的小问题；解决（Conquer）小到能直接解就递归到底；合并（Merge）把子解拼回原答案。几乎所有 $\Theta(n\log n)$ 算法都长这样。

三个经典例子

归并排序：拆成两半 → 递归排 → 合并两有序段。
快速排序：选基准 → 分区 → 拼回。
最近点对：按 x 中线分平面 → 递归求左右最近对 → 跨中线只校验"窄带"内的点，合并代价降到 $O(n)$。

参考代码：分治框架模板

def divide_and_conquer(problem):
    if base_case(problem):               # ② 解决
        return solve(problem)
    halves = split(problem)              # ① 分解
    subs = [divide_and_conquer(h) for h in halves]
    return merge(subs)                   # ③ 合并

def split(arr):
    mid = len(arr) // 2
    return arr[:mid], arr[mid:]

掌握这个骨架，你就拥有了一把"万能钥匙"：遇到能天然拆分的问题，先想分治，再用主定理估复杂度。

关联推荐

• 插入、选择、冒泡排序（KU） — 排序是分治的第一课
• 算法通关训练营·排序篇（课程） — 系统拆解归并与快排
• 算法与问题求解入门（KU） — 算法范式的总纲