快速选择 Quickselect 如何求第 K 大或第 K 小？

简化版

Quickselect 是快速排序 partition 思想的变体，用来找第 K 大或第 K 小。

每次选择一个 pivot，把数组分成小于 pivot 和大于 pivot 的两边。如果 pivot 最终位置正好是目标下标，就返回；如果目标在左边，只递归左边；如果目标在右边，只递归右边。

它平均时间复杂度是 O(n)，最坏可能退化为 O(n^2)。

详细版

快速排序 partition 后，pivot 会落到它排序后应该在的位置。

Quickselect 不需要把两边都排好，只关心目标下标在哪一边。

target = k - 1  // 第 k 小
pos = partition(nums)
if pos == target: return nums[pos]
if target < pos: search left
else: search right

问题	转换
第 K 小	目标下标 K - 1
第 K 大	目标下标 n - K

平均每轮能丢掉一部分元素，因此平均 O(n)；如果 pivot 总是极端，最坏 O(n^2)。

完整版教学

1. Quickselect 和快排有什么关系

快速排序每次 partition 后，会递归处理左右两边。

Quickselect 也做 partition，但它只进入目标所在的一边。

这就是二者最大的差别：

算法	partition 后
快速排序	左右两边都处理
快速选择	只处理目标所在一边

Quickselect 的价值在于：找第 K 个元素不需要完整排序。

2. partition 给了什么信息

partition 会选一个 pivot，并把它放到最终有序数组中的位置 pos。

以升序为例：

左边元素 <= pivot <= 右边元素

这意味着 pivot 已经排在正确位置。虽然左右两边内部还没有排序，但我们已经知道 pos 前面有多少元素不大于它。

3. 第 K 小如何转换成下标

数组下标从 0 开始。

第 K 小对应下标：

K - 1

如果 partition 返回的 pos 正好等于 K - 1，答案就是 nums[pos]。

如果 pos 更大，说明目标在左边；如果 pos 更小，说明目标在右边。

4. 第 K 大如何转换

第 K 大可以转成升序下标：

n - K

例如长度为 5：

问题	升序下标
第 1 大	4
第 2 大	3
第 5 大	0

这个转换很容易写错，面试手写时要特别小心。

5. 平均为什么是 O(n)

如果 pivot 选择比较均衡，每轮会丢掉大约一半元素。

访问元素总量近似：

n + n/2 + n/4 + ... = 2n

所以平均是 O(n)。

这和快排平均 O(n log n) 不同，因为 Quickselect 每层只走一边。

6. 最坏为什么会退化

如果 pivot 每次都选到最小或最大元素，就只能丢掉 1 个元素。

访问量变成：

n + (n - 1) + (n - 2) + ... = O(n^2)

为了降低退化概率，常用随机 pivot 或三数取中。

7. 和堆解 Top K 怎么选

如果只找第 K 个元素，Quickselect 平均更快。

如果要动态维护数据流中的 Top K，堆更合适。

场景	推荐
静态数组找第 K	Quickselect
数据流维护第 K	堆
需要完整排序	排序算法
需要最坏有保证	堆或特殊线性选择算法

8. 常见误区与追问

• 误区：Quickselect 会把数组完全排好。 它只保证目标元素到位，不保证左右两边内部有序。
• 误区：第 K 大对应下标 K - 1。 升序数组里第 K 大对应 n - K。
• 误区：Quickselect 最坏也是 O(n)。 普通随机版本平均 O(n)，最坏可能 O(n^2)。
• 追问：如何降低退化概率？ 使用随机 pivot 或三数取中。
• 追问：为什么平均比完整快排快？ 因为每轮只递归一边，不需要处理另一边。