第7章 快速排序

导读

快速排序（Quicksort）是实际应用中最广泛使用的排序算法之一。由Tony Hoare于1960年提出，快速排序以其优秀的平均性能、原地排序特性和缓存友好性而著称。虽然最坏情况时间复杂度为O(n²)，但通过随机化等优化，可以快速排序在绝大多数场景下都表现出色。

本章将详细介绍快速排序的算法原理、分区策略、性能分析以及各种优化技术。我们还将探讨快速排序在实际系统中的实现细节和变体。

核心概念详解

7.1 快速排序的基本思想

快速排序采用分治策略：

分解（Divide）：选择一个元素作为主元（pivot），将数组分为两部分，使得左部分的所有元素≤主元，右部分的所有元素≥主元。

解决（Conquer）：递归地对左右两部分进行快速排序。

合并（Combine）：无需合并——分区操作已经保证了整体有序。

算法框架：

QUICKSORT(A, p, r)
    if p < r
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, q + 1, r)

7.2 分区算法

Lomuto分区方案：

PARTITION(A, p, r)
    x = A[r]          // 选择最后一个元素作为主元
    i = p - 1
    for j = p to r - 1
        if A[j] ≤ x
            i = i + 1
            交换A[i]和A[j]
    交换A[i + 1]和A[r]
    return i + 1

工作原理：

• 维护两个区域：A[p..i]（≤主元）和A[i+1..j-1]（>主元）
• 遍历数组，将≤主元的元素放到左边
• 最后将主元放到正确位置

Hoare分区方案：

Hoare分区比Lomuto分区更高效，交换次数更少：

PARTITION(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while TRUE
        repeat j = j - 1 until A[j] ≤ x
        repeat i = i + 1 until A[i] ≥ x
        if i < j
            交换A[i]和A[j]
        else
            return j

7.3 正确性证明

快速排序的正确性可以通过循环不变式证明。

PARTITION的循环不变式：

在for循环的每次迭代开始时：

A[p..i]中的所有元素≤主元x

A[i+1..j-1]中的所有元素>主元x

A[r] = x（主元在原位）

QUICKSORT的正确性：

通过数学归纳法：

• 基本情况：p ≥ r时，子数组最多一个元素，自然有序
• 归纳步骤：假设递归调用正确排序了A[p..q-1]和A[q+1..r]，由于PARTITION保证了A[p..q-1] ≤ A[q] ≤ A[q+1..r]，因此整个数组有序

7.4 性能分析

最坏情况：O(n²)

• 每次分区都产生极端不平衡的划分（0和n-1）
• 发生在数组已经有序且选择最后一个元素作为主元时
• 递归树退化为链状，深度为n

最好情况：O(n log n)

• 每次分区都产生平衡的划分（n/2和n/2）
• 递归树深度为log n
• 每层总代价为O(n)

平均情况：O(n log n)

• 假设所有排列等概率
• 期望递归深度为O(log n)
• 更精确的分析：比较次数约为2n ln n ≈ 1.39n log₂ n

空间复杂度：O(log n)（递归栈）

7.5 随机化快速排序

为了避免最坏情况，可以在选择主元时引入随机性：

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    交换A[i]和A[r]
    return PARTITION(A, p, r)

分析：

• 对任何输入，期望时间复杂度都是O(n log n)
• 最坏情况仍然可能，但概率极低
• 消除了对输入分布的依赖

7.6 三数取中分区

一种常用的主元选择策略是三数取中（Median-of-Three）：

• 取首、中、末三个元素的中位数作为主元
• 减少极端不平衡划分的概率
• 避免在已排序数组上的最坏情况

MEDIAN-OF-THREE(A, p, r)
    mid = ⌊(p + r) / 2⌋
    if A[mid] < A[p]
        交换A[p]和A[mid]
    if A[r] < A[p]
        交换A[p]和A[r]
    if A[r] < A[mid]
        交换A[mid]和A[r]
    交换A[mid]和A[r - 1]
    return PARTITION(A, p, r)

7.7 小数组优化

快速排序在递归到小数组时效率不如插入排序。常见的优化策略：

• 当子数组大小小于阈值（通常10-20）时，切换到插入排序
• 这可以减少约10-15%的运行时间

QUICKSORT-OPTIMIZED(A, p, r)
    if r - p < THRESHOLD
        INSERTION-SORT(A, p, r)
    else
        q = PARTITION(A, p, r)
        QUICKSORT-OPTIMIZED(A, p, q - 1)
        QUICKSORT-OPTIMIZED(A, q + 1, r)

7.8 尾递归优化

快速排序的第二个递归调用是尾递归，可以优化为迭代：

QUICKSORT-TAIL(A, p, r)
    while p < r
        q = PARTITION(A, p, r)
        QUICKSORT-TAIL(A, p, q - 1)
        p = q + 1

这减少了递归栈的深度，从最坏O(n)降低到O(log n)。

7.9 重复元素处理

当数组中有大量重复元素时，标准分区可能产生不平衡划分。改进策略：

三路分区（Dijkstra荷兰国旗问题）：

• 将数组分为三部分：<主元、=主元、>主元
• 递归处理<和>部分，=部分已经有序

THREE-WAY-PARTITION(A, p, r)
    x = A[p]
    lt = p, gt = r, i = p + 1
    while i ≤ gt
        if A[i] < x
            交换A[lt]和A[i]
            lt = lt + 1
            i = i + 1
        else if A[i] > x
            交换A[i]和A[gt]
            gt = gt - 1
        else
            i = i + 1
    return lt, gt

7.10 快速排序的变体

内省排序（Introsort）：

• 结合快速排序和堆排序
• 当递归深度超过2·⌊log₂ n⌋时，切换到堆排序
• 保证O(n log n)最坏情况，同时保持快速排序的平均性能

双主元快速排序（Dual-Pivot Quicksort）：

• 使用两个主元将数组分为三部分
• Java 7+的Arrays.sort使用此算法
• 比传统快速排序更快，减少比较次数

多主元快速排序（Multi-Pivot Quicksort）：

• 使用多个主元
• 适合外部排序和并行排序

重要知识点

知识点1：快速排序的缓存友好性

快速排序的分区操作具有良好的空间局部性：

• 顺序访问数组元素
• 交换操作在相邻或近距离元素间进行
• 对CPU缓存友好，实际性能优于理论分析

这是快速排序在实践中比堆排序更快的重要原因。

知识点2：快速排序的不稳定性

快速排序是不稳定的排序算法。在分区过程中，相等元素的相对顺序可能改变。如果需要稳定排序，应选择归并排序。

知识点3：快速排序的递归深度

快速排序的递归深度影响空间复杂度：

• 最好情况：O(log n)
• 最坏情况：O(n)
• 通过尾递归优化，可以将栈深度限制在O(log n)

知识点4：主元选择的重要性

主元选择直接影响快速排序的性能：

• 差的主元导致不平衡分区，性能退化
• 好的主元选择策略：随机、三数取中、中位数的中位数
• 实际中，三数取中是最常用的策略

知识点5：快速排序的并行化

快速排序天然适合并行化：

• 分区后可以独立排序左右两部分
• 可以使用多线程或分布式处理
• 关键是负载均衡——避免子问题规模差异过大

常见误区

误区1：快速排序的最坏情况很少发生

虽然随机化后最坏情况概率很低，但在特定场景（如恶意输入、特定数据分布）下仍可能发生。生产环境中应使用内省排序等保证最坏情况的变体。

误区2：快速排序总是最快的排序算法

快速排序在大多数情况下很快，但不是万能的：

• 小规模数据：插入排序更快
• 大量重复元素：三路分区或计数排序更好
• 需要稳定排序：归并排序是唯一选择
• 链表排序：归并排序更合适

误区3：快速排序是原地排序，不需要额外空间

快速排序虽然是原地排序（不需要额外数组），但递归调用需要栈空间。最坏情况下栈空间为O(n)，平均为O(log n)。

误区4：Lomuto分区和Hoare分区没有区别

Hoare分区比Lomuto分区的交换次数少约3倍，实际性能更好。但Lomuto分区更容易理解和实现。

误区5：快速排序不适合链表

虽然标准快速排序确实不适合链表（无法高效随机访问），但可以改造为适合链表的版本。不过，归并排序通常是链表排序的更好选择。

实践应用

应用1：标准库中的快速排序

大多数编程语言的标准库使用快速排序或其变体：

• C++ std::sort：内省排序
• Java Arrays.sort（基本类型）：双主元快速排序
• Python sorted()：Timsort（归并+插入）
• Go sort.Sort：模式检测+快速排序

应用2：外部排序

当数据量超过内存时，使用外部快速排序：

• 将数据分块读入内存排序
• 写入临时文件
• 多路归并临时文件

应用3：数据库查询优化

数据库系统使用快速排序的变体进行排序：

• 外部排序处理大数据集
• 利用索引避免显式排序
• 并行排序加速查询

应用4：分布式排序

在MapReduce等分布式框架中：

• Map阶段：各节点本地排序
• Shuffle阶段：按范围分区
• Reduce阶段：多路归并

应用5：快速选择在工程中的应用

快速排序的分区思想也用于选择问题（找第k大元素）：

• 快速选择算法：期望O(n)时间
• 用于统计、数据分析、Top-K问题

7.11 快速排序的详细性能分析

平均情况的严格分析：

设C(n)为n个元素的期望比较次数。对于随机输入：

C(n) = (n-1) + (1/n) · Σ(k=1 to n) [C(k-1) + C(n-k)]

化简得：C(n) = 2(n-1) + (2/n) · Σ(k=1 to n-1) C(k)

解为：C(n) = 2(n+1)Hₙ - 4n ≈ 2n·ln n ≈ 1.39n·log₂ n

其中Hₙ是第n个调和数。

与归并排序的比较：

• 归并排序比较次数：n·log₂n - n + 1
• 快速排序比较次数：≈ 1.39n·log₂n
• 快速排序比较次数更多，但移动次数更少，缓存更友好

最坏情况的概率分析：

使用三数取中选择主元时，最坏情况（每次分区产生0和n-1的划分）的概率为：

• 三数取中恰好选到最小或最大元素的概率约为3/n
• 连续n次都选到最差的概率约为(3/n)^n，极其微小

7.12 双主元快速排序的深入分析

Yaroslavskiy双主元快速排序：

Java 7+的Arrays.sort对基本类型使用此算法。

分区策略：

• 选择两个主元p和q（p ≤ q）
• 将数组分为三部分：< p，在[p,q]之间，> q
• 递归排序三部分

优势：

• 比较次数减少约5-10%
• 更好地利用现代CPU的分支预测
• 对大量重复元素表现更好

7.13 快速排序的工程优化实践

模式检测：

现代排序实现会检测数据的特征并选择最优策略：

• 已排序/逆序：检测后直接返回或反转
• 少量唯一值：切换到计数排序
• 小规模：切换到插入排序
• 一般情况：使用快速排序

分支预测优化：

• 避免在循环中使用难以预测的条件分支
• 使用无分支代码（如条件移动指令）
• 将数据按主元预分区，减少分支

SIMD向量化：

某些快速排序实现利用SIMD指令并行比较多个元素，进一步提升性能。

7.14 快速排序与其他排序的混合策略

Timsort（Python、Java对象排序）：

• 检测自然有序段（run）
• 归并排序框架
• 小段使用插入排序
• 利用数据的已有顺序

pdqsort（Pattern-Defeating Quicksort）：

• 检测不利模式（如大量重复、管风琴模式）
• 自动切换到堆排序或特殊处理
• 最坏情况O(n log n)

Rust的sort_unstable：

• 基于pdqsort
• 不稳定但更快
• 自动处理各种不利输入

本章小结

本章深入介绍了快速排序算法。我们学习了：

基本思想：分治策略，通过分区将数组分为两部分，递归排序。无需合并步骤。

分区算法：Lomuto分区（简单）和Hoare分区（高效），以及三数取中等主元选择策略。

性能分析：最坏O(n²)，最好和平均O(n log n)。平均比较次数≈1.39n·log₂n。缓存友好性使其在实践中表现优异。

优化技术：随机化、三数取中、小数组切换插入排序、尾递归优化、三路分区。

变体算法：内省排序（保证O(n log n)）、双主元快速排序（减少比较）、三路分区（处理重复元素）。

工程实践：模式检测、分支预测优化、SIMD向量化、与其他排序的混合策略。

实际应用：标准库实现（C++、Java、Go、Rust）、外部排序、分布式排序等。

快速排序是算法设计与工程的完美结合。它不仅在理论上优雅，在实践中也表现出色。理解快速排序的原理和优化技术，对于编写高效的排序代码至关重要。

关键术语

思考题

分析当输入数组所有元素都相同时，标准快速排序和三路分区快速排序的性能差异。

设计一个快速排序的变体，使其在链表上也能高效工作。

证明：使用三数取中选择主元时，快速排序的最坏情况仍然是O(n²)，但发生的概率大大降低。

实现双主元快速排序，并与标准快速排序进行性能比较。