03 快速排序分治框架：分区的力量

快速排序分治框架：分区的力量

摘要

快速排序是工程实践中使用最广泛的排序算法，也是分治法的经典示范。但面试中考察的不仅是”能不能写出快速排序”，更重要的是：理解分区（Partition）操作的多种变体（Lomuto、Hoare、三路分区）及其各自的适用场景；能从快速排序自然推导出快速选择（QuickSelect），在 $O(n)$ 期望时间内找到第 K 大元素。本文深度剖析这两道核心题目：LeetCode 215（数组中的第 K 个最大元素）和 LeetCode 75（颜色分类，即荷兰国旗问题），还原每个设计选择背后的”为什么”。

---

第 1 章 快速排序的分治结构

1.1 与归并排序的对比

快速排序和归并排序都是 $O(n\log n)$ 的分治排序算法，但它们的设计哲学截然相反：

维度	归并排序	快速排序
复杂工作在哪一阶段	合并阶段（combine 代价高）	分解阶段（divide 代价高）
分解方式	简单取中点（$O(1)$）	分区操作（$O(n)$）
合并方式	有代价的合并（$O(n)$）	不需要合并（$O(1)$）
空间复杂度	$O(n)$（需要临时数组）	$O(\log n)$（原地操作，只需递归栈）
稳定性	稳定	不稳定（元素交换破坏相对顺序）
最坏情况	$O(n\log n)$（始终如此）	$O(n^2)$（分区极不平衡时）

快速排序的核心操作是 Partition（分区）：选择一个枢轴元素（pivot），将数组重新排列，使得所有小于 pivot 的元素在左边，所有大于 pivot 的元素在右边，pivot 本身在正确位置上。

分区之后不需要合并：这是快速排序最优雅的地方。分区完成后，pivot 已经在最终位置，递归分别对左半部分和右半部分排序，两部分之间天然不需要再合并（左段的所有元素都 ≤ pivot ≤ 右段的所有元素）。

1.2 快速排序的整体结构

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;  // 基础情形：0 或 1 个元素，已有序
 
    // 分区：返回 pivot 最终所在的下标
    int pivotIndex = partition(arr, left, right);
 
    // 递归：分别对 pivot 左边和右边排序
    // 注意：pivot 本身已在正确位置，不参与后续递归
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
}

复杂度分析：

• 最优/平均情况：每次分区将数组均匀对半切，$T(n)=2T(n/2)+O(n)$，即 $O(n\log n)$
• 最坏情况：每次分区极不平衡（如 pivot 始终是最小或最大元素），$T(n)=T(1)+T(n-1)+O(n)$，展开后是 $O(n^2)$

---

第 2 章 分区操作的三种变体

2.1 Lomuto 分区

Lomuto 分区是最容易理解的变体，通常用数组最后一个元素作为 pivot：

int partitionLomuto(int[] arr, int left, int right) {
    int pivot = arr[right];  // 选最后一个元素为 pivot
    int i = left - 1;        // i 是小于 pivot 的区域的末尾（exclusive）
 
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            // arr[j] 应该放入"小于等于 pivot"的区域
            i++;
            swap(arr, i, j);
        }
    }
 
    // 将 pivot 放到正确位置：i+1
    swap(arr, i + 1, right);
    return i + 1;  // 返回 pivot 的最终下标
}

不变量：在每次迭代结束时：

• arr[left..i]：所有元素 ≤ pivot
• arr[i+1..j-1]：所有元素 > pivot（待处理）
• arr[j..right-1]：尚未处理
• arr[right]：pivot

循环结束后（j == right），将 arr[right]（pivot）交换到 i+1 的位置，分区完成。

Lomuto 的缺点：当数组有大量重复元素时，Lomuto 分区会将所有重复元素划分到同一侧，导致极不平衡的分区，退化到 $O(n^2)$。

2.2 Hoare 分区

Hoare 分区是快速排序的原始设计，使用双指针从两端向中间扫描：

int partitionHoare(int[] arr, int left, int right) {
    int pivot = arr[left + (right - left) / 2];  // 选中间元素为 pivot
    int i = left - 1;  // 左指针（从左向右找大于 pivot 的元素）
    int j = right + 1; // 右指针（从右向左找小于 pivot 的元素）
 
    while (true) {
        do { i++; } while (arr[i] < pivot);   // 找到左边第一个 >= pivot 的元素
        do { j--; } while (arr[j] > pivot);   // 找到右边第一个 <= pivot 的元素
 
        if (i >= j) return j;  // 两指针相遇或交叉，分区完成
 
        swap(arr, i, j);  // 交换：让大的去右边，小的去左边
    }
}

Hoare 分区的注意事项：

1. 返回的是 j（右指针），不是 pivot 的最终下标。递归时要用 quickSort(arr, left, j) 和 quickSort(arr, j+1, right)，注意边界包含 j。
2. Hoare 分区不保证 pivot 在返回的下标位置上——它只保证 arr[left..j] 的元素都 ≤ pivot，arr[j+1..right] 的元素都 ≥ pivot。
3. Hoare 分区在实践中性能优于 Lomuto：Hoare 平均做的交换次数是 Lomuto 的约 1/3。

2.3 三路分区（Dutch National Flag）

三路分区（也叫荷兰国旗分区）将数组分成三个区域：小于 pivot、等于 pivot、大于 pivot。这是专门针对大量重复元素设计的优化：

// 返回 [lt, gt]：arr[left..lt-1] < pivot，arr[lt..gt] == pivot，arr[gt+1..right] > pivot
int[] partition3Way(int[] arr, int left, int right) {
    int pivot = arr[left + (right - left) / 2];
    int lt = left;    // arr[left..lt-1] < pivot
    int gt = right;   // arr[gt+1..right] > pivot
    int i = left;     // 当前处理位置
 
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr, lt, i);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            swap(arr, i, gt);
            gt--;
            // 注意：i 不递增！因为 arr[gt] 原来的值还未处理
        } else {
            // arr[i] == pivot，直接跳过
            i++;
        }
    }
 
    return new int[]{lt, gt};
}
 
// 使用三路分区的快速排序
void quickSort3Way(int[] arr, int left, int right) {
    if (left >= right) return;
 
    int[] bounds = partition3Way(arr, left, right);
    int lt = bounds[0], gt = bounds[1];
 
    quickSort3Way(arr, left, lt - 1);   // 对小于 pivot 的部分递归
    quickSort3Way(arr, gt + 1, right);  // 对大于 pivot 的部分递归
    // arr[lt..gt] 都等于 pivot，无需递归！
}

三路分区的关键优势：当数组中有大量重复元素时，所有等于 pivot 的元素在一次分区后就”彻底完成了”，不再参与后续递归。例如，对全部相同的数组，三路分区只需 $O(n)$（只做一次分区，递归不再继续），而 Lomuto/Hoare 需要 $O(n^2)$。

---

第 3 章 LeetCode 75：颜色分类（荷兰国旗问题）

3.1 题目

LeetCode 75 - Sort Colors（中等）

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

必须不使用库的 sort 函数来解决这个问题。

输入: nums = [2, 0, 2, 1, 1, 0]
输出: [0, 0, 1, 1, 2, 2]

输入: nums = [2, 0, 1]
输出: [0, 1, 2]

3.2 为什么不用通用排序

这道题三种元素，用计数排序（统计 0、1、2 各有多少个，然后填回）$O(n)$ 时间、$O(1)$ 空间，正确且高效。但这会有两次遍历（第一次统计，第二次填回）。

面试官的考察重点是：**能否用一次遍历（单趟）完成分类？**这正是三路分区（荷兰国旗）算法的价值所在。

3.3 三路分区的直观过程

以 pivot = 1（白色）为基准，将数组分为三段：

[0, 0, ..., 0 | 1, 1, ..., 1 | ?, ?, ..., ? | 2, 2, ..., 2]
               lt             i              gt

• [0, lt-1]：已知都是 0（红色）
• [lt, i-1]：已知都是 1（白色）
• [i, gt]：未知区域，需要处理
• [gt+1, n-1]：已知都是 2（蓝色）

初始时 lt = 0, i = 0, gt = n-1，未知区域覆盖整个数组。我们从 i 开始处理，直到 i > gt（未知区域为空）：

public void sortColors(int[] nums) {
    int lt = 0;          // [0, lt-1] 都是 0
    int gt = nums.length - 1;  // [gt+1, n-1] 都是 2
    int i = 0;           // 当前处理位置
 
    while (i <= gt) {
        if (nums[i] == 0) {
            // 当前是红色（0），应放到左侧区域
            // 与 lt 位置交换，lt 右移，i 右移（因为 lt 位置原来是 1，现在移到 i 了）
            swap(nums, i, lt);
            lt++;
            i++;
        } else if (nums[i] == 2) {
            // 当前是蓝色（2），应放到右侧区域
            // 与 gt 位置交换，gt 左移，但 i 不能右移（因为 gt 原来的值未知，还需要处理）
            swap(nums, i, gt);
            gt--;
        } else {
            // 当前是白色（1），正好在中间区域，直接跳过
            i++;
        }
    }
}

为什么 nums[i] == 2 时 i 不递增？

当 nums[i] == 2，我们把 nums[i] 与 nums[gt] 交换，然后 gt--。交换后 nums[i] 的新值是原来 nums[gt] 的值——这个值我们还没有处理过（gt 的位置在未知区域里），所以不能推进 i，需要在下一次循环中继续处理 nums[i]。

相反，当 nums[i] == 0，我们把 nums[i] 与 nums[lt] 交换，lt 右移，i 右移。这里可以推进 i 是因为：lt 始终 ≤ i，nums[lt] 要么是 1（白色，已处理过并标记为”白色区域”）要么等于 0（在 lt == i 时）。交换后 nums[i] 是 1，这是已处理好的状态（1 本就属于中间区域），所以可以推进 i。

3.4 手工演示

以 nums = [2, 0, 2, 1, 1, 0] 为例：

步骤	nums	lt	i	gt	操作
初始	[2,0,2,1,1,0]	0	0	5
1	[0,0,2,1,1,2]	0	0	4	nums[0]=2，与 nums[5] 交换，gt—
2	[0,0,2,1,1,2]	1	1	4	nums[0]=0，与 nums[0] 交换（lt=i=0），lt++, i++
3	[0,0,2,1,1,2]	1	1	4	nums[1]=0，与 nums[1] 交换，lt++, i++

等等，让我重新演示：

初始 lt=0, i=0, gt=5，nums=[2,0,2,1,1,0]：

1. nums[0]=2：与 nums[5] 交换 → [0,0,2,1,1,2]，gt=4，i 不变=0
2. nums[0]=0：与 nums[0] 交换（自交换）→ [0,0,2,1,1,2]，lt=1, i=1
3. nums[1]=0：与 nums[1] 交换（自交换）→ [0,0,2,1,1,2]，lt=2, i=2
4. nums[2]=2：与 nums[4] 交换 → [0,0,1,1,2,2]，gt=3，i 不变=2
5. nums[2]=1：i++，i=3
6. nums[3]=1：i++，i=4
7. i=4 > gt=3，循环结束

最终 [0,0,1,1,2,2]，正确。

复杂度：时间 $O(n)$（一次遍历），空间 $O(1)$（原地操作）。

---

第 4 章 LeetCode 215：数组中的第 K 个最大元素

4.1 题目

LeetCode 215 - Kth Largest Element in an Array（中等）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

请不使用排序来解决这个问题。（严格来说，面试中 $O(n\log n)$ 的排序解法通常可以接受，但题目鼓励追求更优解）

输入: [3, 2, 1, 5, 6, 4], k = 2
输出: 5

输入: [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
输出: 4

4.2 直觉解法：排序后取下标

将数组排序（降序），然后取 nums[k-1]。时间 $O(n\log n)$，空间 $O(1)$（原地排序）。

但是，题目提示”不使用排序”，面试官期望的是 $O(n)$ 期望时间的解法——快速选择（QuickSelect）。

4.3 快速选择：从快速排序到线性选择

核心洞察：排序是为了找到”排名第 k 的元素”，但排序做了很多”不必要”的工作——它对所有元素进行了全局排序，而我们只需要知道第 k 个位置的元素是什么。

快速选择利用了分区操作的一个特性：分区后，pivot 处于其最终位置，我们知道它在整个数组中的排名。

• 如果 pivot 的排名（下标）恰好是 k，直接返回 pivot
• 如果 pivot 排名 < k，第 k 大元素在右侧（更大的那侧），递归处理右侧
• 如果 pivot 排名 > k，第 k 大元素在左侧（较大的那侧），递归处理左侧

每次递归只需处理一侧（而不是像快速排序那样处理两侧），这是快速选择 $O(n)$ 期望复杂度的来源。

4.4 第 K 大 vs 第 K 小的下标转化

约定数组降序排列，第 k 大的元素在下标 k-1 处；等价地，第 k 大的元素 = 升序排列后下标为 n-k 处的元素。

在代码实现中，通常将”第 k 大”转化为”第 k 小”来处理，避免混淆：找第 k 大 = 找升序排列第 n-k 小（0-indexed）。

4.5 完整实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 第 k 大 = 升序排列中第 (n-k) 小（0-indexed）
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
 
    /**
     * 在 nums[left..right] 中，返回升序第 targetRank 小（0-indexed）的元素
     */
    private int quickSelect(int[] nums, int left, int right, int targetRank) {
        if (left == right) return nums[left];  // 只有一个元素，直接返回
 
        // 分区：将 nums 分为三段，返回 [lt, gt]
        // nums[left..lt-1] < pivot
        // nums[lt..gt] == pivot
        // nums[gt+1..right] > pivot
        int[] bounds = partition(nums, left, right);
        int lt = bounds[0], gt = bounds[1];
 
        if (targetRank < lt) {
            // 目标排名在左段（小于 pivot 的部分）
            return quickSelect(nums, left, lt - 1, targetRank);
        } else if (targetRank > gt) {
            // 目标排名在右段（大于 pivot 的部分）
            return quickSelect(nums, gt + 1, right, targetRank);
        } else {
            // 目标排名在 pivot 段（等于 pivot 的部分）
            // nums[lt..gt] 的值都等于 pivot，所以直接返回 pivot 的值
            return nums[lt];
        }
    }
 
    private int[] partition(int[] nums, int left, int right) {
        // 随机化 pivot 选择：防止最坏情况（如有序数组的退化）
        int randomIndex = left + (int) (Math.random() * (right - left + 1));
        swap(nums, left, randomIndex);
        int pivot = nums[left];
 
        // 三路分区
        int lt = left;
        int gt = right;
        int i = left + 1;
 
        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums, lt, i);
                lt++;
                i++;
            } else if (nums[i] > pivot) {
                swap(nums, i, gt);
                gt--;
            } else {
                i++;
            }
        }
 
        return new int[]{lt, gt};
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

4.6 随机化枢轴的重要性

为什么需要随机化 pivot 选择？

对抗最坏情况：如果总是选第一个或最后一个元素作为 pivot，当输入是有序数组时，每次分区只能从两端”剥离”一个元素，退化为 $O(n^2)$。面试中已知存在刻意构造最坏输入的情况。

期望 $O(n)$ 复杂度的推导：随机化后，期望每次分区将数组大致对半切（至少 25%:75% 的概率是 0.5），期望递归深度是 $O(\log n)$，但因为每次只递归一侧，总期望工作量是：

$T(n)=T(3n/4)+O(n)$（期望最坏情况：每次至少去掉 1/4 的元素）

用主定理：$a=1,b=4/3,f(n)=O(n)$，${\log }_{4/3}1=0<1$，满足情形三，$T(n)=O(n)$。

更严格的分析（利用 indicator 随机变量）可以证明期望比较次数为 $\le 4n$。

生产避坑：快速选择是原地修改的

quickSelect 会修改传入的数组（分区操作会交换元素）。如果调用方不希望数组被修改，需要先复制一份。LeetCode 题目中通常不成问题，但在实际工程代码中要注意这个副作用。

4.7 备选方案：最小堆 TopK

面试中还有一种常见解法：用一个大小为 k 的最小堆维护”当前遇到的最大 k 个元素”。

public int findKthLargest(int[] nums, int k) {
    // 最小堆，大小不超过 k
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
 
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();  // 弹出当前最小的，维持堆大小为 k
        }
    }
 
    // 堆顶就是第 k 大的元素
    return minHeap.peek();
}

堆解法的适用场景：

• 时间复杂度：$O(n\log k)$（每个元素最多做一次 $O(\log k)$ 的堆操作）
• 空间复杂度：$O(k)$
• 适合流式场景：当数据是流式输入（不能全部存入内存），或者 $k\ll n$ 时，堆解法更实用。
• 不适合 $k\approx n$ 的场景：此时 $\log k\approx \log n$，性能接近全排序，不如快速选择。

解法	时间复杂度	空间复杂度	适用场景
排序后取下标	$O(n\log n)$	$O(1)$ 或 $O(n)$	简单，任何场景
快速选择	$O(n)$ 期望	$O(\log n)$ 递归栈	全量内存，追求最优
最小堆	$O(n\log k)$	$O(k)$	流式数据，$k\ll n$
BFPRT	$O(n)$ 最坏	$O(n)$	对最坏情况有严格保证

---

第 5 章 枢轴选择策略深度对比

5.1 固定枢轴的风险

首元素枢轴：对已排序或逆序排列的数组，每次分区只剥离一个元素，退化 $O(n^2)$。

末元素枢轴（Lomuto 默认）：与首元素枢轴同样的问题。

中间元素枢轴（Hoare 默认）：对已排序数组表现良好，但对专门构造的”反中间点”输入仍可能退化。

5.2 随机化枢轴

从 [left, right] 均匀随机选一个位置作为 pivot。期望复杂度 $O(n\log n)$（排序）或 $O(n)$（选择），能对抗绝大多数构造输入。

缺点：对性能有极高要求的场景（如实时系统），期望值不提供最坏情况保证。

5.3 三数取中（Median of Three）

取 arr[left]、arr[mid]、arr[right] 三者的中位数作为 pivot。

这是实际工程中（如 C++ STL 的 std::sort、Java 的 Arrays.sort）常用的优化，能有效避免已排序输入的退化，且不引入随机数开销。

5.4 BFPRT：线性时间最坏保证

BFPRT 算法（由 Blum-Floyd-Pratt-Rivest-Tarjan 五位作者提出）通过选择”中位数的中位数”作为 pivot，保证每次分区至少去掉 30% 的元素，从而在最坏情况下也是 $O(n)$。

但 BFPRT 的实现复杂，常数因子大，实际性能不如随机化的快速选择。在面试中了解其存在即可，极少要求手写。

---

第 6 章 本文核心结论

1. 分区是快速排序的灵魂：快速排序”难”的工作在分区，“简单”的工作在合并（无需合并）——这与归并排序正好相反。

2. 三路分区是重复元素的正确解：大量重复元素时，Lomuto/Hoare 退化，三路分区能将等于 pivot 的元素一次性放到正确位置，避免退化。

3. 快速选择：单侧递归 + 三路分区 = $O(n)$ 期望：快速排序两侧都递归（分治），快速选择只递归一侧（按需），这是从 $O(n\log n)$ 降到 $O(n)$ 的本质原因。

4. 随机化枢轴是工程必须：面试中凡是用快速选择，必须加随机化，否则在已排序输入上会 TLE。

5. 堆 vs 快速选择的权衡：流式/内存受限场景用堆，全量内存追求最优用快速选择。面试中能说清楚两种方案的适用边界，是加分点。