数组第 K 大：划分一次，只搜还含答案的一半
整段排序是多余的。快选让 pivot 落到最终下标；等于 n−K 就返回，否则丢掉没有答案的那一侧。小顶堆大小 K 是另一条路。
目标下标 target=n−k（升序第 n−k 小）。反复用末尾元素做 pivot 划分，左侧 ≤ pivot。p==target 返回 nums[p]；p<target 则 lo=p+1，否则 hi=p−1。期望 O(n)，最坏 O(n²)。大小 K 的小顶堆是 O(n log K)。
这是 LeetCode 215. Kth Largest Element in an Array。整数数组 nums 和整数 k，返回其中第 k 个最大的元素。不去重：两个 5 算两个位置。不必稳定，不必把整段排好。
主例 nums = [3,2,1,5,6,4]，k=2。从大到小是 6,5,4,3,2,1，第 2 大是 5。演示里目标下标 n−k=4，两次划分后 pivot 落在 4，值是 5。
第一直觉是排序后取倒数第 k 个，O(n log n)，能做对，但多排了不需要的数。缺的是：划分一次就能确定 pivot 的最终名次，另一半可以扔掉。下面从这块缺口推出快选，并对照堆。
pivot 的下标就是它排完后的名次
第 k 大在升序数组里是下标 n−k。主例 n=6、k=2，target=4，也就是升序第 5 小。完全排序会把 1、2、3 也排好，这些比较对答案没有贡献。
快排划分的性质：选一个 pivot，把小于等于它的换到左边，再把它放到中间下标 p。p 就是这个值在最终升序里的位置。缺的只是「p 和 target 比完之后别再碰另一侧」。p==target，答案就是 nums[p]。p<target，第 k 大在右边，lo 改成 p+1。p>target，答案在左边，hi 改成 p−1。
代码用区间末尾当 pivot，从左扫描：≤ pivot 的跟写指针交换。主例第一次区间 [0..5]，末尾是 4。3、2、1 都 ≤4，5 和 6 大于 4，4 换到下标 3，数组变成 [3,2,1,4,6,5]。p=3 < 4，丢掉左边，只搜 [4..5]。
用手走第二次。区间 [4,5] 是 [6,5]，末尾 pivot=5。6>5，不换，最后 5 和 6 对调，数组变成 [3,2,1,4,5,6]，p=4，正好等于 target，返回 5。演示四帧：先标目标 4，再标第一次 p=3，再标第二次 p=4，最后写第 2 大是 5。
期望每次扔掉一半，n+n/2+n/4+…=2n。最坏每次只缩 1，退化成 O(n²)，随机打乱或随机 pivot 可压概率。另一条路：扫数组，维护容量 k 的小顶堆，堆顶就是当前第 k 大；扫完堆顶即答案，O(n log k)，最坏有保证。k=1 就是最大值，扫一遍即可，不必上堆或快选。
扔掉的一半不必有序p=3 时左边 [3,2,1,4] 仍是乱的。它们都 ≤4，而 target 在右边，左边永远当不了第 2 大。不必再排。
Go：QuickSelect
func findKthLargest(nums []int, k int) int {n := len(nums)target := n - klo, hi := 0, n-1for {p := partition(nums, lo, hi)if p == target { return nums[p] }if p < target { lo = p + 1 } else { hi = p - 1 }}}func partition(a []int, lo, hi int) int {pivot := a[hi]i := lofor j := lo; j < hi; j++ {if a[j] <= pivot { a[i], a[j] = a[j], a[i]; i++ }}a[i], a[hi] = a[hi], a[i]return i}
1target=n-k。主例 6-2=4，要的是升序下标 4 上的数。
2partition 用 a[hi] 做 pivot。主例第一次 hi 上是 4，归位到下标 3。
3p<target 只抬 lo，p>target 只降 hi。主例第二次区间变成 [4,5]，5 归位即返回。
总结
快选只搜含 n−k 的一侧。主例 4 先落到下标 3，5 再落到下标 4，第 2 大是 5。
- 整段排序能对，但多做了左边那些用不上的比较。
- 划分后 pivot 的下标就是最终名次。另一侧可以乱着扔掉。
- 小顶堆容量 k 是最坏 O(n log k) 的备选；面试常先讲快选再补堆。