找第 K 个不用排全数组。Partition 一次,pivot 自动落到它最终该在的位置,然后只递归 K 所在的那一边。期望 ,完爆排序的 。

直觉 — partition 就够了,不必完全排序

排序是 ,因为每一层都要把两半都递归排好。但找第 K 个这件事根本不关心其他位置的相对顺序,只关心一件事:

谁的最终位置正好是 K?

这正是 partition 的产物。一次 partition 后,pivot 被放到它”如果数组排好序的话该在的位置” p,且左边全部 pivot,右边全部 pivot。三种情况:

• p == k — 直接返回 nums[p],完事。
• p < k — 第 K 个在右边,递归右半段。
• p > k — 第 K 个在左边,递归左半段。

只递归一边,这是 quickselect 比 quicksort 快一个 log 的根本原因。期望规模每次减半:,等比级数收敛。最坏情况(永远选到极值当 pivot)退化成 ,随机化 pivot 让这件事概率上几乎不发生。

动画 — 跟着 i/j 指针走一遍 partition

下面这个动画演示数组 [3, 6, 2, 8, 1, 5, 4],pivot 取最后一个元素 4。点”下一步”看 Lomuto partition 的两个指针:

• i 指针(绿):指向”下一个小于 pivot 的元素应该放的位置”,i 左边全是 < pivot 的。
• j 指针(青):扫描指针,逐个看。

规则就一条:nums[j] < pivot 就 swap(i, j); i++,否则 j++ 跳过。扫完最后把 pivot swap 到位置 i,partition 结束。

看完动画再读模板,每一步都对得上号。

模板 — Python (随机化 pivot)

import random

def quickselect(nums, k):
    """返回排序后第 k 个元素(0-indexed)。原地修改 nums。"""
    def partition(lo, hi):
        # 随机化:避免有序数组退化成 O(n^2)
        p = random.randint(lo, hi)
        nums[p], nums[hi] = nums[hi], nums[p]
        pivot = nums[hi]
        i = lo
        for j in range(lo, hi):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]
        return i                       # pivot 的最终位置

    lo, hi = 0, len(nums) - 1
    while True:
        p = partition(lo, hi)
        if p == k:   return nums[p]
        elif p < k:  lo = p + 1        # 只递归 K 所在的一边
        else:        hi = p - 1

三个易错点:

1. 必须随机化 pivot。不随机化,遇到已排序数组每次只能排除一个元素,退化成 。
2. k 是 0-indexed。求”第 K 大”要转成 k = n - K,求”第 K 小”是 k = K - 1。
3. 写成 while True + 迭代,不要递归。递归在最坏情况下会爆栈。

三路划分 — 应对大量重复元素

如果数组里有一堆等于 pivot 的元素,Lomuto partition 会反复在它们之间切分,退化。三路划分(荷兰国旗)把数组切成 < pivot、== pivot、> pivot 三段,等值段直接跳过。

def partition3(nums, lo, hi):
    pivot = nums[random.randint(lo, hi)]
    lt, gt, i = lo, hi, lo            # [lo,lt): <pivot;  (gt,hi]: >pivot
    while i <= gt:
        if nums[i] < pivot:
            nums[lt], nums[i] = nums[i], nums[lt]
            lt += 1; i += 1
        elif nums[i] > pivot:
            nums[gt], nums[i] = nums[i], nums[gt]
            gt -= 1                    # 注意 i 不前进,新换来的还没看
        else:
            i += 1
    return lt, gt                      # [lt, gt] 全是 pivot

判断 k 落在哪段:k < lt 走左,k > gt 走右,否则 nums[k] 就是答案。

Quickselect vs 堆做 Top-K — 比较

两个常见误区:”找第 K 个就用堆”、”quickselect 永远更快”。都不对。看场景:

维度	Quickselect	堆 (Heap)
时间(期望)
时间(最坏)
空间	原地
原数组	会被打乱	不动
数据形式	离线(必须全部拿到)	在线/流式可做
多次查询	每次	维护一个堆,/次

怎么选:

• 一次性、离线、内存够、数据量大 → quickselect。
• 流式数据、原数组不能改、需要稳定最坏复杂度、 远小于 → 堆。
• 极端 小():直接扫一遍 ,什么都不用。

注意 远小于 时 实际上很接近 (log k 是个小常数),堆代码还更短,面试里写堆通常更稳。

经典题

• LC 215. 数组中的第 K 个最大元素 — 模板裸题。注意”第 K 大” → k = n - K。
• LC 347. 前 K 个高频元素 — 先统计频次,再对频次做 quickselect(或上堆)。
• LC 973. 最接近原点的 K 个点 — 按距离平方 partition,标准应用。
• LC 324. 摆动排序 II — 先 quickselect 找中位数,再三路划分 + 索引映射。难。
• LC 462. 最小操作次数使数组元素相等 II — 中位数 = 第 个,quickselect 取出来即可,不必排序。

记忆法/易错点

一句话:partition 一次,pivot 归位;K 在哪边就只递归哪边。

三个对照:

问题	算法	复杂度
完全排序	quicksort(递归两边)
找第 K 个	quickselect(递归一边)	期望
维护 Top K	堆(大小 K 的小顶堆)

易错点清单:

1. K 的下标:0-indexed 还是 1-indexed,”第 K 大”还是”第 K 小”,写之前先理清。
2. pivot 必须随机化,不然有序输入直接 。
3. partition 返回 pivot 位置 p,不是值。比较的是 p 和 k 这两个下标。
4. 重复元素多 → 用三路划分,不然退化。
5. 不要递归,用 while True + 调整 lo/hi,防爆栈。
6. 原数组会被打乱。如果调用方不能接受,先 copy 一份。