查看“︁快速排序”︁的源代码

'''快速排序'''（quicksort）选一个基准值，把待排序区间分成“小于基准”“等于基准”“大于基准”三段，再分别排序两侧。这里采用三路划分，是为了让大量重复值一次归位；它与只把一个基准元素放到最终位置的两路实现同属快速排序，但划分状态不同。

== 一次三路划分 ==
取 <math>(6,3,6,2,8,3,5)</math>，选首项 6 为基准。划分完成后，数组可能成为 <math>(3,2,5,3\mid6,6\mid8)</math>。竖线只标分区边界，不是数组元素；左侧每项小于 6，中间每项等于 6，右侧每项大于 6。此时两个 6 无须参与后续递归，只要再分别排序长度为 4 和 1 的两侧区间。

[[File:Gezhi-quicksort-three-way.svg|frame|center|alt=数组六三六二八三五以六为基准，三路划分后小于六区为三二五三，等于六区为六六，大于六区为八|三路划分只保证三个区域的大小关系；左侧的 3、2、5、3 此时还没有排好序。]]

用三个下标 <math>lt,i,gt</math> 把当前半开区间 <math>[lo,hi)</math> 分成四段：
* <math>[lo,lt)</math>：小于基准。
* <math>[lt,i)</math>：等于基准。
* <math>[i,gt)</math>：尚未检查。
* <math>[gt,hi)</math>：大于基准。
开始时 <math>lt=i=lo,\ gt=hi</math>，四段条件显然成立。检查 <math>a_i</math>：它小于基准，就与 <math>a_{lt}</math> 交换并同时推进 <math>lt,i</math>；它等于基准，只推进 <math>i</math>；它大于基准，就先减小 <math>gt</math>，再与 <math>a_{gt}</math> 交换，'''暂不推进 <math>i</math>'''，因为换过来的数尚未检查。

在示例中，读到 8 时把它与右端的 5 交换，5 会落到待检查位置；接下来仍要比较这个 5。每一步都使未检查区间 <math>[i,gt)</math> 缩短一格，最终 <math>i=gt</math>，恰得到图中的三个区域。

== 排序的正确性 ==
划分时四段条件保持不变。例如遇到小于基准的数，<math>a_{lt}</math> 原先位于等于区，交换后左区多一个小值；它移到 <math>i</math> 处仍属于等于区，两个下标一起前进即可。遇到大于基准的数，右区多一个大值，换来的未知数留待下一轮判断。循环结束后等于区已经处在所有小值与大值之间。

两侧递归处理的是比原区间更短的区间，因此终会停在长度 0 或 1。假设递归分别将左右两侧排好序，因为左侧每项小于基准、中间等于基准、右侧每项大于基准，三段接起来就是完整有序列。重复值并未被误分到两个递归分支。

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

== Python 实现 ==
此版本直接改动传入的列表，并固定选当前区间首项为基准，以便代码、例子与图一致。函数返回同一列表，便于查看结果。

<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
def quick_sort(a):
    def sort(lo, hi):
        if hi - lo < 2:
            return
        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
        sort(lo, lt)
        sort(gt, hi)

    sort(0, len(a))
    return a


if __name__ == "__main__":
    values = [6, 3, 6, 2, 8, 3, 5]
    assert quick_sort(values) == [2, 3, 3, 5, 6, 6, 8]
    assert quick_sort([]) == []
    assert quick_sort([4, 4, 4]) == [4, 4, 4]
</pre>
</div>

== 代价与次序 ==
一次划分检查每个元素一次，成本为 <math>\Theta(n)</math>。若每次两侧规模接近各半，递归深度约为 <math>\log_2 n</math>，总时间为 <math>\Theta(n\log n)</math>。'''本代码固定选首项'''，不能保证平衡：已经有序且值互异的输入可使一侧空、另一侧只少一个元素，比较量达到 <math>\Theta(n^2)</math>，递归栈最坏也会有 <math>O(n)</math> 层。随机选基准可以改变期望表现，但那是另一项算法条件，不能据此把本代码的最坏界改成 <math>O(n\log n)</math>。

三路划分在全为同一值时只扫一遍，两个严格大小区都为空，时间为 <math>\Theta(n)</math>。它不保证'''稳定性'''：例如三张按数值排序的卡片 <math>(1,2_B,2_C)</math>，划分时首项 1 使右端的 <math>2_C</math> 换到 <math>2_B</math> 前面。若必须保持相等关键字的原次序，可读[[归并排序]]。

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/sorts/quick_sort_3_partition.py TheAlgorithms/Python：quick_sort_3_partition.py]：三路分区选题参考；本站用半开区间和独立编写的代码。
* [https://algs4.cs.princeton.edu/23quicksort/ Sedgewick、Wayne，Quicksort]：划分、不平衡情形与三路排序。
* 先修：[[算法与复杂度]]；对照：[[归并排序]]。
[[分类:算法]]