算法知识图谱总览 / 排序与基础算法族 / 快速排序

快速排序

P0basicdeepG-A-1
← 上一个 / 组内merge-sort 组内第 3 / 20返回组索引 全局返回总览 下一个 / 组内heap-sort

What · 是什么

分治排序，期望 O(n log n)，最坏 O(n^2)，常数小

快速排序（quicksort）通过选取基准（pivot）把数组划分为『小于/大于』两部分后递归排序。期望/平均 O(n log n)，最坏 O(n^2)（每次取到最值做基准），空间 O(log n)（递归栈）。非稳定排序。工程上通过随机基准、三数取中、插入排序兜底、三路划分等优化，是 C 库 qsort 与多数语言内建排序的基础。

Why · 为什么

直觉 · Intuition

『选一个中间数，把小的放左边、大的放右边，然后只负责把两边各自排好』。与归并不同，划分本身就在『修位置』，所以无需合并步骤。平均情况下每个元素被比较约 O(log n) 次，故总代价 O(n log n)。

原理 · Principle

期望复杂度证明（经典引理）：设 X 为总比较次数，第 i 小与第 j 小的元素发生比较当且仅当两者之一是最先被选为基准的，概率 2/(j-i+1)。由期望线性性 E[X]=Σ 2/(j-i+1) = O(n log n)。最坏情况（每次基准都是极值）递推 T(n)=T(n-1)+Θ(n)=Θ(n^2)。三路快排（荷兰国旗划分）把相等元素集中到中间，处理大量重复值时最优可达 O(n)。

历史 · History

1960 年由 Tony Hoare 发明，并在 Algol 中实现，是『快排』名字的来源。因其缓存局部性好、常数小，成为实用排序的首选。2009 年前后 Java 等标准库开始转向 Timsort/introsort，C++ std::sort 用 introsort（快排+堆排混合）保证最坏 O(n log n)。

How · 实现

伪代码

quick_sort(a, l, r):            # 排序 [l, r)
    if r - l <= 1: return
    p = partition(a, l, r)        # 划分，返回基准最终下标
    quick_sort(a, l, p)
    quick_sort(a, p + 1, r)

partition(a, l, r):               # Lomuto 划分
    pivot = a[r - 1]
    i = l
    for j in range(l, r - 1):
        if a[j] < pivot:
            swap(a, i, j); i += 1
    swap(a, i, r - 1)
    return i

Python 实现

import random


def partition(a, l, r):
    """Lomuto 划分，基准取区间最后一个元素，返回基准最终位置"""
    pv = a[r - 1]
    i = l
    for j in range(l, r - 1):
        if a[j] < pv:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[r - 1] = a[r - 1], a[i]
    return i


def quick_sort(a, l=0, r=None):
    """快速排序 [l,r)，随机基准（期望 O(n log n)，防毒瘤数据卡成 O(n^2)）"""
    if r is None:
        r = len(a)
    if r - l <= 1:
        return a
    p = random.randrange(l, r)
    a[l], a[p] = a[p], a[l]
    p = partition(a, l, r)
    quick_sort(a, l, p)
    quick_sort(a, p + 1, r)
    return a


def quick_select(a, k, l=0, r=None):
    """快速选择：返回第 k 小元素（0-based），期望 O(n)"""
    if r is None:
        r = len(a)
    while True:
        p = random.randrange(l, r)
        a[l], a[p] = a[p], a[l]
        p = partition(a, l, r)
        if p == k:
            return a[p]
        if p < k:
            l = p + 1
        else:
            r = p


def quick_sort_3way(a, l=0, r=None):
    """三路快排：处理大量重复值不退化（荷兰国旗划分）"""
    if r is None:
        r = len(a)
    if r - l <= 1:
        return a
    p = random.randrange(l, r)
    a[l], a[p] = a[p], a[l]
    pv = a[l]
    lt, gt = l, r
    i = l
    while i < gt:
        if a[i] < pv:
            a[i], a[lt] = a[lt], a[i]
            lt += 1
            i += 1
        elif a[i] > pv:
            gt -= 1
            a[i], a[gt] = a[gt], a[i]
        else:
            i += 1
    quick_sort_3way(a, l, lt)
    quick_sort_3way(a, gt, r)
    return a


if __name__ == "__main__":
    random.seed(42)
    for _ in range(300):
        arr = [random.randint(0, 50) for _ in range(random.randint(0, 120))]
        b = arr[:]
        quick_sort(b)
        assert b == sorted(arr), (arr, b)
        b3 = arr[:]
        quick_sort_3way(b3)
        assert b3 == sorted(arr), (arr, b3)
        if arr:
            k = random.randrange(len(arr))
            assert quick_select(arr[:], k) == sorted(arr)[k], (arr, k)
    print("快排 / 三路快排 / 快速选择 全部正确 OK（300 组随机）")
    print("第 3 小（0-based）示例:", quick_select([3, 1, 4, 1, 5, 9, 2, 6], 3))
PyPy 提示递归深度最坏 O(n) 会爆栈，比赛可改成非递归（显式栈存区间）或随机化。Python 递归开销大，n 很大时手写循环式快排更稳。切片式快排（list 推导式分区）简洁但额外 O(n) 空间且慢，不推荐用于大 n。
时间复杂度期望/平均 O(n log n)，最坏 O(n^2)，三路快排含重复值最优 O(n)
空间复杂度O(log n) 期望（递归栈），最坏 O(n)
注意 · 局限不稳定；朴素实现最坏 O(n^2) 会被毒瘤数据卡；需配合随机化/三数取中/三路划分。快速选择（partition 定位第 k 大）是重要衍生技巧。

易错点

例题

OJ题号难度考点链接
LuoguP11773快速排序模板（需优化防卡）https://www.luogu.com.cn/problem/P1177
OI-Wikibasic/quick-sort2快排期望复杂度证明https://oi-wiki.org/basic/quick-sort/
步骤迷你图（节点 = 算法步骤 · 边 = 流程 · 绿色 = 起始步骤）
上游 · 本知识点依赖（前置/变体/组合/共现）
排序基础概念变体分治与递归前置依赖

信源

✓ = 已核验 · △ = 未核验