专题 16排序与分治

16.1排序算法全景图

先给一张性质表。面试不要求手写这些排序（Java 内置的足够好），但性质题（「为什么 Arrays.sort 对对象用归并系而不是快排？」）和选型题（「这个场景该用什么排？」）常考：

16.2Java 内置排序与自定义比较器

力扣题里你几乎总要自定义比较器，这节是默写级内容：

import java.util.*;

// 基本类型：只能升序，更快（双轴快排，无装箱）
int[] a = {3, 1, 2};
Arrays.sort(a);                       // a = [1, 2, 3]

// 对象数组 / List：TimSort（归并系），稳定
Integer[] b = {3, 1, 2};
Arrays.sort(b, (x, y) -> x - y);      // 升序：小的排前面
Arrays.sort(b, (x, y) -> y - x);      // 降序：大的排前面

// 推荐写法：用 Integer.compare 防溢出（见下）
Arrays.sort(b, (x, y) -> Integer.compare(x, y));

// 按二维数组的第 0 列升序，第 0 列相等时按第 1 列降序
int[][] intervals = {{1, 3}, {2, 2}};
Arrays.sort(intervals, (p, q) -> {
    if (p[0] != q[0]) return Integer.compare(p[0], q[0]);
    return Integer.compare(q[1], p[1]);   // 降序：比较顺序反过来
});

记忆口诀：比较器返回负数 = 第一个参数排在前面。升序「小的在前」→ compare(x, y)；降序「大的在前」→ compare(y, x)。

16.3合并区间：排序预处理（中等，力扣 56）

中等 核心：排序把无序变有序，问题瞬间变简单

题意。给一组区间，把所有有重叠的合并成一个。比如 [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]（[1,3] 和 [2,6] 重叠）。

思路推导。不排序时，判断「哪两个区间重叠」要两两比较，合并后区间还可能和更远的区间重叠，越理越乱。 先按左端点排序，观察排序后会发生什么：所有可能重叠的区间必然相邻——因为左端点单调不减，一旦当前区间的左端点大于已合并区间的右端点， 它和之前所有区间都不可能重叠了。于是问题变成线性的「逐个看、能合就合」：

class Solution {
    public int[][] merge(int[][] intervals) {
        // 第一步：按左端点升序排序——一切的前提
        Arrays.sort(intervals, (p, q) -> Integer.compare(p[0], q[0]));

        List<int[]> merged = new ArrayList<>();
        for (int[] cur : intervals) {
            // merged 的最后一个区间与新区间「不相邻重叠」：
            // 新区间的左端点落在最后一个区间的右端点之内
            if (!merged.isEmpty() && cur[0] <= merged.get(merged.size() - 1)[1]) {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], cur[1]);   // 取右端点的较大者（可能完全被包含）
            } else {
                merged.add(cur);                        // 不重叠，开一个新区间
            }
        }
        return merged.toArray(new int[0][]);
    }
}

小例子走一遍：[[1,3],[2,6],[8,10]] → 2 ≤ 3 合并成 [1,6] → 8 > 6 开新段 → [[1,6],[8,10]] ✓

复杂度。时间 O(n log n)（排序主导），空间 O(log n)（排序栈）+ O(n)（结果）。

16.4数组中的第 K 个最大元素：快速选择（中等，力扣 215）

中等 核心：只递归一边，把 O(n log n) 砍成平均 O(n)

题意。在无序数组里找第 K 大的元素。比如 [3,2,1,5,6,4]，k=2 → 5。必须 O(n) 或接近，纯排序是 O(n log n)——能过但面试不够分。

思路推导。回想快排的分区（partition）：选一个基准，把小于它的放左边、大于它的放右边，返回基准的最终下标 p。 此时基准已经处在它排序后的正确位置上。关键观察：如果 p 正好是「第 K 大的位置」（升序下标 n−k），答案就是它； 如果 p 偏左，答案在右半边；偏右，在左半边——且只需要递归那一边。

所以复杂度是 n + n/2 + n/4 + … ≈ 2n = 平均 O(n)：每轮处理量减半，而排序必须两边都递归。这就是「分治只走一半」与「分治两边都走」的差别。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;   // 第 K 大 = 升序数组中下标 n-k 的元素
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int p = partition(nums, lo, hi);   // 随机基准分区
            if (p == target) return nums[p];   // 基准正好落在目标位置
            else if (p < target) lo = p + 1;   // 目标在右侧，只递归右边
            else hi = p - 1;                   // 目标在左侧，只递归左边
        }
        return nums[lo];
    }

    // 随机化基准的分区：把 < pivot 的换到左边，返回 pivot 最终下标
    private int partition(int[] nums, int lo, int hi) {
        int r = lo + (int) (Math.random() * (hi - lo + 1));
        int tmp = nums[r]; nums[r] = nums[hi]; nums[hi] = tmp;  // 基准换到末尾
        int pivot = nums[hi];
        int i = lo;                                   // i 左侧全是 < pivot 的
        for (int j = lo; j < hi; j++) {
            if (nums[j] < pivot) {                    // 遇到小的，换到左边
                tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
                i++;
            }
        }
        tmp = nums[i]; nums[i] = nums[hi]; nums[hi] = tmp;  // 基准归位
        return i;
    }
}

复杂度。平均时间 O(n)（n + n/2 + n/4 + …），最坏 O(n²)（基准总选到极值——随机化后概率可忽略）；空间 O(1)（迭代写法）。

16.5颜色分类：三指针（中等，力扣 75）

中等 核心：一趟扫描 + O(1) 空间的分区

题意。数组里只有 0、1、2 三种值（红白蓝），原地把它们按 0、1、2 排好。要求：一趟扫描 + 常数空间（不许调 sort，不许数 0/1/2 再回填——那是两趟）。

思路推导。其实就是「三路分区」（荷兰国旗问题）：维护三个指针，把数组划成三段：

[  全是 0  |  全是 1（未处理）  |  待定  |  全是 2  ]
 0      zero          i         two     n-1

规则：i 是当前扫描位置，zero 的左边全是 0，two 的右边全是 2。

• nums[i] == 0：和 nums[zero] 交换，zero++、i++（换来的必然是 1，可以直接前进）；
• nums[i] == 1：正是它该待的段，i++；
• nums[i] == 2：和 nums[two] 交换，two--，i 不动——因为从右边换过来的值还没看过，下一轮继续判断它。

class Solution {
    public void sortColors(int[] nums) {
        int zero = 0;                   // nums[0..zero-1] 全是 0
        int two = nums.length - 1;      // nums[two+1..] 全是 2
        int i = 0;                      // i 是当前待判断的元素
        while (i <= two) {
            if (nums[i] == 0) {
                // 和 zero 位交换：换过来的一定是 1（zero 与 i 之间全是 1），可以 i++
                int t = nums[zero]; nums[zero] = nums[i]; nums[i] = t;
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;                    // 1 就在中间段，直接过
            } else {
                // 和 two 位交换：右边换来的值没看过，i 原地不动再判一次
                int t = nums[two]; nums[two] = nums[i]; nums[i] = t;
                two--;
            }
        }
    }
}

复杂度。时间 O(n) 一趟扫描；空间 O(1)。

16.6分治思想：归并排序与逆序对（选学）

选学 核心：分治三步 + 「合并时顺便计数」

分治三步。把问题切成两半（分）→ 分别解决（治）→ 把两半的结果合并（合）。归并排序是教科书样本：切一半、各自排好、 合并两个有序数组（O(n) 双指针，链表专题的 21 题就是它）。分治的复杂度规律：如果「分」和「合」都是 O(n)，总复杂度 O(n log n)——log n 层 × 每层 O(n)。

逆序对（选学，对应力扣 315 / 剑指 51）。逆序对 = 满足 i < j 且 nums[i] > nums[j] 的对数，暴力 O(n²)。 排序后有序数组没有逆序对——所以「边归并边数」：合并左右两个有序半区时，若右半的元素先出队，说明它比左半所有剩余元素都小， 一次性产生「左半剩余元素个数」个逆序对。一次归并顺带完成计数，总复杂度仍是 O(n log n)。

// 逆序对核心片段（完整题见力扣 493 / 剑指 Offer 51）
private long mergeCount(int[] nums, int[] tmp, int lo, int hi) {
    if (lo >= hi) return 0;                       // 只剩一个元素，无逆序对
    int mid = (lo + hi) / 2;
    long cnt = mergeCount(nums, tmp, lo, mid)     // 分 + 治（左半）
             + mergeCount(nums, tmp, mid + 1, hi); // 分 + 治（右半）
    // 合并两个有序半区，顺便统计跨越左右的逆序对
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];                 // 左半元素出队，不产生逆序对
        } else {
            cnt += mid - i + 1;                   // 右半先出队：左半剩余的都和它构成逆序对
            tmp[k++] = nums[j++];
        }
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= hi)  tmp[k++] = nums[j++];
    System.arraycopy(tmp, lo, nums, lo, hi - lo + 1);
    return cnt;
}

16.7本专题常见坑

16.8自测题