快速选择算法（QuickSelect）

题目描述：
给定一个整数数组 nums 和一个整数 k，请找出数组中第 k 个最大的元素。注意，这里的排序顺序是从大到小，即第 1 个最大是数组中的最大值，第 2 个最大是次大值，以此类推。例如，对于 nums = [3,2,1,5,6,4]，k = 2 时，第 2 个最大元素是 5。

解题过程

1. 问题分析
最直接的方法是先对数组排序（例如降序排序），然后直接取第 k-1 个位置的元素。排序的时间复杂度为 O(n log n)。但我们可以用 快速选择算法（QuickSelect） 在平均 O(n) 时间内解决，其思想来源于快速排序的分治策略。

2. 算法核心思想
快速选择算法基于快速排序的 分区（Partition） 操作：

• 在数组中随机选一个元素作为 基准（pivot）。
• 将数组重新排列，使得所有比 pivot 大的元素移到其左侧，比 pivot 小的元素移到其右侧（注意：这里为了找第 k 个最大，我们定义左侧为大于 pivot 的部分）。
• 分区后，pivot 会处在最终排序后的正确位置，假设其索引为 pivot_index。
• 比较 pivot_index 与 k-1（因为第 k 个最大在排序后数组中的索引是 k-1）：
  • 如果 pivot_index == k-1，则 pivot 就是答案。
  • 如果 pivot_index > k-1，说明第 k 个最大在左侧，递归处理左半部分。
  • 如果 pivot_index < k-1，说明在右侧，递归处理右半部分。

3. 分区过程详解（以找第 k 个最大为例）
我们调整分区逻辑，让大于 pivot 的数放在左边，小于 pivot 的数放在右边。
步骤：

1. 随机选择 pivot（例如选最后一个元素），将其交换到末尾。
2. 初始化一个指针 store_index = left（当前处理区间的起始位置）。
3. 从 left 到 right-1 遍历元素：
   • 如果当前元素大于 pivot，将其与 store_index 位置的元素交换，然后 store_index++。
4. 将 pivot（目前在 right 位置）与 store_index 位置交换，此时 pivot 位于最终位置 store_index。
5. 返回 store_index。

示例：nums = [3,2,1,5,6,4], k=2，找第 2 个最大（即排序后索引 1 的元素）。

• 选 pivot=4（末尾），分区后：大于 4 的 [5,6] 在左，小于 4 的 [3,2,1] 在右，pivot 在索引 2（值 4）。
• 因为 pivot_index=2 大于目标索引 1，所以递归左半部分 [5,6]。

4. 时间复杂度

• 平均情况：每次分区大约处理 n + n/2 + n/4 + ... ≈ 2n 次操作 → O(n)。
• 最坏情况（每次 pivot 选到最值）：O(n²)，但随机选择 pivot 可避免。

5. 代码框架（伪代码）

function quickSelect(nums, left, right, k):
    if left == right:
        return nums[left]
    pivot_index = partition(nums, left, right)
    if pivot_index == k:
        return nums[pivot_index]
    elif pivot_index < k:
        return quickSelect(nums, pivot_index+1, right, k)
    else:
        return quickSelect(nums, left, pivot_index-1, k)

function partition(nums, left, right):
    // 随机选择 pivot 并交换到 right
    pivot = nums[right]
    store_index = left
    for i from left to right-1:
        if nums[i] > pivot:  // 注意：大于号确保大的在左
            swap nums[i] and nums[store_index]
            store_index++
    swap nums[store_index] and nums[right]
    return store_index

调用时：quickSelect(nums, 0, len(nums)-1, k-1)。

6. 关键点

• 分区时比较用 > 而不是 <，因为我们要的是第 k 个最大。
• 随机化 pivot 避免最坏情况。
• 每次递归只处理一侧，因此平均时间复杂度为 O(n)。