分治专题：快速排序核心思想与典型应用

易错点提示

• 区间边界：明确各指针维护的区间含义，交换时注意前置/后置自增自减的顺序。
• cur 指针处理：当遇到 2 并与右侧交换时，cur 必须保持不变，因为从右侧换过来的元素可能是 0 或 2，需要重新判断。
• 原地操作：严格遵循 O(1) 空间要求，所有交换均在原数组上进行。

复杂度分析

• 时间复杂度：O(n)。cur 指针最多遍历数组一次，每个元素最多被交换两次。
• 空间复杂度：O(1)。仅使用常数个额外指针。

2. 排序数组（快速排序）

题目链接：912. 排序数组 题目描述：给定整数数组 nums，将其按升序排列。 示例：

• 输入：nums = [5,2,3,1] -> 输出：[1,2,3,5]

算法思路（三分区 + 随机基准）

传统快速排序在数据有序或大量重复时可能退化至 O(n^2)。优化方案如下：

1. 随机基准：每次递归前随机选取基准元素，打乱数据分布，避免最坏情况。
2. 三分区策略：将数组划分为 < key、== key、> key 三部分，减少重复元素的递归开销。
3. 递归排序：仅对 < key 和 > key 的区间递归调用，等于基准的元素已就位。

C++ 代码实现

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(nullptr));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    void quickSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int key = getRandom(nums, l, r);
        int i = l, left = l - 1, right = r + 1;
        while (i < right) {
            if (nums[i] < key) {
                swap(nums[++left], nums[i++]);
            } else if (nums[i] == key) {
                i++;
            } else {
                swap(nums[--right], nums[i]);
            }
        }
        quickSort(nums, l, left);
        quickSort(nums, right, r);
    }

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

易错点提示

• 递归终止：l >= r 时必须返回，防止栈溢出。
• 随机数范围：rand() % (right - left + 1) + left 确保基准索引严格落在当前区间内。
• 三分区指针：left 维护小于区末尾，right 维护大于区开头，i 负责扫描。注意 swap 后指针的移动逻辑。

复杂度分析

• 时间复杂度：平均 O(n log n)。随机基准有效规避了有序数据导致的退化，最坏情况仍为 O(n^2) 但概率极低。
• 空间复杂度：平均 O(log n)，主要为递归调用栈开销。

3. 数组中的第 K 个最大元素（快速选择）

题目链接：215. 数组中的第K个最大元素 题目描述：返回数组排序后第 k 个最大的元素（非去重）。 示例：输入 [3,2,1,5,6,4], k = 2 -> 输出 5

算法思路

快速选择算法基于快速排序的分区思想，但无需完全排序，只需定位目标元素所在区间即可，平均时间复杂度可降至 O(n)。

1. 分区：随机选基准，将数组分为 < key、== key、> key 三部分。
2. 区间判断：
   • 统计右侧（大于基准）元素个数 c。
   • 若 k <= c，说明目标在右侧，递归右区间。
   • 若 k 落在中间区间（c < k <= c + b，b 为等于基准的个数），则基准即为目标，直接返回。
   • 否则目标在左侧，递归左区间，并更新 k 为 k - c - b。

C++ 代码实现

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

private:
    int quickSelect(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 - left - 1; // 等于基准的元素个数
        if (k <= c) return quickSelect(nums, right, r, k);
        else if (k <= c + b) return key;
        else return quickSelect(nums, l, left, k - c - b);
    }

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

易错点提示

• 递归出口：l == r 时直接返回该元素。
• k 的更新：进入左区间查找时，需减去已排除的右侧和中间区间的元素数量（k - c - b）。
• 基准随机化：防止特定测试用例导致算法退化。

复杂度分析

• 时间复杂度：平均 O(n)。每次分区期望排除一半元素，总比较次数为 n + n/2 + n/4 + ... ≈ 2n。
• 空间复杂度：O(log n)，递归栈深度。

4. 最小的 k 个数

题目链接：剑指 Offer 40. 最小的k个数 题目描述：输入整数数组 arr，找出其中最小的 k 个数。 示例：输入 arr = [3,2,1], k = 2 -> 输出 [1,2]（顺序不限）

算法思路

与第 K 大元素类似，本题求最小的 k 个数，只需调整区间判断逻辑：

1. 分区：同样采用随机基准三分区。
2. 区间判断（设左区间个数为 a，中间区间个数为 b）：
   • 若 a >= k：最小的 k 个数全在左区间，递归左区间。
   • 若 a + b >= k：左区间和中间区间已包含至少 k 个最小元素，直接返回。
   • 若 a + b < k：左、中区间元素不足，需进入右区间查找剩余的 k - a - b 个元素。

C++ 代码实现

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if (k == 0 || arr.empty()) return {};
        srand(time(nullptr));
        quickSelect(arr, 0, arr.size() - 1, k);
        return {arr.begin(), arr.begin() + k};
    }

private:
    void quickSelect(vector<int>& arr, int l, int r, int k) {
        if (l >= r) return;
        int key = getRandom(arr, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (arr[i] < key) swap(arr[++left], arr[i++]);
            else if (arr[i] == key) i++;
            else swap(arr[--right], arr[i]);
        }
        int a = left - l + 1; // 小于基准的元素个数
        int b = right - left - 1; // 等于基准的元素个数
        if (a >= k) quickSelect(arr, l, left, k);
        else if (a + b >= k) return;
        else quickSelect(arr, right, r, k - a - b);
    }

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

易错点提示

• 边界处理：k == 0 或数组为空时需直接返回空结果。
• 返回值构造：分区完成后，数组前 k 个元素即为所求，直接截取返回即可，无需额外排序。
• 递归逻辑：注意 k 在递归右区间时的扣减逻辑。

复杂度分析

• 时间复杂度：平均 O(n)。
• 空间复杂度：O(log n)，递归栈开销。

总结

分治策略的核心在于'分而治之'与'递归收敛'。快速排序通过基准划分将无序数组逐步有序化；快速选择则在此基础上剪枝，仅递归目标所在区间，将时间复杂度优化至线性。掌握这些变体不仅能高效解决排序与选择问题，更能培养将复杂问题拆解为可管理子问题的算法思维。