数组中第 K 个最大元素

排一遍当然行，O(n log n)。但题目只要「第 K 大」一个数，把整个数组都排好太亏了——大量功夫花在了和答案无关的元素上。

快排里 partition 一轮，能让基准归到它在排序结果里的下标 p。我们只关心「第 K 大该在的下标 target＝n−k」：若 p＝target，基准就是答案；若 p 偏小，目标在右半；偏大则在左半——只递归含目标的那一半，另一半直接扔。这就是快速选择比快排省的地方。

目标：找排序后下标 4 的数：六根柱子。第 2 大＝排序后下标 4 的那个数。我们不排序，用 partition 一步步把它逼出来。

第 1 轮分区 · 选末尾 4 当基准：选最后一个数 4 当基准（橙色）。和快排一样，把比 4 小的甩到左边、不小于 4 的留右边。

扫描 · 3、2、1 都小于 4 → 进左区：从左扫：3、2、1 依次都小于 4，全部留在左区（它们本就在前面，原地不动）。接着 5、6 不小于 4，跳过。

基准 4 归位到下标 3：把基准 4 换到小区后面：4 归位到下标 3（绿色）。左边 [3,2,1] 全小于 4、右边 [6,5] 全大于 4。partition 返回 p＝3。

p=3 小于 target=4 → 只看右半：基准落在下标 3，比目标下标 4 小——这正是「位置不对」的分支：目标在它右边，所以只递归右半 [6,5]，左边那一整段（灰）看都不用看。

第 2 轮分区 · 右半选末尾 5 当基准：只在右半 [6,5] 里继续，选末尾 5 当基准。扫描：6 不小于 5，跳过。

基准 5 归位到下标 4：6 大于 5，5 换到下标 4 归位，6 落到下标 5。partition 返回 p＝4。

p=4 == target → 答案 = 5：基准 5 正好落在下标 4（＝ n−k），它就是第 2 大。返回 5，结束——全程没把整个数组排完，只动了含目标的那一侧。

快排两边都递归（要全排好）；快速选择只要找第 K 个，只走含目标的那一边，所以更快。「第 K 大/小」「找中位数」「Top-K」都用这套。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。