有一回我在某家互联网公司面试，二面官在共享屏幕上贴了一道题：给一个只包含 0、1、2 的数组，原地排序，不能申请额外数组，最好只遍历一遍。我第一反应是这题也太“模板”了，心里想着直接Arrays.sort()不就完事了吗？然后看到他补充的限制条件，我意识到这才是重点。后来我才慢慢理解，这道编号 75 的颜色分类题，本质上考的并不是“排序”，而是三向切分，也就是大家俗称的荷兰国旗问题。
这个问题的经典程度，不亚于“反转链表”和“二分查找”。你去看大厂面试题单，前 100 题里几乎都有它；刷题社区的讨论区里，关于这题的高赞评论也往往不是给代码，而是解释“为什么交换 2 之后不能马上往后走”。如果你只是背下了答案，下次面试换个问法，比如“把数组按 0、负数、正数排序”，很可能就僵住了。这篇文章我不想只贴一种解法，而是把这道题从最笨的思路讲到最优解，再把容易踩的坑、变体题、甚至面试表达顺序，都拆开揉碎讲一遍。
1. 第一眼看题：你可能会想到的几种“笨”办法
1.1 直接调用库排序，为什么会被面试官否定
看到数组排序，很多人第一反应是调用内置排序，比如 Python 里sorted()，Java 里Arrays.sort()。这个思路在工程里完全没问题，但在这种题型的场景里，它至少有三层问题：
第一，内置排序是通用排序，没有利用到“数组里只有 0、1、2 三种值”这个强约束。面试官出题不是为了让你展示调库能力，而是想看你能否根据数据特性设计更优的算法。第二，很多内置排序是稳定的归并排序，需要 O(n) 的辅助空间，这与“不能申请额外数组”的约束冲突。即使像 Java 的Arrays.sort()对基本类型使用的是双轴快速排序，空间上勉强算 O(logn) 递归栈空间，但时间上 O(nlogn) 对这个小规模问题来说也显得很浪费。第三，这道题的“题眼”是原地、一次遍历，你要是不往这个方向想，那等于没答到点子上。
1.2 计数排序思路：方向对了，但还是要“两趟”
既然只有 0、1、2 三种值，另一个很自然的想法是计数器：先遍历一遍，分别数出 0、1、2 的个数，然后再遍历一遍，按个数往原数组里填。
这个方案在时间复杂度上是 O(n)，空间复杂度 O(1)，看起来已经很不错了。用代码写就是：
def sort_colors_count(nums): count0 = count1 = count2 = 0 for num in nums: if num == 0: count0 += 1 elif num == 1: count1 += 1 else: count2 += 1 idx = 0 for _ in range(count0): nums[idx] = 0 idx += 1 for _ in range(count1): nums[idx] = 1 idx += 1 for _ in range(count2): nums[idx] = 2这段代码面试时写出来，能拿及格分。但如果你停下来想一想就会发现，它有两个“不够好”的地方：
一是它需要遍历数组两遍，以为“一遍扫描”是这题最核心的考核点。面试官可能会追问：能不能把两趟压缩成一趟？二是计数排序本质上还是“先统计后覆盖”，对“0、1、2”有效，但如果题目改成“数组里有 0 和 1”其实也能用，可一旦改成“k 种颜色”，你就得准备 k 个计数器，扩展性比较差。相比之下，荷兰国旗算法的一遍遍历方案，才是这类题的标准答案。
1.3 本质：排序问题变成了“三区间划分”问题
当数组里只有三类元素时，你真正需要的不是把所有元素“排得细枝末节”，而是把数组切分成三段：左边全是 0，中间全是 1，右边全是 2。这不就是快速排序里的 partition 思想吗？快排里的 partition 是把数组分成“小于 pivot”和“大于等于 pivot”两块，荷兰国旗问题则是把一个数组按 pivot 分成“小于、等于、大于”三块。
一旦完成了这个视角转换，你就抓住了核心：用几个指针维护区间边界，然后一遍扫描，不断把当前元素放进对应的区间里。这就是三向切分，也叫 Dutch National Flag Algorithm，最早由计算机科学家 Dijkstra 提出。
2. 荷兰国旗问题的来源与三向切分的核心思路
2.1 为什么叫“荷兰国旗”：三色条带的类比
荷兰的国旗是三条水平色带，颜色是红、白、蓝。Dijkstra 用它来描述一个问题：给你一堆红白蓝三种颜色的球，乱序排成一行，要求把它们排列成红、白、蓝的顺序，并且只能交换相邻或任意两个球。这个比喻非常形象，后来在算法题里，颜色可能变成 0、1、2，但本质完全一样。
在颜色分类这道题里，0 可以代表红色，1 代表白色，2 代表蓝色。目标就是让数组形成000...111...222的形状。你不用关心每个相同颜色的球之间有什么差别，因为它们是等价的，这也让“稳定性”变得无关紧要。
2.2 三指针的状态定义：左区、中区、右区
荷兰国旗算法通常用三个指针：
left：指向当前已经排好的 0 区域的下一个位置，也就是第一个 1 应该插入的位置；mid：当前扫描指针，从数组头向尾部移动；right：指向当前已排好的 2 区域的前一个位置，也就是从右向左维护的边界。
我们可以定义整个数组在扫描过程中保持这样的不变量：
[0, left)区间内的元素全是 0；[left, mid)区间内的元素全是 1；(right, n-1]区间内的元素全是 2；[mid, right]区间内是还没有检查的“未知区”。
一开始left = 0, mid = 0, right = n-1，整个数组都处于未知区。随着扫描推进，未知区不断缩小，三个已知区间不断扩展，直到mid > right时结束。
这个不变量非常关键。写代码之前，先在纸上把这个不变量画出来，后面所有分支都不用硬背，而是“当前元素属于哪个区间，就把它交换到哪个区间去”。
2.3 核心循环的三种分支：0、1、2 各怎么办
循环里每次看nums[mid]的值，分三种情况处理：
如果
nums[mid] == 0，说明这个元素应该放到左边的 0 区。交换nums[left]和nums[mid]，因为nums[left]目前要么是 1，要么就是nums[mid]自己（当 left 和 mid 重合时）。交换后left++，mid++。为什么mid要加一？因为交换过来的旧nums[left]一定是 1（除非区间为空时交换的是 0 自己），它已经处在正确区域，所以扫描指针可以继续前进。如果
nums[mid] == 1，说明它已经在正确的中区里，不需要交换，直接mid++。如果
nums[mid] == 2，说明它应该放到右边的 2 区。交换nums[mid]和nums[right]，然后right--。注意这里mid不能加一。因为交换过来的nums[right]是一个还没检查过的元素，它可能是 0，可能是 1，也可能是 2。如果盲目地把mid加一，你会跳过一个需要处理的元素，导致结果错误。
这三种分支的逻辑，几乎不需要记：每个指针维护的是“下一个位置”，你只要保证交换后区间边界正确即可。
3. 标准解法：一次遍历 + 三指针的实现细节
3.1 代码实现（Python 与 Java 双版本）
下面给出标准的荷兰国旗算法实现。以 Python 为例：
def sort_colors(nums): left, mid, right = 0, 0, len(nums) - 1 while mid <= right: if nums[mid] == 0: nums[left], nums[mid] = nums[mid], nums[left] left += 1 mid += 1 elif nums[mid] == 1: mid += 1 else: # nums[mid] == 2 nums[mid], nums[right] = nums[right], nums[mid] right -= 1Java 版本也是一样的结构：
public void sortColors(int[] nums) { int left = 0, mid = 0, right = nums.length - 1; while (mid <= right) { if (nums[mid] == 0) { int tmp = nums[left]; nums[left] = nums[mid]; nums[mid] = tmp; left++; mid++; } else if (nums[mid] == 1) { mid++; } else { int tmp = nums[mid]; nums[mid] = nums[right]; nums[right] = tmp; right--; } } }代码看着不长，但里面每一个细节都是经过设计的。比如 Python 里的多重赋值，其实等价于先把右边元组求值再赋值，所以交换逻辑是正确的，但如果你在面试时手写，建议还是用显式的临时变量，避免解释不清。
3.2 为什么循环条件是mid <= right而不是mid < right
这是很多人第一次写会踩的坑。如果写成mid < right，循环结束时mid和right相等，那么nums[mid]这个位置上的元素可能还没有被处理过。
举个例子，数组是[1, 0]。初始mid = 0, right = 1，进入循环。因为nums[0] == 1，所以mid++，此时mid = 1, right = 1。如果你用的是mid < right，循环直接退出，可是nums[1] == 0根本没被移到数组前面，结果当然是错的。
所以条件必须写成mid <= right。当mid == right时，未知区只剩一个元素，仍然需要进入循环体处理。处理完之后，要么mid越过right，要么right左移小于mid，循环自然结束。
3.3 遇到 2 时为什么不能mid++
假设现在mid指向一个 2，它和right位置的元素交换后，mid并不一定就已经处在正确位置。因为旧的nums[right]可能也是个 2，或者是个 0，或者是个 1，它们都需要再次被分类。
你可以用[2, 1, 0]来模拟一下：
初始
left = 0, mid = 0, right = 2。nums[0] == 2，交换nums[0]和nums[2]，得到[0, 1, 2]，right变成 1。这时如果错误地执行
mid++，mid变成 1，交换后nums[1] == 1，mid++变 2，循环判断2 <= 1退出。结果数组是
[0, 1, 2]，看起来碰巧对了。但换一个数组[0, 2, 1, 0]呢？初始
left=0, mid=0, right=3。nums[0] == 0，交换（自交换），left=1, mid=1。nums[1] == 2，交换nums[1]和nums[3]，数组变成[0, 0, 1, 2]，right=2。如果错误地
mid++，则mid=2。nums[2] == 1，mid=3，循环退出，结果正确。
但很多情况下会出错，比如[2, 0, 1]：
- 初始
left=0, mid=0, right=2。 nums[0] == 2，交换nums[0]和nums[2]，数组变成[1, 0, 2]，right=1。- 错误地
mid++，mid=1。 nums[1] == 0，交换nums[0]和nums[1]，数组变成[0, 1, 2]，left=1, mid=2，退出。看起来还是对的。
这类碰巧对的例子很多，但请你试试[0, 2, 1]或者[2, 0, 2, 1]，很容易出现漏处理。也就是说，“对某些输入正确”并不代表逻辑正确。正确做法的关键是：遇到 2 交换后，mid要停留在原地，重新检查交换过来的元素。
4. 常见错误与边界条件的完整排查链路
4.1 错误一：交换后不自增mid导致死循环
反过来，有人记住“交换 2 后不能自增”，结果在交换 0 之后也忘了自增，就会出现死循环。
比如nums = [2, 0, 1]的某个分支，如果在nums[mid] == 0时只做了交换和left++，没有mid++，那么下一次循环还是看同一个位置。这个位置现在放的是从前面的 0 区换过来的旧值，可能是 1，也可能是 0。如果交换过来的是 0，你又把它和nums[left]交换一次，然后left++，但mid没动，这样会导致左边界不断前进，而mid卡在同一个位置，永远处理不完。
这种错误的典型表现是程序陷入死循环。排查方法很简单：在循环体开头打印三个指针和数组状态，如果发现left一直增加而mid保持不变，就能秒懂。
4.2 错误二：把right写成数组长度或n，导致越界
刚写这题的新手，很容易把right初始化为len(nums)，然后循环里直接访问nums[right]。这是一个经典越界错误。因为right应该指向“未知区的右边界”，也就是最后一个未处理元素的下标，所以必须是len(nums) - 1。
还有人在更新right时写成right -= 1却忘了在nums[mid] == 2时才更新，结果导致mid扫描到已经处理好的 2 区域里，把已排好的数据又换乱。记住，right只在遇到 2 并交换后递减，其他情况都不能动。
4.3 错误三：循环结束条件判断错误
只讨论mid < right和mid <= right太抽象，我用一个例子给你完整走一遍排查链路。
假设你写的是while mid < right，输入nums = [1, 0]：
- 初始
left=0, mid=0, right=1。条件成立，进入循环。 nums[0] = 1，于是mid++，mid = 1。- 再次判断条件：
1 < 1不成立，循环退出。 - 输出
[1, 0]，排序失败。
修好之后，把条件改成mid <= right，同样输入：
- 初始
mid=0, right=1，条件成立。 nums[0]=1，mid++，mid=1。- 判断
1 <= 1成立，进入循环。 nums[1]=0，交换nums[left]和nums[mid]，即nums[0]和nums[1]交换，结果[0, 1]；left++，mid++，mid=2。- 判断
2 <= 1失败，结束。结果正确。
4.4 用“哨兵实例”验证边界：长度为 1、全 0、全 2
写完代码之后，一定要用几组特殊输入过一遍，而不是只测普通例子：
[0]：初始left=0, mid=0, right=0，进入循环后nums[0]==0，自交换后left=1, mid=1，退出。结果正确。[2]：nums[0]==2，自交换后right=-1，mid=0，此时0 <= -1不成立，退出。结果还是[2]，正确。[0,0,0]：所有元素都是 0，mid一路自增，left也跟着自增，最终退出，结果不变。[2,2,2]：每次遇到 2 都交换自己和右边界，right递减，mid不变，直到right < mid。但要注意，因为交换的是同一个位置，数组内容不变，最终排序正确。
你把这些用例放在简历背面的草稿纸上，面试时能快速提示自己不要踩边界坑。
5. 复杂度对比：三指针 vs 计数排序 vs 双指针
5.1 时间复杂度与空间复杂度对比表
我自己面过很多候选人，发现大家都懂 O(n) 和 O(1) 的概念，但能把“几趟遍历”说清楚的人不多。这里我给你一个清晰的对比表：
| 解法 | 时间复杂度 | 额外空间 | 遍历趟数 | 是否原地 |
|---|---|---|---|---|
| 内置排序 | O(n log n) | O(logn) 栈空间 | 1 | 是 |
| 计数排序 + 覆盖写回 | O(n) | O(1) | 2 | 是 |
| 双指针（快排 partition 两次） | O(n) | O(1) | 2 | 是 |
| 荷兰国旗三指针 | O(n) | O(1) | 1 | 是 |
严格来说，内置排序在时间上也能过，但它忽略了数据特性。计数排序是一趟数数、一趟填充，空间没问题，但不是“单趟扫描”。荷兰国旗算法的优势在于一遍扫描，同时不借助额外空间。
5.2 为什么“稳定”在本题中不适用
有些问题会问“排序算法是否稳定”，放在颜色分类这道题里，这个问题的答案有点微妙。数组里的 0、1、2 都是相同元素，你根本分辨不出“第一个 0”和“第二个 0”在排序前后的相对位置是否变化。因为没有可辨识的身份信息，“稳定性”这个概念自然失效。
所以面试时如果有人问“这个算法稳定吗”，你可以这样答：对于完全等价的重复元素，谈论稳定性没有实际意义；如果元素本身是带身份信息的对象，仅按颜色属性排序，三向切分交换时可能会破坏稳定性，但我们可以通过额外字段来保留，具体问题具体分析。
5.3 与快速排序三向切分的关联
如果你写过三向切分的快速排序，会发现这段代码非常眼熟。三向切分快排的思路是：选一个 pivot，把数组切分成< pivot、== pivot、> pivot三块，然后只对小于和大于的两部分递归排序。这和荷兰国旗问题的差别只是“颜色固定是 0、1、2”，而快排的 pivot 是动态的。
理解了这层关系，你会明白为什么这道题常被当作“手写快排 partition”的低配备选题。很多候选人能背出“三向切分”这个名词，但说不出它和颜色分类的关系。面试时如果你能主动把两者关联起来，会是一个很加分的信号。
6. 变体问题与举一反三：从颜色分类到更广义的划分
6.1 变体一：把数组按负数、零、正数排序
这是很常见的改造题。给定一个数组，要求原地把头处理成负数、中间零、后面正数，不允许使用额外数组。你只需要把荷兰国旗算法的判断条件换成：
def sort_signs(nums): left, mid, right = 0, 0, len(nums) - 1 while mid <= right: if nums[mid] < 0: nums[left], nums[mid] = nums[mid], nums[left] left += 1 mid += 1 elif nums[mid] == 0: mid += 1 else: nums[mid], nums[right] = nums[right], nums[mid] right -= 1逻辑完全一样，只是把“等于 0”变成“等于 0”，把“等于 2”变成“大于 0”。这道题的实质是三向划分，而不是“颜色”本身。
6.2 变体二：给定一个 pivot，把数组分成< pivot、== pivot、> pivot三块
这其实就是三向切分快排的 partition 核心。很多教材里写的partition3就是荷兰国旗算法的泛化版：
def partition3(nums, pivot): left, mid, right = 0, 0, len(nums) - 1 while mid <= right: if nums[mid] < pivot: nums[left], nums[mid] = nums[mid], nums[left] left += 1 mid += 1 elif nums[mid] == pivot: mid += 1 else: nums[mid], nums[right] = nums[right], nums[mid] right -= 1这个方法在经典的三向快速排序中用来处理大量重复键，能让快排在数据重复较多时也保持 O(nlogn) 的最优复杂度。
6.3 变体三：数组只有 0 和 1 时怎么处理
这也是常见的“抗干扰题”。如果数组只有 0 和 1，你只需要双指针：一个left指向 0 区边界，一个right指向 1 区边界，遇到 0 就放到左边界，遇到 1 就放到右边界。代码可以简化成荷兰国旗算法的一个子集，少处理一种颜色。
但面试时我建议你直接说出荷兰国旗算法的完整版本，再说“如果只有 0 和 1，用两个指针就够了”，这样能展示你是从上位概念往下兼容，而不是只会背模板。
7. 面试中怎么答这题：从思路到收尾的表达顺序
7.1 先给结论：一次遍历和两趟的区别
面试官问你思路时，不要上来写代码。先用两句话给结论：
“我可以用三个指针维护三个区域：左边是 0，中间是 1，右边是 2。扫描一遍，遇到 0 交换到左边，遇到 1 直接跳过，遇到 2 交换到右边。这样可以做到时间 O(n)、空间 O(1)、单趟遍历。”
然后画一下不变量图，甚至用一个小例子手动模拟两步。这个过程不仅是在给自己理思路，也是给面试官传递信号：你理解状态边界。
7.2 写代码时的手势与边界自测
写代码时，我习惯在注释里写出三个区间的定义：
# [0, left): zeros # [left, mid): ones # (right, end): twos # [mid, right]: unknown每写一行，都对照一下这个区间定义，避免逻辑混乱。
写完代码以后，立刻用两个边界样例自测：[0]和[2]。然后再用一个中等例子[2,0,2,1,1,0]手动跑一遍，保证left/mid/right的变化符合不变量。面试官不会因为你多写一个测试用例而觉得啰嗦，反而会觉得你工程素养在线。
7.3 更进阶的回答：扩展到任意 k 种元素
如果面试官追问“如果数组有 k 种不同颜色呢”，你可以分几种情况回答：
- 如果 k 很小，比如 k=3，荷兰国旗算法直接可用；
- 如果 k 在合理范围内，计数排序更合适，时间 O(n)，空间 O(k)；
- 如果 k 很大，且要求稳定排序，可以选择基数排序的思路，或者退化为基于比较的排序。
把这个逻辑讲清楚，会让面试官觉得你不是“背题”，而是真的理解了这一类划分问题的工具选择策略。
8. 我的实战体会与后续练习建议
8.1 这个题在真实工作中的应用场景
也许有人觉得这种题只存在于面试中，实际工作用不到。但你做日志清洗、数据分桶、配置下发时，经常会遇到“按某种优先级把异构数据重新组织”的场景。比如我给某个任务分发模块写过一段逻辑：把待处理消息按“高优、中优、低优”重排，本质上就是三向划分，只是把颜色换成了优先级数字。
一旦你习惯了这种思考方式，很多看似无序的数组重排需求，你都会下意识地想到“维护两个边界指针”。这种抽象能力正是刷题的意义——不是让你背题，而是训练你在工程里快速识别规律。
8.2 刷题复盘方法：三遍法
我总结了一个针对这类经典题的三遍刷法，适合任何需要深入理解的题目：
第一遍，看着标准答案写出来，并且手动模拟一遍小数据。第二遍，合上答案，在白纸上写完整代码，同时用嘴巴讲一遍不变量。第三遍，两天后不看任何资料，直接写一个新的变体题，比如把颜色分类改成“负数、0、正数”。只有到第三遍，你才算真正掌握。
如果你做到第三遍时卡住了，大概率是“为什么交换 2 之后不能自增”这一类的细节没理解透，回头重新看本文第 3 章。
8.3 推荐练习路径：从这道题出发的递进清单
这里给你一条完整的练习路径，适合把这题的知识点延伸开：
- 先做“颜色分类”本身；
- 再做“移动零”，体会双指针的简化版；
- 然后做“删除有序数组中的重复项”，理解快慢指针；
- 接着做“按奇偶排序数组”，练习分类交换；
- 最后尝试手写一遍三向切分快速排序。
走完这条路径，你对数组原地划分的理解会明显上一个台阶。面试时最大的收益，不只是答对这一道题，而是你能从这道题顺手带出快排、分区算法、复杂度分析一整套知识体系。
就我个人经验来说，面试时遇到这道题，最重要的不是“秒出代码”，而是你能否用一分钟讲清楚left、mid、right三个指针各自维护什么边界。把这个讲明白了，代码几乎是自然流露出来的。你可以找个朋友当面试官，让他随机打断追问“为什么交换 2 之后不前进”，如果你能连续五次回答到点子，这道题你就彻底吃透了。
