快速排序

概述

快速排序（Quicksort） 是由 C. A. R. Hoare 于 1960 年发明的一种基于 分治法 的排序算法。其期望时间复杂度为 $O(n\lg n)$，最坏情况为 $O(n^2)$，但在实际应用中通常比其他 $O(n\lg n)$ 排序算法更快。

定义

快速排序

快速排序采用分治策略，分为三个步骤：

1. 分解（Divide）：选择数组中的一个元素作为主元（pivot），通过 PARTITION 过程将数组 $A[p..r]$ 划分为两个（可能为空的）子数组 $A[p..q-1]$ 和 $A[q+\mathrm{1..}r]$，使得 $A[p..q-1]$ 中的每个元素 $\le A[q]$，$A[q+\mathrm{1..}r]$ 中的每个元素 $\ge A[q]$。$A[q]$ 位于最终排序位置。
2. 解决（Conquer）：递归地对 $A[p..q-1]$ 和 $A[q+\mathrm{1..}r]$ 调用快速排序。
3. 合并（Combine）：无需合并，因为子数组已经就位。

期望时间复杂度：$O(n\lg n)$ 最坏时间复杂度：$O(n^2)$

核心性质

PARTITION 过程

PARTITION 是快速排序的核心子程序。CLRS 采用 Lomuto 分区方案（末尾元素为主元），也有 Hoare 分区方案（双指针从两端向中间扫描）。

性能分析

• 最好情况：每次划分将数组等分为两半，递归深度为 $\lg n$，总时间 $\Theta (n\lg n)$。
• 最坏情况：每次划分极度不平衡（如已排序数组选末尾为主元），递归深度为 $n$，总时间 $\Theta (n^2)$。
• 期望情况：假设所有排列等概率出现，期望递归深度为 $O(\lg n)$，期望总时间 $O(n\lg n)$。

随机化快速排序

通过 RANDOMIZED-PARTITION 随机选择主元，使得算法的期望性能不依赖于输入分布，期望时间始终为 $O(n\lg n)$。

空间复杂度

• 最好/平均情况：$O(\lg n)$（递归栈深度）
• 最坏情况：$O(n)$

不稳定性

快速排序是不稳定的排序算法，分区操作可能改变相等元素的相对顺序。

章节扩展

第7章：快速排序

快速排序是第7章的核心内容，涵盖了算法描述、性能分析、随机化版本和工程优化。

第7章：快速排序的分析

通过递归关系式和概率分析深入理解快速排序的期望性能。

参见

• 归并排序
• 分治法
• Introsort