快速排序算法 - 5种分区方案完全指南

概述

快速排序是最高效、应用最广泛的排序算法之一。它采用分治策略：选择一个基准元素，将数组分区使较小的元素在左边、较大的在右边，然后递归排序各个分区。

虽然基本思想很简单，但选择基准和分区的方式对性能影响很大。本文探讨5种流行的变体，每种都解决特定问题或针对不同场景进行优化。

⏱️ 时间复杂度

情况	复杂度
平均	O(n log n)
最好	O(n log n)
最坏	O(n²) — 基准选择不当

💾 空间复杂度

O(log n) — 递归调用栈

方案对比

变体	核心思想	平均/最坏	重复元素	有序输入	适用场景
Lomuto	单指针，末元素为基准	O(n log n) / O(n²)	⚠️ 差	⚠️ 差	教学、简单场景
Hoare	双指针从两端开始	O(n log n) / O(n²)	✓ 较好	✓ 一般	通用场景
三路分区	三个区域：`<`、`=`、`>`	O(n log n) / O(n²)	✅ 优秀	✓ 良好	大量重复值
三数取中	取首/中/末的中位数	O(n log n) / O(n²)*	✓ 良好	✅ 优秀	有序/逆序输入
双轴快排	双基准，三分区	O(n log n) / O(n²)	✓ 良好	✓ 良好	JDK的 `Arrays.sort()`

* 最坏情况发生概率大大降低

1. Lomuto 分区

教科书标准的分区方案

💡 工作原理

Lomuto 分区使用最后一个元素作为基准，维护一个指针 i 来跟踪小于基准的元素和大于等于基准的元素之间的边界。

📝 算法步骤

1. pivot ← array[right]
2. i ← left - 1  // 较小元素的边界
3. FOR j FROM left TO right-1:
   └─ IF array[j] < pivot:
        i++
        SWAP array[i] ↔ array[j]
4. SWAP array[i+1] ↔ array[right]  // 放置基准
5. RETURN i+1  // 基准的最终位置

💻 实现代码

✅ 解决的问题

提供一个简单直观、易于理解的分区方案，非常适合教学和简单实现。

⚠️ 缺点

当数组有大量重复值时，Lomuto 会退化到 O(n²)，因为相等的元素都会分到一侧，造成不平衡的分区。

🎮 交互式可视化

观察指针 i 如何在 j 扫描数组时扩展”小于基准”区域。

Speed:

1/0

React Flow

2. Hoare 分区

Tony Hoare 发明的原始快速排序分区

💡 工作原理

Hoare 分区使用两个指针从数组两端开始。左指针找到 ≥ 基准的元素，右指针找到 ≤ 基准的元素，然后交换。如此反复直到指针交叉。

📝 算法步骤

1. pivot ← array[left]
2. i ← left - 1,  j ← right + 1
3. LOOP:
   └─ MOVE i → until array[i] ≥ pivot
   └─ MOVE j ← until array[j] ≤ pivot
   └─ IF i ≥ j: BREAK, RETURN j
   └─ SWAP array[i] ↔ array[j]
4. RETURN j  // 分区点

💻 实现代码

✅ 解决的问题

平均比 Lomuto 减少约 3 倍的交换次数。双指针方式更高效，因为元素会自然地向正确的一侧移动。

🔄 与 Lomuto 的关键区别

分区后基准不会在固定位置。相反，我们得到一个分区点 j，j 左边的元素 ≤ 基准，j+1 右边的元素 ≥ 基准。

🎮 交互式可视化

观察两个指针 i 和 j 从两端收敛，交换位置不对的元素。

Speed:

1/0

React Flow

3. 三路分区（荷兰国旗）

处理重复元素的荷兰国旗算法

💡 工作原理

三路分区将数组分成三个区域：

小于基准的元素
等于基准的元素
大于基准的元素

这也被称为**荷兰国旗（DNF）**算法，以 Dijkstra 解决按荷兰国旗三种颜色排序的方案命名。

📝 算法步骤

1. lt ← left,  i ← left + 1,  gt ← right
2. pivot ← array[left]
3. WHILE i ≤ gt:
   ├─ IF array[i] < pivot:
   │    SWAP array[lt] ↔ array[i], lt++, i++
   ├─ ELIF array[i] > pivot:
   │    SWAP array[i] ↔ array[gt], gt--
   └─ ELSE: i++
4. RECURSE on [left, lt-1] and [gt+1, right]

💻 实现代码

✅ 解决的问题

当所有元素相等时实现 O(n) 时间复杂度！通过将重复元素聚集在一起，避免对相同值的区域递归，非常适合有大量重复值的数组。

🇳🇱 为什么叫”荷兰国旗”？

Dijkstra 提出了在线性时间、常数空间内对三个不同值的数组排序的问题（就像荷兰国旗的 🔴 红、⚪ 白、🔵 蓝三条纹）。这个分区方案就是解决方案，将值视为 <基准、=基准、>基准。

🎮 交互式可视化

观察 lt、i 和 gt 指针如何在元素分类时维护三个不同区域。

Speed:

1/0

React Flow

4. 三数取中

智能选择基准以避免最坏情况

💡 工作原理

不是盲目选择第一个或最后一个元素作为基准（这会导致有序数组的 O(n²)），三数取中检查第一个、中间和最后一个元素，选择中位值作为基准。

📝 算法步骤

1. COMPARE array[left], array[mid], array[right]
2. SORT these three elements in place
3. pivot ← array[mid]  // 中位数
4. PROCEED with standard partitioning

💻 实现代码

✅ 解决的问题

有序或近乎有序的数组是基本快速排序的最坏情况。三数取中大大降低了选择极端基准的概率，确保更平衡的分区。

🏭 实际应用

这种技术被许多标准库实现使用（如 C++ 的 std::sort），并结合其他优化。

🎮 交互式可视化

观察算法如何首先比较三个候选值（首、中、末）来找到中位数，然后再分区。

Speed:

1/0

React Flow

5. 双轴快排

JDK Arrays.sort() 使用的双基准算法

💡 工作原理

双轴快速排序使用两个基准 (P1 ≤ P2) 将数组分成三个区域：

< P1 的元素 (左区域)
P1 和 P2 之间的元素 (中间区域)
> P2 的元素 (右区域)

这是由 Vladimir Yaroslavskiy 发明的，被 Java 的 Arrays.sort() 用于原始类型。

📝 算法步骤

1. ENSURE array[left] ≤ array[right]; else SWAP
2. P1 ← array[left],  P2 ← array[right]
3. lt ← left + 1,  k ← left + 1,  gt ← right - 1
4. WHILE k ≤ gt:
   ├─ IF array[k] < P1: SWAP to left, lt++, k++
   ├─ ELIF array[k] > P2: SWAP to right, gt--
   └─ ELSE: k++  // 中间区域
5. PLACE pivots in final positions
6. RECURSE on three partitions

💻 实现代码

✅ 解决的问题

双轴快速排序具有更好的缓存性能，因为平均每个元素的内存访问次数更少。研究表明，实践中它比单轴快速排序减少约 10% 的比较次数。

☕ 为什么 Java 使用它

从 Java 7 开始，Arrays.sort(int[]) 对原始类型使用双轴快速排序。结合小子数组的插入排序和避免最坏情况的自省机制，它提供了出色的实际性能。

🎮 交互式可视化

注意两个基准值 (P1 和 P2) 如何创建三个不同区域，导致三次递归调用而不是两次。

Speed:

1/0

React Flow

总结

每种快速排序变体都解决特定的挑战：

变体	最适合	权衡
Lomuto	学习和教学	处理重复值差
Hoare	通用场景	更少交换，经典效率
三路分区	重复值多的数据	全等时 O(n)！
三数取中	有序/逆序输入	平衡分区
双轴快排	现代应用	缓存友好，JDK 使用

🔧 生产级实现

实践中，生产级排序实现会组合多种技术：

Java Arrays.sort() — 双轴 + 插入排序 + 自省
C++ std::sort() — 三数取中 + 插入排序 + 堆排序回退
Python sorted() — Timsort（归并排序 + 插入排序混合）

💡 关键要点：理解这些变体让你能够根据特定用例和数据特征选择正确的方法。