查看“︁快速选择”︁的源代码

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

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

[[File:Gezhi-quickselect-rank.svg|frame|center|alt=七个数以六为基准分成四个小于六、两个等于六和一个大于六；第4小落在左段，左段再以三划分，最终选中五|每轮只追踪目标名次所在的严格一侧；等于基准的一整段可以同时判定。]]

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

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

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

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

<math-experiment type="algorithm" demo="quick-select" />

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

<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
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]
</pre>
</div>

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

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/searches/quick_select.py TheAlgorithms/Python：quick_select.py]：同一问题的另一种三列表实现；本文代码、名次约定和例子独立编写。
* [https://algs4.cs.princeton.edu/23quicksort/ Sedgewick、Wayne，Quicksort and Selection]：划分与选择的关系。
* 先修：[[算法与复杂度]]、[[快速排序]]；相关：[[归并排序]]。
[[分类:算法]]