题目描述
给一个数组，找出其中第 k 个最大的元素（是排序后的第 k 大，不是第 k 个不同的）。
思路解析
排一遍当然行，O(n log n)。但题目只要「第 K 大」一个数，把整个数组都排好太亏了。
快排里 partition 一轮，能让基准归到它最终的位置，左边都比它小、右边都比它大。我们只关心「第 K 大该在的那个下标」，所以只递归含目标的那一半，另一半直接扔——这就是快速选择。
目标：找排序后下标 4 的数：六根柱子。第 2 大＝排序后下标 4 的那个。我们不排序，用分区一步步把它逼出来。
第 1 轮分区：选末尾 4 当基准：选最后一个 4 当基准（橙色）。把比 4 小的甩到左边、比 4 大的留右边。
4 归位到下标 3：分完区，4 落到了下标 3（绿色＝已归位）。3、2、1 在它左边，6、5 在它右边。
4 在下标 3 < 目标 4 → 只看右半：基准在下标 3，我们要的是下标 4，在它右边——所以只递归右半 [6,5]，左边那一整段（灰）看都不用看。这就是它比快排省的地方。
第 2 轮分区：右半选 5 当基准：只在右半 [6,5] 里继续。选末尾 5 当基准。
5 归位到下标 4：6 > 5，5 归到了下标 4。
下标 4 == 目标 → 答案 = 5：基准 5 正好落在下标 4（= n−k），它就是第 2 大。返回 5，结束——全程没把整个数组排完。
快排两边都递归（要全排好）；快速选择只要找第 K 个，只走含目标的那一边，所以更快。「第 K 大/小」「找中位数」都用它。
参考代码（Python）
1import random
2def findKthLargest(nums, k):
3 target = len(nums) - k # 第K大 = 排序后下标 target
4 lo, hi = 0, len(nums) - 1
5 while True:
6 p = partition(nums, lo, hi) # 基准归位后的下标
7 if p == target: return nums[p]
8 elif p < target: lo = p + 1 # 只往含目标的一边走
9 else: hi = p - 1复杂度分析
- 平均：O(n) —— 每轮规模减半，n+n/2+…≈2n
- 最坏：O(n²) —— 基准选偏（随机化避免）
套路模板
骨架：target = n−k、partition 拿到归位下标 p、只往 p 偏向 target 的那边收。和快排唯一的差别就是「只递归一边」。
1def quick_select(nums, k):
2 target = len(nums) - k # 第K大的下标
3 lo, hi = 0, len(nums) - 1
4 while lo <= hi:
5 p = partition(nums, lo, hi)
6 if p == target: return nums[p]
7 if p < target: lo = p + 1 # 只走一边
8 else: hi = p - 1易错点
- ❌ 第 K 大用下标 k → ✅ 下标是 n − k（第 K 大＝排序后倒数第 k 个，下标要从右数）
- ❌ partition 后两边都递归 → ✅ 只递归含目标的一边（两边都递归就退化成快排 O(n log n)，丢了快速选择的优势）
- ❌ 固定拿末尾当基准 → ✅ 随机选基准再换到末尾（碰上已排好的数组，固定选末尾会退化成 O(n²)；随机一下就稳了）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。