分治的真谛：三指针划分与随机化基准

一、 前言：快排的“死穴”与进化

💬 开篇：传统的快速排序（双指针划分）在遇到大量重复元素或者有序数组时，时间复杂度会退化到 $O(N^2)$。

🚀 进化方向：

1. 三指针划分（荷兰国旗思想）：将数组一次性分为“小于”、“等于”、“大于”三块。遇到大量重复元素时，中间的“等于块”直接跳过，效率提升数倍！
2. 随机基准（Random Pivot）：通过数学概率，将最坏情况发生的概率降到几乎为零。

👍 点赞收藏：这篇的代码模板是目前面试和竞赛中最通用的“万能快排模板”，建议背诵并默写！🔥

---

二、 颜色分类：数组分三块 (Medium)

2.1 题目描述

题目链接：75. 颜色分类

描述：
数组 nums 包含红色(0)、白色(1)和蓝色(2)。原地排序，使相同颜色相邻，顺序为红、白、蓝。
要求：不使用 sort 函数，一次遍历完成。

2.2 深度拆解：三指针算法 (Dutch National Flag)

我们要把数组划分为：[0...0, 1...1, 待处理, 2...2]。
定义三个指针：

• left：指向 0 序列的末尾（初始为 -1）。
• right：指向 2 序列的开头（初始为 n）。
• cur：正在扫描的位置（初始为 0）。

扫描逻辑（数学归纳与证明）：

1. nums[cur] == 0：把它甩到左边。执行 swap(nums[++left], nums[cur++])。

   • 证明：left+1 位置一定是 1（或者就是 cur 本身），交换后 cur 拿到的新数是确定过的，所以 cur 放心右移。

2. nums[cur] == 1：位置正确，不管它。执行 cur++。

3. nums[cur] == 2：把它甩到右边。执行 swap(nums[--right], nums[cur])。

   • 证明：交换过来的数是从右边还没看过的区域拿的，不知道是什么，所以 cur 不能移动，下一轮必须原地再检查一遍！

ASCII 状态图：

[ 0 0 | 1 1 1 | ? ? ? | 2 2 ]
      ^       ^       ^
     left    cur    right

2.3 C++ 代码实战

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = n, cur = 0;

        while (cur < right) {
            if (nums[cur] == 0) {
                // 把 0 换到左边去
                swap(nums[++left], nums[cur++]);
            } else if (nums[cur] == 1) {
                // 1 本来就在中间，继续扫描
                cur++;
            } else {
                // 把 2 换到右边去
                // 重点：换过来的数没看过，cur 不能加！
                swap(nums[--right], nums[cur]);
            }
        }
    }
};

---

三、 快速排序：三块划分 + 随机基准 (Medium)

3.1 题目描述

题目链接：912. 排序数组

描述：升序排列数组。

3.2 策略进化：为什么要随机化？

如果每次都选第一个数当基准（Pivot），给一个已经排好序的数组排序，快排就变成了“冒泡”，时间复杂度 $O(N^2)$。
随机化证明：通过随机选择一个位置作为基准，任何一种特定的输入都无法稳定地触发快排的最坏情况。数学上，其期望时间复杂度为严格的 $O(N\log N)$。

结合数组分三块，我们在递归时：

• 左边递归：[l, left]
• 右边递归：[right, r]
• 中间的等于块 [left + 1, right - 1] 已经归位，直接无视！ 这种剪枝在处理全重复数组时速度是惊人的 $O(N)$。

3.3 C++ 代码实战（万能快排模板）

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL)); // 种下随机数种子
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void quickSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;

        // 1. 随机选择基准元素
        int key = nums[rand() % (r - l + 1) + l];

        // 2. 三指针划分 (荷兰国旗)
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right) {
            if (nums[cur] < key) swap(nums[++left], nums[cur++]);
            else if (nums[cur] == key) cur++;
            else swap(nums[--right], nums[cur]);
        }

        // 3. 递归左右区间 [l, left] 和 [right, r]
        // 注意：中间的等于 key 的部分 [left + 1, right - 1] 已经不动了
        quickSort(nums, l, left);
        quickSort(nums, right, r);
    }
};

---

四、 快速选择算法：数组中的第 K 个最大元素 (Medium)

4.1 题目描述

题目链接：215. 数组中的第 K 个最大元素

描述：找出排序后的第 k 个最大的元素。要求 $O(N)$ 时间复杂度。

4.2 深度拆解：为什么是 O(N)？

如果全排好序再拿，是 $O(N\log N)$。
但在快排划分三块后：

• 大于区（右块）个数为 c。
• 等于区（中块）个数为 b。
• 小于区（左块）个数为 a。

贪心决策：

1. 如果 c >= k：说明第 k 大一定在右块，直接去右块找。
2. 如果 c + b >= k：说明第 k 大正好落在等于区，直接返回 key！
3. 否则：说明第 k 大在左块，要去左块找。

数学证明：
每次只进入一侧，总遍历量为 $N+N/2+N/4\cdots =2N$。
因此时间复杂度为严格的 $O(N)$。

4.3 C++ 代码实战

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return quickSelect(nums, 0, nums.size() - 1, k);
    }

    int quickSelect(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[l];

        // 1. 随机选基准并分三块
        int key = nums[rand() % (r - l + 1) + l];
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right) {
            if (nums[cur] < key) swap(nums[++left], nums[cur++]);
            else if (nums[cur] == key) cur++;
            else swap(nums[--right], nums[cur]);
        }

        // 2. 统计各块元素个数
        int c = r - right + 1; // 大于区个数
        int b = right - left - 1; // 等于区个数

        // 3. 分情况讨论
        if (c >= k) {
            return quickSelect(nums, right, r, k);
        } else if (b + c >= k) {
            return key;
        } else {
            // 去左块找，k 要更新（扣掉右块和中块的个数）
            return quickSelect(nums, l, left, k - b - c);
        }
    }
};

---

五、 最小的 K 个数 (Medium)

5.1 题目描述

题目链接：LCR 159. 库存管理（原：最小的 k 个数）

描述：找出数组中最小的 k 个数。

5.2 核心思路

与“第 K 大”完全对称。
三块划分后：[左块(a个), 中块(b个), 右块(c个)]。

1. 如果 a > k：去左块继续找。
2. 如果 a + b >= k：中块和左块的部分已经凑够 k 个了，直接结束递归。
3. 如果 a + b < k：左块和中块全拿走，再去右块找剩下的 k - a - b 个。

5.3 C++ 代码实战

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        qsort(stock, 0, stock.size() - 1, cnt);
        // 返回前 cnt 个元素即可
        return {stock.begin(), stock.begin() + cnt};
    }

    void qsort(vector<int>& nums, int l, int r, int k) {
        if (l >= r) return;

        int key = nums[rand() % (r - l + 1) + l];
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right) {
            if (nums[cur] < key) swap(nums[++left], nums[cur++]);
            else if (nums[cur] == key) cur++;
            else swap(nums[--right], nums[cur]);
        }

        // a: 小于区个数, b: 等于区个数
        int a = left - l + 1, b = right - left - 1;

        if (a > k) {
            qsort(nums, l, left, k);
        } else if (a + b >= k) {
            return; // 凑够了，收工
        } else {
            // 左块中块都要了，去右边找剩下的
            qsort(nums, right, r, k - a - b);
        }
    }
};

---

六、 总结

💬 复盘：快排并不难，难的是如何处理那些“极端输入”。

1. 分三块（Dutch National Flag） 是对抗重复元素的最强武器。
2. 随机化（Randomization） 是对抗有序数组的唯一解。
3. 快速选择（Quick Select） 是在不完全排序的前提下，通过“剪枝”实现 $O(N)$ 统计的数学神迹。