颜色分类荷兰国旗问题：三指针原地排序一次扫描详解

颜色分类这道题，刷过算法题的朋友应该都不陌生，一般叫它荷兰国旗问题。题目本身很直白：一个整数数组里只有 0、1、2 三种值，分别代表红、白、蓝，要你原地排序，让所有 0 在前面，所有 1 在中间，所有 2 在后面。限制条件有两个：一趟扫描完成，辅助空间只能用常数级。我第一次做这题的时候觉得很简单，结果一写就卡在边界和指针移动上，尤其是遇到 2 的时候，交换完之后指针到底要不要往前走，每次都要重新推一遍。后来把循环不变量彻底想清楚，才发现它是理解快速排序三路分区的最佳跳板，很多数组分区相关的题都会因此顺手不少。

如果你刚接触这道题，一时没头绪很正常。下面我就把题目拆开，从暴力思路讲到三指针方案，再把代码、边界、调试技巧一次讲清楚。你不需要多深的算法基础，只要熟悉数组遍历和交换操作，就能自己复现并验证。

1. 问题拆解：荷兰国旗到底想考什么

1.1 题目描述与关键限制

原题描述可以概括成这样：给定一个长度为 n 的数组 nums，里面只包含数字 0、1、2，分别代表红色、白色、蓝色，要求原地排序，让相同颜色的元素相邻，并且按红、白、蓝的顺序排列。换句话说，排序完成后数组前段全是 0，中段全是 1，后段全是 2，每个数字内部的相对顺序没有额外要求，不需要稳定排序，只要求分组正确。

真正让这道题变得有嚼劲的，是“一趟扫描完成”和“空间复杂度 O(1)”这两个限制。如果没注意到“一趟扫描”，你很自然地会想到先统计 0、1、2 的出现次数，再重新填充数组。这也是很多初学者的第一反应。但题目明确要求只能遍历一次，还不能用额外数组，这就把常规的计数排序方案挡在了门外，逼着你直接在数组内部通过指针划分区间。

这个限制并不是刻意刁难人。实际工程里经常会出现“数据只有几类，内存又有限，希望一次遍历就把数据归拢到连续区间”的场景，比如把日志按低、中、高优先级原地整理成三段，或者把一批只有三个状态的对象分组处理。荷兰国旗问题的思路，在这种场景里可以直接迁移。

1.2 为什么计数排序不是最优解

计数法写起来非常轻松：第一遍扫描统计 0 的个数、1 的个数、2 的个数，第二遍按顺序把数组重新填好。时间复杂度 O(n)，空间复杂度只用三个变量，也是 O(1)。单看时空复杂度，它甚至优于许多排序算法，所以刚看到题目的人最容易写这种答案。

问题就出在“两趟”上。题目要求的是“一趟扫描完成”，计数法虽然时空达标，但遍历次数明显不符合要求。如果你在面试现场，建议先口述计数法方案，证明自己有最基础的解题能力，然后立刻补充一句“但题目要求一趟扫描，所以我们要用三指针做原地分区”，这样会显得思路灵活且有层次。

换个角度想，为什么出题人执着于“一趟扫描”？因为它想考察“同时维护多个边界”的能力。计数法把“分类”和“整理”拆成了两件事，三指针方案则把这两件事合并成一次扫描。在数据量极大、只能顺序读一遍的场景里，这种边读边整理的思路更贴近流式处理，实用性确实更强。

1.3 荷兰国旗问题的本质

这道题叫荷兰国旗问题，是因为荷兰国旗的颜色布局就是红、白、蓝三条横带。把数组想象成一条旗面，我们要做的事就是把它切成三段：红色段、白色段、蓝色段。这个“切三刀”的过程，本质上是计算机科学里的三路划分问题。

三路划分的目标不是把一个序列排成严格递增或递减，而是按某个基准值把所有元素分成三类：小于基准值的、等于基准值的、大于基准值的。在颜色分类这题里，0 可以看作“小于基准”，1 可以看作“等于基准”，2 可以看作“大于基准”，基准就是 1。标准快速排序中的 partition 操作通常只分两路，遇到大量重复元素时会退化；而三路划分能很好地缓解这个问题。

所以不要只把这道题当成一道简单题刷过去。它背后的核心思想是“分组、分块、维护边界”。理解了这些指针关系，后面再看快速排序变体、看一些数据分区逻辑，都会轻车熟路。

2. 三指针方案：三个指针之间的默契

2.1 双指针的局限

如果数组里只有两种数字，比如只有 0 和 1，那双指针很轻松就能解决：一个指针从前往后找 1，一个指针从后往前找 0，找到就交换，一趟下来两边各自归位。这种二分法本质上只维护两个区间：0 区和 1 区。

但颜色分类有三种数字，问题从“二分”变成了“三分”。如果继续用双指针，你会发现很难同时维护三个连续区间。你可能想：先用一个指针扫描，遇到 0 往左扔，遇到 2 往右扔，剩下的自然就是 1。这个方向是对的，但“往左扔”和“往右扔”需要两个额外的指针记录边界，分别指向下一个 0 应该放的位置和下一个 2 应该放的位置，同时你还必须有一个遍历指针。三个指针一个都不能少，这件事才能办利索。

这也是我早期踩过的一个坑：总觉得双指针也勉强算一趟扫描，于是试图只用两个指针强行完成三分类，结果写着写着就卡在“遇到 1 不知道往哪里放”上。后来才意识到，三类互斥数据至少需要三个边界指针：左边界、右边界、当前扫描位置。想明白这一点，核心思路其实已经拿下了。

2.2 循环不变量：三个区间的定义

写指针类题目最有力的工具是循环不变量，也就是在循环的每一轮开始之前、进行之中、结束之后，都保证某些区间划分始终成立。对于颜色分类，我习惯这样定义：

• 从数组开头到 left 之前，即索引区间 [0, left)，所有元素都是 0；
• 从 left 到 cur 之前，即区间 [left, cur)，所有元素都是 1；
• 从 cur 到 right，即区间 [cur, right]，是尚未扫描的区域；
• 从 right 之后到数组末尾，即区间 (right, n-1]，所有元素都是 2。

初始状态下，left = 0，cur = 0，right = n - 1。此时 [0, left) 和 [left, cur) 都为空区间，未扫描区域是整个数组，(right, n-1] 也为空，不变量自然成立。

循环的结束条件是 cur > right，也就是未扫描区域为空。此时所有元素都已经被分到三个区间中，而这三个区间在位置上天然满足 0 在最前、1 在中间、2 在最后，所以数组已经排好序。写代码前先在纸上把这条不变量画出来，比死记代码有用得多。

2.3 三种情况的交换细节

开始扫描后，我们根据 nums[cur] 的值分三种情况处理。

如果 nums[cur] 等于 0，说明它应该进入左区间。把它和 nums[left] 交换，然后 left++、cur++。这里经常有人问：为什么 cur 也要跟着加？因为交换后 cur 位置拿到的是原来 left 位置的值。根据不变量，[left, cur) 之前全是 1，left 这个位置要么是 1，要么就是当前位置本身，反正不可能是 2。所以交换之后，cur 可以放心往前走。

如果 nums[cur] 等于 1，说明它本来就处在正确的中间区域，直接 cur++ 继续扫描。

如果 nums[cur] 等于 2，说明它应该进入右区间。把它和 nums[right] 交换，然后 right--。注意，cur 千万不能加！因为 right 位置是未扫描区域的最后一个元素，我们并不知道它是什么。交换后 nums[cur] 变成从右边换过来的未知值，可能是 0、1、2 中的任意一个。如果这时贸然 cur++，就会跳过一个还没处理的元素，排序立即出错。

“遇到 2 时 cur 不移动”是整个算法最关键的细节，也是多数人唯一会写错的地方。记住一句话：左边换回来的值，我们已经知道它的身份；右边换回来的值，身份未知，必须留在原地重新判断。

3. 代码实现与验证

3.1 完整代码示例

用 Java 写，结构最清楚：

public void sortColors(int[] nums) { if (nums == null || nums.length <= 1) { return; } int left = 0; int cur = 0; int right = nums.length - 1; while (cur <= right) { if (nums[cur] == 0) { swap(nums, left, cur); left++; cur++; } else if (nums[cur] == 1) { cur++; } else { swap(nums, cur, right); right--; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

Python 版本更简短：

def sort_colors(nums: List[int]) -> None: left, cur, right = 0, 0, len(nums) - 1 while cur <= right: if nums[cur] == 0: nums[left], nums[cur] = nums[cur], nums[left] left += 1 cur += 1 elif nums[cur] == 1: cur += 1 else: nums[cur], nums[right] = nums[right], nums[cur] right -= 1

C++ 版本逻辑完全一致：

void sortColors(vector<int>& nums) { int left = 0, cur = 0, right = nums.size() - 1; while (cur <= right) { if (nums[cur] == 0) { swap(nums[left++], nums[cur++]); } else if (nums[cur] == 1) { cur++; } else { swap(nums[cur], nums[right--]); } } }

C++ 里swap(nums[left++], nums[cur++])是先交换再移动指针，写起来很紧凑，但新手容易看花眼，建议初期还是拆开写。代码本身不长，难的是理解每一步的移动原因。

3.2 手推一个标准测试用例

拿一个常见的输入做完整推演：nums = [2, 0, 2, 1, 1, 0]，长度 6。

初始：left = 0，cur = 0，right = 5。

第一轮：nums[0] = 2，进入 2 分支。交换 nums[0] 和 nums[5]，数组变成 [0, 0, 2, 1, 1, 2]，right 变为 4，cur 仍然为 0。

第二轮：nums[0] = 0，进入 0 分支。交换 nums[0] 和 nums[0]，数组不变，left 变为 1，cur 变为 1。

第三轮：nums[1] = 0，进入 0 分支。交换 nums[1] 和 nums[1]，数组不变，left 变为 2，cur 变为 2。

第四轮：nums[2] = 2，进入 2 分支。交换 nums[2] 和 nums[4]，数组变成 [0, 0, 1, 1, 2, 2]，right 变为 3，cur 仍然为 2。

第五轮：nums[2] = 1，进入 1 分支，cur 变为 3。

第六轮：nums[3] = 1，进入 1 分支，cur 变为 4。

此刻 cur = 4，right = 3，循环条件 cur <= right 不成立，退出循环。最终数组是 [0, 0, 1, 1, 2, 2]，正确。

这个例子没有出现“从右边换过来一个 0，然后 cur 原地等待再处理”的经典回合。你可以自己再拿 [1, 0, 2, 1, 2, 0] 推一遍，重点观察遇到 2 时 cur 保持不动的那一步，感受一下为什么要留到下一轮重新判断。

3.3 复杂度和正确性证明

时间复杂度方面，每一轮循环有三种结果：要么 cur 右移，要么 right 左移，要么 cur 和 left 一起右移。无论哪种情况，未处理的区间都在缩小，所以循环次数不会超过数组长度 n，时间复杂度是 O(n)。空间上只用了几个整型变量，没有额外数组，空间复杂度是 O(1)，完全满足题目要求。

正确性可以用循环不变量严格证明。我们已经在 2.2 里定义了四个区间的状态。初始状态成立；每一轮循环，0 分支把 0 放到正确位置并扩大左边界，1 分支直接越过一个 1，2 分支把 2 放到正确位置并缩小右边界，四个区间始终满足不变量；循环结束时未扫描区间为空，三个分段自然就绪。这就是最清晰也最严谨的证明。

如果不想做形式化证明，可以直接写脚本随机生成只包含 0、1、2 的数组，跑完后再用语言自带的排序结果比对。我习惯在本地跑十万条随机数据，几秒钟就能得出验证结论，比自己肉眼盯边界可靠得多。

4. 常见错误与调试技巧

4.1 遇到 2 后错误地移动 cur

这是排名第一的坑。很多人在处理 nums[cur] == 2 时，写完 right-- 之后顺手又写 cur++，理由是“反正当前这个 2 已经放到右边了”。问题在于，你只是把 2 放到了右边，但从右边换过来的元素是什么，你完全没有看过。如果它是个 0，却因为 cur 继续往后走被跳过，最终数组里就会出现一个没归位的 0。

看一个最小反例：数组 [1, 2, 0]。如果错误地写成 2 分支里也 cur++，初始 left=0，cur=0，right=2。第一轮 nums[0] = 1，cur 变为 1。第二轮 nums[1] = 2，交换 nums[1] 和 nums[2]，数组变成 [1, 0, 2]，right 变为 1，cur 被错误地加 1 变成 2。此时 cur > right，循环结束，得到错误的 [1, 0, 2]。如果保留 cur 不动，第二轮交换后 cur 仍是 1，nums[1] 变成 0，下一轮会触发 0 分支，最终得到 [0, 1, 2]。

明白这个例子后，你基本不会再在 2 分支里加 cur++。写完这类指针移动代码后，第一件就是用包含“2 后面跟着 0”的输入做验证，比如 [2, 0, 1]。

4.2 while 条件的左右边界写法

while 条件用 cur <= right 还是 cur < right，取决于 right 的初始化方式。大多数实现把 right 设为 nums.length - 1，这时候必须用 <=，因为 right 指向的元素还没有被扫描。如果 right 那个位置恰好是一个需要处理的 0，而你用了 <，它就会被漏掉，排序结果当然出错。

另一种常见写法是把 right 初始化为 n，循环条件用 cur < right，此时 right 表示右边界开区间，交换时需要改成 --right 再换，也就是先减后用。两种体系都可以，但混用就会出问题。我的经验是固定一种写法：right 初始为 n-1，循环写 while (cur <= right)，分支里统一用 right--。这样最不容易乱。

4.3 边界测试用例清单

写指针题最忌讳只在常规输入上验证。我建议准备一组固定的边界用例，写完代码直接全跑一遍：

其中全 2 这个用例特别有意思。right 初始为 n-1，第一轮交换 nums[0] 和 nums[n-1] 后，right 变成 n-2，cur 仍为 0，由于新换来的还是 2，会继续交换。很多人担心这里会不会死循环，其实每轮 right 都在缩小，最终一定会让 cur > right 退出。亲眼跑一遍，比背一百遍结论都踏实。

4.4 与快速排序三路分区的关系

这里值得一提，因为它可能是刷完这题后最容易被忽略的延伸点。标准快速排序在选择基准值时，通常只把数组分成两段：小于等于基准值的一段和大于基准值的一段。如果数组里大量元素都等于基准值，这些重复元素会在递归中反复出现在不同子问题里，导致性能明显下降。

荷兰国旗问题的三路划分恰好解决了这个痛点。它把数组分成小于、等于、大于三个区域，等于基准值的区域完全不需要再递归。为了实现三路划分，我们需要两个额外指针维护边界，这和颜色分类里的 left、right 是同一回事。如果你已经理解 2 分支中 cur 不动的原则，再看三路快排的 partition 代码，会感觉特别眼熟：同样是维护左右边界，遇到小于基准值就交换到左边界并推进扫描指针，遇到大于基准值就交换到右边界但不推进扫描指针。

可以说，颜色分类就是三路快排分区最纯粹的训练场。这也是我强烈建议把这道题完全吃透的原因。它不是一道孤立小题，而是通往高级排序思想的跳板。

5. 变体与扩展

5.1 只有两种颜色时的简洁解法

如果题目变成只有 0 和 1，或者只有两类数据，就不用三指针了。双指针就能解决：left 从最左边开始找第一个 1，right 从最右边开始找第一个 0，找到就交换，直到两个指针错开。整个过程同样是一趟扫描、常数空间。

双指针的循环不变量是：左边已经全是 0，右边已经全是 1。左侧遇到 0 就 left++，右侧遇到 1 就 right--，左侧遇到 1、右侧遇到 0 时交换，然后两个指针各自向内收。这个思路也可以从三指针代码里退化出来：把所有等于 2 的分支删掉，只保留 0 分支和 1 分支，语义上就变成了二分类。

5.2 如果颜色变多怎么办

最常见的是四色、五色甚至 k 色分类。有人会说，三色用三个指针，四色是不是用四个指针？理论上可以，但实现会越来越复杂。四色时你需要维护左边界、中左边界、中右边界、右边界，指针数量变成四个，交换逻辑也复杂得多，而且每一轮只能把一个元素归到四个区间之一，边界错误概率大幅上升。

更实际的方案是根据限制条件选择。如果 k 很小且不要求一趟扫描，计数排序依然最好写、最稳定；如果 k 很大，直接调稳定快排或归并排序更合理。荷兰国旗问题最精彩的部分，就是“三种分区却能一趟扫描完成”这个巧妙设计，而不是要把所有可能颜色的版本都背下来。遇到多色扩展，我通常会先和需求方确认对“稳定性”和“扫描次数”的具体要求，再决定方案。

5.3 工程场景中的实际应用

实际开发里也会有类似需求。比如某个图像处理 demo 要把像素点按亮度分成暗、中、亮三类，再分别执行不同滤镜；再比如日志系统按级别把 error、warn、info 分段存储。多数时候我们能用额外数组或现成库，但在内存受限、数据需要流式处理的嵌入式环境里，三指针分区就是一种很实用的手段。

我自己的习惯是，遇到“三类互斥数据需要原地整理”的需求，会优先想起荷兰国旗方案。只要把 0、1、2 换成任意三种互斥状态，算法骨架完全不变。三种状态不多不少时，三指针通常都是最高效的方案之一，代码短、思路清晰、性能可预测。

最后分享一点个人体会。我每次重写这道题，都会刻意在纸上先把三个指针的循环不变量画一遍，再动笔写代码。核心口诀就两句：左边换来的值已经知道身份，右边换来的值必须原地再看一眼；遇到 2 时 cur 不前进。如果你第一次写错了，不用气馁，这题错一次反而记得更牢。拿 [2, 0, 1] 这种最小反例手推几遍，理解会非常深刻。真正把这道题吃透之后，再看三路快排、再看各类分区逻辑，你会觉得遍地都是荷兰国旗的影子。