快速排序

概述

快速排序（Quicksort）是一种基于分治法的原地排序算法。其核心过程为：选择一个主元（pivot），将数组分为小于和大于主元的两部分（分区），然后递归排序两部分。快速排序的期望时间复杂度为 $\Theta (n\log n)$，最坏为 $\Theta (n^2)$。通过随机化选择 pivot 可以避免最坏情况。在实践中，快速排序通常是最快的通用排序算法之一。

定义

快速排序（Quicksort）

快速排序的分治过程：

1. 选择主元（Choose Pivot）：从数组中选择一个元素作为 pivot
2. 分区（Partition）：将数组重新排列为 $A[p..q-1]\le \text{pivot}\le A[q+\mathrm{1..}r]$，pivot 放在位置 $q$
3. 递归排序（Conquer）：递归地对 $A[p..q-1]$ 和 $A[q+\mathrm{1..}r]$ 进行快速排序

分区操作（Lomuto 或 Hoare 方案）在 $\Theta (n)$ 时间内完成，且是原地操作。

核心性质

性质	描述	备注
期望时间	$\Theta (n\log n)$	输入随机或随机化 pivot 时
最坏时间	$\Theta (n^2)$	每次选到最大或最小元素作为 pivot
原地排序	空间复杂度 $\Theta (\log n)$（递归栈）	优于归并排序的 $\Theta (n)$
不稳定排序	相等元素的相对顺序可能改变	区别于归并排序
实际性能	通常是最快的通用排序	缓存友好，常数因子小
随机化	随机选择 pivot 可避免最坏情况	实践中几乎不会遇到最坏情况

复杂度分析

期望情况（随机化 pivot 或输入随机排列）：

$T(n)=2T(n/2)+\Theta (n)⟹\Theta (n\log n)$

最坏情况（每次选到极值）：

$T(n)=T(n-1)+\Theta (n)⟹\Theta (n^2)$

随机化快速排序的期望比较次数：$2n\ln n+O(n)$，由概率分析中的指示器随机变量得出。

快速排序 vs 归并排序

比较维度	快速排序	归并排序
平均时间	$\Theta (n\log n)$	$\Theta (n\log n)$
最坏时间	$\Theta (n^2)$	$\Theta (n\log n)$
空间	$\Theta (\log n)$	$\Theta (n)$
稳定性	不稳定	稳定
原地	是	否
实际速度	通常更快	通常稍慢

应用场景

• 通用排序：实践中最常用的排序算法之一（C 的 qsort、Java 的基础排序）
• 内排序：数据可全部装入内存时的首选
• 随机化算法：随机化快速排序是随机化算法的经典案例
• 三路快速排序：处理大量重复元素的优化版本

参见

• 分治法 — 快速排序的设计策略
• 归并排序 — 另一种分治排序算法
• 概率分析 — 分析随机化快速排序的期望性能
• 递归关系式 — 快速排序的递推关系
• 动态多线程 — 并行快速排序