分治算法实战：快速排序与荷兰国旗问题详解

排序数组

题目描述

给定一个整数数组，不使用内置排序函数，要求时间复杂度为 O(n log n)。这是快速排序的典型应用场景。

核心思路

标准的快速排序通过选取基准值（pivot）将数组分为小于和大于两部分。为了优化性能，我们引入两个关键策略：

1. 随机基准值：避免在有序或近乎有序数组上退化为 O(n^2)。每次递归前随机选择一个元素作为基准。
2. 三路划分（Dutch National Flag）：将数组分为 < key、= key、> key 三部分。当数组中存在大量重复元素时，可以大幅减少递归深度。

对于三路划分，逻辑与上述颜色分类完全一致，只是比较对象变为当前基准值 key。划分完成后，只需对 < key 和 > key 区间递归，等于 key 的部分已有序，无需再处理。

参考实现

class Solution {
public:
    void qsort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        // 随机选择基准值
        int key = nums[l + rand() % (r - l + 1)];
        
        // 三路划分
        int left = l - 1, right = r + 1;
        int 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);
    }

    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
};

第 K 个最大元素

题目描述

找出数组中第 k 个最大的元素。典型的 TopK 问题。

核心思路

解决 TopK 问题通常有两种主流方案：

1. 堆排序：维护一个大小为 k 的小顶堆，遍历数组后堆顶即为答案。时间复杂度 O(n log k)。
2. 快速选择（Quick Select）：基于快速排序的分区思想。利用三路划分将数组分为 < key、= key、> key 三部分。假设 > key 部分长度为 c，= key 部分长度为 b：
   • 若 c >= k，目标在 > key 区间；
   • 若 b + c >= k，目标就是 key；
   • 否则，目标在 < key 区间，需查找第 k - b - c 大的元素。

虽然标题涉及第 K 大，但以下代码展示了通用的排序框架。在实际工程中，针对'最小 K 个数'这类变体（如库存管理），只需取排序后的前缀即可。该框架的核心在于利用分区特性跳过不必要的递归，平均时间复杂度可达 O(n)。

参考实现

class Solution {
public:
    void qsort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int key = nums[l + rand() % (r - l + 1)];
        int left = l - 1, right = r + 1;
        int 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);
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        qsort(stock, 0, stock.size() - 1);
        vector<int> ret(cnt, 0);
        for (int i = 0; i < cnt; i++) ret[i] = stock[i];
        return ret;
    }
};

库存管理 III

题目描述

给定数组 stock 和整数 cnt，返回数组中最小的 cnt 个数。

核心思路

这同样是 TopK 问题的变种。相比全量排序，如果数据量极大，可以使用小顶堆或快速选择来优化。但在本例中，为了展示算法的一致性，我们复用上述快速排序逻辑，排序后直接截取前 cnt 个元素。

实际开发中，若仅需获取结果而不需完整排序，建议优先使用快速选择算法（Quick Select），将时间复杂度从 O(n log n) 降低至 O(n)。

参考实现

class Solution {
public:
    void qsort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int key = nums[l + rand() % (r - l + 1)];
        int left = l - 1, right = r + 1;
        int 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);
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        qsort(stock, 0, stock.size() - 1);
        vector<int> ret(cnt);
        for (int i = 0; i < cnt; i++) ret[i] = stock[i];
        return ret;
    }
};