核心要点

  • 思路：选基准 pivot，partition 把小于它的放左、大于的放右，再递归两侧

  • 复杂度：平均 O(n log n)，最坏（已排序+固定取端点）退化为 O(n²)，空间 O(log n) 递归栈

  • 优化：随机化选 pivot 避免最坏；大量重复元素用三路切分；小区间切换插入排序

标准回答

快速排序是基于分治的原地排序：每轮选一个基准元素 pivot，通过 partition 把数组划分成「小于 pivot」和「大于 pivot」两部分，使 pivot 落到最终位置，再对左右两部分递归。平均时间 O(n log n)，但当每次划分极不均衡（如对已排序数组固定取首/尾元素为 pivot）时退化为 O(n²)。常用优化包括随机化选 pivot 打破最坏情况、对大量重复元素用三路切分、小区间改用插入排序。下面给出随机化的 Lomuto 分区实现：

python
import random


def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:                    # 区间长度 <= 1，递归出口
        return arr
    p = partition(arr, lo, hi)      # 划分，p 为 pivot 最终位置
    quicksort(arr, lo, p - 1)       # 递归左半
    quicksort(arr, p + 1, hi)       # 递归右半
    return arr


def partition(arr, lo, hi):
    # 随机选 pivot 并换到末尾，避免对有序数组退化
    rand = random.randint(lo, hi)
    arr[rand], arr[hi] = arr[hi], arr[rand]
    pivot = arr[hi]
    i = lo                          # i 指向下一个 < pivot 的存放位
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]   # pivot 归位
    return i


if __name__ == '__main__':
    data = [5, 2, 9, 1, 5, 6, 3]
    print(quicksort(data))          # [1, 2, 3, 5, 5, 6, 9]

常见误区

⚠️ 常见踩坑

固定取首元素为 pivot 时，对已排序数组会退化成 O(n²) 且递归深度 O(n) 可能栈溢出；快排不稳定（相等元素相对顺序可能改变），需要稳定排序时应选归并排序。

追问

追问 1：为什么平均 O(n log n) 而最坏 O(n²)？随机化如何缓解？

每层 partition 是 O(n)，若每次大致均分则递归深度 O(log n)，总 O(n log n)；若每次只分出一个元素则深度 O(n)，总 O(n²)。随机选 pivot 使出现持续极端划分的概率极低，期望仍为 O(n log n)。

追问 2：三路快排（荷兰国旗）解决什么问题？

当数组有大量重复元素时，普通二路划分会把等于 pivot 的元素反复参与递归。三路切分把数组分成 <、=、> 三段，等于 pivot 的部分直接定位不再递归，对大量重复键能从 O(n²) 改善到接近 O(n)。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

🎯 相关面试题