快速选择

快速选择（quickselect）在未排序的序列中找第 $k$ 小的值。它借用快速排序的划分步骤，却只继续处理包含目标名次的那一段；不需要把其余元素排成有序。本文的名次从 1 开始：最小值是第 1 小，重复值分别占据各自的名次。

名次落在哪一段

沿用排序词条的七个数 $(6,3,6,2,8,3,5)$，要找第 4 小。以首项 6 为基准，三路划分可能得到 $$(3,2,5,3\mid 6,6\mid 8).$$ 左段四个数都小于 6，因而占第 1 至第 4 名；两个 6 占第 5、6 名；8 占第 7 名。目标落在左段，右两段此后都不用再看。左段以 3 为基准再划分为 $(2\mid 3,3\mid 5)$；扣除一个小于 3 的数和两个等于 3 的数后，第 4 小就是右段唯一的 5。

每轮只追踪目标名次所在的严格一侧；等于基准的一整段可以同时判定。

例如问第 5 小时，第一轮就落在两个 6 的等值段内，直接返回 6。这也是三路划分处理重复值的好处：若把“等于”同时算入左右两边，名次会重叠，后续无法正确扣除已经排除的元素。

划分后的名次不变式

设当前待查区间被分成长度为 $a,b,c$ 的小于、等于、大于三段，目标在当前区间内排第 $r$。若 $r\le a$，目标在小于段，名次仍为 $r$；若 $a<r\le a+b$，答案等于基准；否则到大于段继续找第 $r-a-b$ 小。三种情况互斥且穷尽。

划分只交换元素，不改变元素的多重集合；小于段任何值都排在等值段之前，等值段又排在大于段之前。因此上述名次扣除是正确的，不依赖各段内部已经有序。基准至少占据等值段的一个位置；只要尚未返回，下一轮区间严格缩小，有限输入必会停止。

下面代码把目标名次改成从 0 开始的全数组下标 $k-1$。它在一份副本上原地做三路划分，因此即使左右边界不断移动，目标的全局下标也不必每次重算。循环保持：所求元素仍在 $[lo,hi)$ 中。

快速选择的名次定位

每次划分后只保留第 4 小所在的区间。

打开交互演示

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

输入是非空、元素之间可比较的序列和 $1\le k\le n$；函数返回一个值，不改动传入的序列。为了与图逐步对应，基准固定为当前区间首项。

Python 3

def quick_select(items, k):
    if not 1 <= k <= len(items):
        raise ValueError("k must be between 1 and len(items)")
    a = list(items)
    target = k - 1
    lo, hi = 0, len(a)

    while True:
        pivot = a[lo]
        lt = i = lo
        gt = hi
        while i < gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                gt -= 1
                a[i], a[gt] = a[gt], a[i]
            else:
                i += 1

        if target < lt:
            hi = lt
        elif target >= gt:
            lo = gt
        else:
            return a[target]


if __name__ == "__main__":
    values = [6, 3, 6, 2, 8, 3, 5]
    assert quick_select(values, 4) == 5
    assert quick_select(values, 5) == 6
    assert [quick_select(values, k) for k in range(1, 8)] == sorted(values)
    assert values == [6, 3, 6, 2, 8, 3, 5]

代价与排序的区别

一次三路划分扫描当前区间一次。若每轮保留的严格一侧至多占固定比例，扫描量形成 $n+\alpha n+{\alpha }^{2}n+\cdots =O(n)$，其中 $0<\alpha <1$。本代码固定首项为基准，有序且互异的输入可能每次只排除一个值，最坏时间为 $\Theta (n^2)$；不能把随机基准的期望线性结论直接套到这里。列表副本需 $O(n)$ 空间，循环和划分下标本身只需 $O(1)$ 额外空间。

快速排序要把两侧都排好，平衡时总时间为 $\Theta (n\log n)$；快速选择每轮只保留一侧，目标仅是一个名次对应的值。若需要整张有序表，应直接排序；若只问少数名次，选择可省去无关区间的递归工作。

参考资料

• TheAlgorithms/Python：quick_select.py：同一问题的另一种三列表实现；本文代码、名次约定和例子独立编写。
• Sedgewick、Wayne，Quicksort and Selection：划分与选择的关系。
• 先修：算法与复杂度、快速排序；相关：归并排序。