题目描述
给一个数组，找出其中第 k 个最大的元素（是排序后的第 k 大，不是第 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」都用这套。
参考代码（Python）
1import random
2def partition(nums, lo, hi): # 把基准放到正确位置，返回其下标
3 r = random.randint(lo, hi) # 随机选基准，防有序时退化到 O(n²)
4 nums[r], nums[hi] = nums[hi], nums[r]
5 pivot, i = nums[hi], lo # i = 小于基准的区段末尾
6 for j in range(lo, hi):
7 if nums[j] < pivot: # 比基准小的换到左区
8 nums[i], nums[j] = nums[j], nums[i]; i += 1
9 nums[i], nums[hi] = nums[hi], nums[i] # 基准归位到 i
10 return i
11def findKthLargest(nums, k):
12 target = len(nums) - k # 第K大 = 排序后下标 target
13 lo, hi = 0, len(nums) - 1
14 while True:
15 p = partition(nums, lo, hi) # 基准归位后的下标
16 if p == target: return nums[p] # 命中目标下标
17 elif p < target: lo = p + 1 # 目标在右，只走右半
18 else: hi = p - 1 # 目标在左，只走左半复杂度分析
- 时间复杂度：平均 O(n) —— 只递归一边，规模 n+n/2+n/4+… 约等于 2n；最坏 O(n²)（基准选偏，随机化避免）
- 空间复杂度：O(1) —— 原地分区，迭代写法无递归栈
套路模板
骨架：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 个，下标要从右数；比如 [1..6] 求第 2 大，下标是 6−2＝4（值 5），写成 k＝2 会取到 3，结果整个错位）
- 错误写法：partition 后两边都递归 → 正确写法：只递归含目标的一边（两边都递归就退化成快排 O(n log n)，丢了快速选择平均 O(n) 的优势）
- 错误写法：固定拿末尾当基准 → 正确写法：随机选基准再换到末尾（碰上已排好的数组，固定选末尾每趟划分极不均，退化成 O(n²)；随机一下就稳了）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。