原始题目

完善程序：计算数组中第 k 大的元素（使用快速选择算法）。

int quickSelect(int a[], int left, int right, int k) {
    int pivot = a[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (a[j] >= pivot) {
            swap(a[i], a[j]);
            i++;
        }
    }
    swap(a[i], a[right]);
    if (i == k - 1) return a[i];
    else if (i > k - 1) return quickSelect(a, left, i - 1, k);
    else return ___;
}

• A. quickSelect(a, i + 1, right, k)
• B. quickSelect(a, left, i - 1, k)
• C. quickSelect(a, i, right, k)
• D. quickSelect(a, left, right, k - i)

答案：A（quickSelect(a, i + 1, right, k)）

注意：截图中高亮的 D 是干扰项，正确答案是 A。

核心思路：i 就是 pivot 的排名

这段代码的关键在于划分规则：

• 把 ≥ pivot 的元素都换到左边
• 把 < pivot 的元素都换到右边
• 最后把 pivot 放到中间位置 i

划分完成后：

• a[i] 左边有 i - left 个元素，且它们都 ≥ a[i]
• 所以 a[i] 是当前区间 [left, right] 里第 i - left + 1 大的元素

当 left = 0 时（题目里的常见简化写法），a[i] 就是第 i + 1 大的元素。代码里用 i == k - 1 来判断是否命中第 k 大，就是这个道理。

图解：划分后的三种情况

上图中 pivot = 4 排到了第 3 位（i = 2）：

• 若 k = 3，i == k - 1，直接返回 4
• 若 k = 1，i > k - 1，去左半边 {5, 6} 找第 1 大
• 若 k = 5，i < k - 1，去右半边 {3, 2, 1} 找第 5 大

逐项排除

为什么 k 不变

很多人第一次写会下意识以为“右半边的元素排名要减去左边的数量”，于是写出类似 D 的 k - i。但注意：

• i 是 pivot 在当前数组里的绝对下标
• k 是“第 k 大”这个全局目标

进入右半边时，我们要找的仍然是“第 k 大的元素”，只是缩小了搜索范围。下标 i 在划分后已经告诉我们：排名 ≤ i 的元素都在左边或就是 pivot 本身，所以右边只可能包含排名 > i 的元素。但 k 依然是 k，不需要变。

如果像 D 那样写成 k - i，第一次可能还能接近正确，但继续递归时 i 又会变化，k 会越扣越少，最后完全偏离目标排名。

复杂度

工程上常用随机 pivot 或中位数的中位数来避免最坏情况。

易错点

1. 搞混“第 k 大”和“第 k 小”：第 k 大对应 >= pivot 放左边，第 k 小对应 <= pivot 放左边。判断条件正好相反。
2. k 的范围：k 应该是 1 到 right - left + 1，不要传 0 或越界。
3. 区间开闭：quickSelect 的右端点 right 是闭区间，和有些 STL 的 [left, right) 风格不同。
4. C 的死循环风险：quickSelect(a, i, right, k) 没有把 i 排除，下一次划分 pivot 又会被放到 i，区间不缩小，可能死循环或栈溢出。

考点总结（CSP-J/S 初赛、程序填空）

1. QuickSelect 和快速排序的 partition 是同一套代码，区别只在于 QuickSelect 只递归一边。
2. i 就是 pivot 最终下标，也是它的“排名-1”。
3. i == k - 1 命中；i > k - 1 往左；i < k - 1 往右。
4. 递归时 k 保持不变，只缩小左右区间。

思考题

如果把题目改成“第 k 小”，应该把 if (a[j] >= pivot) 改成什么？else 分支又该返回什么？