分治算法实战：从荷兰国旗到快速排序变体

二、快速排序（Quick Sort）

LeetCode 912. Sort an Array

在颜色分类的基础上，我们可以实现完整的快速排序。核心依然是分区（Partition），但这次的目标是将数组分为小于基准值、等于基准值、大于基准值三部分。

优化策略：随机基准

传统的快排如果选取固定位置的基准（如第一个元素），在有序或近乎有序的数组上性能会退化至 O(n²)。为了避免这种情况，我们引入随机化策略，每次递归前随机选择一个元素作为基准（pivot）。

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

    void qsort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        
        // 随机选择基准并交换到合适位置（此处逻辑整合在 partition 中）
        int key = getRandom(nums, l, r);
        
        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        
        // 递归处理左右两部分
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    int getRandom(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
};

通过这种三路划分，即使存在大量重复元素，也能保证较好的效率。递归结束后，整个数组即完成排序。

三、第 K 个最大元素（Quick Select）

LeetCode 215. Kth Largest Element in an Array

若只需找到第 K 大的元素，全排序显得过于奢侈。我们可以利用上述的分区思想，仅递归查找目标所在的区间，这就是快速选择算法（Quick Select）。

逻辑推导

假设我们将数组按基准值分为三部分：

• 右区间 [right, r]：大于基准值的元素，数量为 c。
• 中间区间 [left+1, right-1]：等于基准值的元素，数量为 b。
• 左区间 [l, left]：小于基准值的元素。

判断逻辑如下：

1. 若 c >= k：说明第 K 大元素在右区间，递归查找右区间。
2. 若 b + c >= k：说明第 K 大元素就是基准值本身，直接返回。
3. 否则：说明在左区间，递归查找左区间，且新的 K 值为 k - b - c。

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

    int qsort(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[l];
        
        int key = getRandom(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        
        while (i < right) {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        
        int c = r - right + 1;      // 右区间数量
        int b = right - 1 - (left + 1) + 1; // 中间区间数量
        
        if (c >= k) return qsort(nums, right, r, k);
        else if (b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }

    int getRandom(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
};

此方法平均时间复杂度为 O(n)，远优于 O(n log n) 的全排序。

四、最小的 K 个数

AcWing 480. 最小的 k 个数

该问题与 TopK 类似，只是方向相反。我们需要找出数组中最小的 K 个数，不要求排序。

实现要点

同样采用三路划分，但关注点在于左侧的小于基准值区域。

• 计算左侧区域大小 a。
• 若 a > k：目标在左侧，递归左半部分。
• 若 a + b >= k：目标已在左侧及中间区域，停止递归。
• 否则：目标在右侧，需继续寻找剩余的 k - a - b 个数。

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> nums, int k) {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1, k);
        return {nums.begin(), nums.begin() + k};
    }

    void qsort(vector<int>& nums, int l, int r, int k) {
        if (l >= r) return;
        
        int key = getRandom(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        
        while (i < right) {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        
        int a = left - l + 1;       // 左侧区域大小
        int b = right - 1 - (left + 1) + 1; // 中间区域大小
        
        if (a > k) qsort(nums, l, left, k);
        else if (a + b >= k) return;
        else qsort(nums, right, r, k - a - b);
    }

    int getRandom(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
};

总结

从颜色分类到快速排序，再到快速选择，本质都是对'分区'这一操作的灵活运用。掌握三路划分（Dutch National Flag）技巧，不仅能解决特定场景的排序问题，更是优化 TopK 类问题的利器。在实际工程中，随机化基准的选择能有效避免最坏情况，确保算法的稳定性。