外观
从两次扫描到一次分区：荷兰国旗三路快排避坑实录
问题背景：颜色分类为什么不能只靠排序
LeetCode 第 75 题「颜色分类」要求把只包含 0、1、2 的数组原地整理成 0 在前、1 在中、2 在后。最直接的想法当然是调用排序函数：
python
nums.sort()这行代码能通过结果，却没有体现题目的核心价值。题目通常还会补充两个要求：
- 不能使用标准库排序；
- 尽量只使用常数额外空间，并通过一趟扫描解决。
这正是经典的荷兰国旗问题（Dutch National Flag Problem），也是三路快排（3-way QuickSort）分区思想的基础模型。普通二分快排只把数组分成「小于 pivot」和「大于等于 pivot」两部分；当数组中存在大量与 pivot 相等的元素时，会产生很多重复比较。三路 partition 则把数组划分为三段：
- 小于 pivot；
- 等于 pivot；
- 大于 pivot。
在颜色分类中，pivot 可以看作 1，于是目标天然变成维护三个区域。
方案对比：计数排序、两次双指针与三路分区
方案一：计数后回填
由于数组只有三种值，可以先统计 0、1、2 的出现次数，再按次数覆盖原数组。
python
def sortColors(nums):
count = [0, 0, 0]
# 第一次遍历：统计每种颜色的数量
for x in nums:
count[x] += 1
# 第二次遍历：按数量回填
for i in range(len(nums)):
if i < count[0]:
nums[i] = 0
elif i < count[0] + count[1]:
nums[i] = 1
else:
nums[i] = 2时间复杂度为 O(n)，空间复杂度为 O(1)，代码也稳定。但它需要两次扫描，并且没有维护元素交换过程中的分区关系。面试中如果题目明确要求一趟扫描，这个方案通常不够理想。
方案二：两次移动 0 和 2
也可以先用双指针把所有 0 移到前面，再把所有 2 移到后面。思路容易理解，但扫描次数较多，且第二轮处理时容易破坏第一轮已经确定的边界。
方案三：三路快排 partition
维护三个指针：
left：下一个放置0的位置；right：下一个放置2的位置；i：当前正在检查的元素。
一趟扫描即可完成原地分区，也是本文重点。
循环不变量：先定义规则，再写代码
很多人写双指针题目靠直觉交换，结果在 nums[i] == 2 时反复出错。更可靠的方式是先写清循环不变量：
nums[0:left]全部是0；nums[left:i]全部是1；nums[i:right+1]是尚未检查的区域；nums[right+1:n]全部是2。
初始状态下：
left = 0，0 区域为空；i = 0，尚未开始扫描；right = n - 1，2 区域为空。
扫描规则如下：
nums[i] == 0：与left交换，然后left++、i++；nums[i] == 1：位置正确，只需i++；nums[i] == 2：与right交换，然后right--，但不能立刻i++。
第三点最关键。从右侧换过来的元素还没有检查，可能是 0，也可能还是 2，必须在下一轮继续观察 nums[i]。
实操步骤：可运行的原地颜色分类代码
下面是完整的 Python 实现，包含测试用例和中文注释：
python
def sort_colors(nums):
"""原地将 nums 按 0、1、2 排序，返回 None。"""
left = 0 # 下一个 0 应该放置的位置
right = len(nums) - 1 # 下一个 2 应该放置的位置
i = 0 # 当前扫描位置
# 当 i > right 时，未处理区域为空
while i <= right:
if nums[i] == 0:
# 把 0 换到左侧。nums[left] 只可能是 1，
# 因为真正的 2 早已被换到右侧。
nums[i], nums[left] = nums[left], nums[i]
left += 1
i += 1
elif nums[i] == 1:
# 1 已经位于中间区域，直接继续扫描
i += 1
else:
# 把 2 换到右侧。换过来的 nums[i] 尚未检查，
# 因此这里不能执行 i += 1。
nums[i], nums[right] = nums[right], nums[i]
right -= 1
# 手动测试
if __name__ == "__main__":
test_cases = [
[2, 0, 2, 1, 1, 0],
[2, 0, 1],
[0],
[1, 2, 0],
[2, 2, 1, 1, 0, 0],
]
for case in test_cases:
sort_colors(case)
print(case)输出为：
text
[0, 0, 1, 1, 2, 2]
[0, 1, 2]
[0]
[0, 1, 2]
[0, 0, 1, 1, 2, 2]为什么遇到 0 可以同时移动 i
当 nums[i] == 0 并与 left 交换时，需要判断换回来的值是什么。根据不变量，left 位于中间区域的起点，nums[left:i] 全部是 1。因此只要 left < i，交换到 i 位置的值一定是 1；如果 left == i，交换前后都是当前的 0，随后两个指针一起前进也没有问题。
所以遇到 0 时可以安全地执行 i++。
为什么循环条件是 i 小于等于 right
nums[i:right+1] 表示未检查区域。只要 i <= right，就至少还有一个元素需要判断。当 i > right 时，未处理区域为空，所有元素都已经落入三个确定区域。
如果误写成 i < right，当 i == right 时最后一个元素不会被检查。虽然它可能碰巧正确，但在 [1, 2, 0] 等边界用例中可能得到错误结果。
复杂度分析
- 时间复杂度：
O(n)。i只向右移动，right只向左移动，每个元素最多参与常数次交换与判断，整体扫描次数是线性的。 - 空间复杂度：
O(1)。只使用left、right、i三个指针变量，排序直接在原数组上完成。 - 稳定性：不稳定。交换可能改变相同值元素的相对位置。本题只按颜色分类，不要求稳定排序。
如果把同样的 partition 思想放回快速排序中，pivot 不再固定为 1，而是选择某个基准值 pivot，并把数组划分为 < pivot、= pivot、> pivot 三段。对于重复元素很多的数据，三路快排能显著减少重复递归和重复比较。
避坑总结：三路 partition 的高频错误
1. 遇到 2 后错误地同时执行 i++
常见错误现象：
python
# 错误示例
if nums[i] == 2:
nums[i], nums[right] = nums[right], nums[i]
right -= 1
i += 1当输入为 [2, 0, 1] 时，第一次交换会把末尾的 1 换到位置 0，把 2 换到末尾。如果立刻 i++，位置 0 的 1 虽然最终可能正确，但更复杂的用例中，从右侧换入的 0 会被跳过，导致结果仍出现乱序。
修正方法： 遇到 2 时只执行 right--，下一轮继续检查当前 i。
2. 循环条件误写为 i 小于 right
错误现象： 最后一个未处理元素没有经过判断，某些数组会漏掉一个 0 或 2。例如区间缩小到只剩一个元素时，这个元素仍然属于未检查区域。
修正方法： 使用：
python
while i <= right:
...只要未处理区间不为空，就继续分区。
3. 交换 0 时搞错指针顺序
错误现象： 有人先写 i += 1，再交换，或者交换后忘记移动 left，导致 0 区域边界没有扩展，后续元素可能再次覆盖已经放好的位置。
修正方法： 固定顺序：先交换 i 与 left，再同时移动 left 和 i。
4. 用排序函数掩盖分区训练目标
nums.sort() 在工程代码中当然更简洁，但面试考察的是你能否维护区间不变量、处理指针交换和证明复杂度。建议练习时手写三指针版本，并能解释为什么与右侧交换后不能跳过新元素。
结语
荷兰国旗问题的本质不是给三个数字排序，而是用一次线性扫描维护三个严格区间。只要记住：
left负责扩张 0 区域；i负责扫描未知区域；right负责扩张 2 区域；- 右侧交换后保持
i不动；
就能稳定写出原地、常数空间、O(n) 时间的颜色分类解法。这套分区逻辑也是理解三路快排、重复元素优化和多区间指针问题的重要基础。
免责声明
本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。