Quicksort 算法概述

1. 引言

Quicksort 是一种经典的分治排序算法，广泛应用于各种编程语言和系统中。它的核心思想是通过“划分”（Partition）将一个数组分成两个子数组，然后递归地对这两个子数组进行排序。

由 Tony Hoare 于 1961 年提出，Quicksort 的平均时间复杂度为 O(n log n)，在实际应用中效率很高，尤其适合大规模数据排序。

本文将带你了解 Quicksort 的基本原理、实现方式、常见优化策略以及性能分析。

---

2. 算法基本要求

Quicksort 的核心依赖于一个比较操作：我们只需要能够判断一个元素是否严格小于另一个元素。不需要判断相等，只要“小于”操作是稳定的即可。

✅ 例如：

• 对整数来说，比较操作是自然的；
• 对字符串来说，可能要考虑大小写或 Unicode 排序规则。

⚠️ 注意：比较操作的稳定性非常重要，否则可能导致排序结果错误。

---

3. 二叉树排序与 Quicksort 的关系

Quicksort 可以看作是二叉树排序（Binary Tree Sort）的优化版本。传统的二叉树排序通过构建一个平衡二叉树来排序元素，但空间开销大。

Quicksort 在原地进行排序，避免了构建额外数据结构的开销，因此更高效。

3.1 示例说明

以数组 [3, 7, 8, 5, 2, 1, 9, 5, 4] 为例：

1. 选择 3 为 pivot

   • 左子数组：[2, 1]
   • 右子数组：[7, 8, 5, 9, 5, 4]

2. 递归处理子数组：

   • 左子数组：选 2 为 pivot → [1] 和 []
   • 右子数组：选 7 为 pivot → [5, 5, 4] 和 [8, 9]

最终排序完成，共 5 次递归划分。

⚠️ 缺点：构建树结构需要额外内存，空间效率低。

---

4. Quicksort 核心思想

Quicksort 的核心是“划分”操作（Partition），通过选择一个 pivot 元素，将数组划分为两个部分：

• 左边：所有元素 < pivot
• 右边：所有元素 ≥ pivot

然后递归对左右两部分进行同样的操作。

三步走策略：

1. ✅ 选择 pivot：可以是任意元素（如首元素、尾元素、中间元素或三数取中）
2. ✅ 划分数组：将小于 pivot 的移到左边，大于等于的移到右边
3. ✅ 递归处理左右子数组

---

5. 示例演示

我们以数组 [3, 7, 8, 5, 2, 1, 9, 5, 4] 为例，演示 Quicksort 的执行过程：

1. 选 5 为 pivot，划分后：

   • 左：[3, 2, 1, 4]
   • 右：[7, 8, 9, 5]

2. 左子数组选 2 为 pivot：

   • 左：[1]
   • 右：[3]

3. 右子数组选 10 为 pivot（无实际元素）：

   • 左：[7, 8, 9, 5]
   • 右：[]

继续递归直到所有子数组长度为 1，排序完成。

---

6. Quicksort 实现方式

Quicksort 有多种实现方式，主要区别在于 pivot 的选择 和 划分策略。

6.1 Lomuto 划分

Lomuto 划分方法由 Nico Lomuto 提出，其特点是：

• 从左向右遍历数组
• 使用一个“滑动索引”标记当前 pivot 的位置

伪代码示例：

fun quicksort(input : T[], low : int, high : int) 
    if (low < high) 
        p := partition(input, low, high) 
        quicksort(input, low, p - 1) 
        quicksort(input, p + 1, high)

fun partition(input: T[], low: int, high: int) : int
    pivot := input[high]
    partitionIndex := low
    for j from low to (high - 1)
        if (input[j] < pivot) 
            swap(input[partitionIndex], input[j])
            partitionIndex += 1
    swap(input[partitionIndex], input[high])
    return partitionIndex

示例执行过程：

输入: [3,7,8,5,2,1,9,5,4]，low=0, high=8
pivot = 4
partitionIndex = 0

遍历过程：
- j=0: 3 < 4 → swap(0,0) → partitionIndex=1
- j=1: 7 ≥ 4 → skip
- j=2: 8 ≥ 4 → skip
- j=3: 5 ≥ 4 → skip
- j=4: 7 ≥ 4 → skip
- j=5: 2 < 4 → swap(1,5) → partitionIndex=2
- j=6: 9 ≥ 4 → skip
- j=7: 5 ≥ 4 → skip

最后 swap(2,8) → array = [3,2,1,4,7,8,9,5,5]
返回 partitionIndex = 3

总共进行了 3 次交换，划分索引为 3。

---

6.2 Hoare 划分

Hoare 划分由 Tony Hoare 提出，其特点是：

• 从数组两端向中间遍历
• 更少的交换次数，但逻辑稍复杂

伪代码示例：

fun quicksort(input : T[], low : int, high : int) 
    if (low < high) 
        p := partition(input, low, high) 
        quicksort(input, low, p) 
        quicksort(input, p + 1, high)

fun partition(input : T[], low: int, high: int) : int
    pivotPoint := (low + high) / 2
    pivot := input[pivotPoint]
    i := low - 1
    j := high + 1
    while true
        do i += 1 while input[i] < pivot
        do j -= 1 while input[j] > pivot
        if i >= j return j
        swap(input[i], input[j])

示例执行过程：

输入: [3,7,8,5,2,1,9,5,4]，low=0, high=8
pivot = 2

遍历并交换：
i=0, j=8 → input[0]=3 ≥ 2; input[8]=4 > 2 → j=7
input[7]=5 > 2 → j=6
input[6]=9 > 2 → j=5
input[5]=1 < 2 → i=0, j=5 → swap(0,5) → array = [1,7,8,5,2,3,9,5,4]

i=1, j=5 → input[1]=7 ≥ 2; input[5]=3 ≥ 2 → swap(1,5) → array = [1,3,8,5,2,7,9,5,4]

继续遍历，最终返回 j=1

整个过程仅进行了 2 次交换，效率更高。

---

7. 算法优化策略

7.1 Pivot 选择优化

选择不当的 pivot 会导致性能下降。例如：

• 数组已有序 → 最坏情况 O(n²)

常见优化方法：三数取中（Median of Three）

mid := (low + high) / 2
if (input[mid] < input[low]) swap(input[mid], input[low])
if (input[high] < input[low]) swap(input[high], input[low])
if (input[mid] < input[high]) swap(input[mid], input[high])

这样可以显著减少最坏情况的发生。

7.2 处理重复元素

当数组中存在大量重复元素时，Quicksort 的效率会下降。可以通过扩展划分函数，返回一个区间而不是单个 pivot 索引，跳过所有等于 pivot 的元素。

修改后的递归结构：

fun quicksort(input : T[], low : int, high : int) 
    if (low < high) 
        (left, right) := partition(input, low, high) 
        quicksort(input, low, left - 1) 
        quicksort(input, right + 1, high)

---

8. 性能分析

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
Quicksort	O(n log n)	O(n²)	O(log n)	❌ 否

关键点：

• ✅ 平均性能优异，适合大规模数据
• ⚠️ 最坏情况退化为 O(n²)，需注意 pivot 选择
• ✅ Hoare 划分比 Lomuto 更高效（交换次数更少）
• ✅ 使用三数取中优化可显著提升性能

---

9. 小结

Quicksort 是一种高效且广泛应用的排序算法，尤其适合原地排序。它通过划分操作将数组分为两部分，然后递归处理，具有 O(n log n) 的平均时间复杂度。

关键点总结如下：

✅ 核心在于“划分”操作
✅ pivot 的选择对性能影响巨大
✅ Hoare 划分比 Lomuto 更高效
✅ 需要处理重复元素和最坏情况
✅ 三数取中是有效的优化策略

掌握 Quicksort 不仅有助于理解分治思想，还能在实际开发中优化排序性能。