“75.颜色分类”，这道题在刷题圈里几乎无人不知——给一个只包含 0、1、2 的数组，要求原地排序成 0 在前、1 居中、2 在后的形式。数字 0、1、2 抽象为颜色，所以叫“颜色分类”。我第一次见它是在某刷题平台的热门题单里，当时觉得这题简单到离谱：这不是排个序就完事了吗？直到面试官追问“能不能一次遍历搞定，空间复杂度 O(1)”，我才意识到这道题真正考的是双指针的边界控制，以及背后那套荷兰国旗问题的 partition 思想。
这篇博客我用自己踩过坑、刷了三遍才彻底想通的经历，把这道题从暴力解到最优解拆开揉碎讲清楚，包括三个指针各自负责什么、为什么遇到 2 交换后指针不能直接前进、边界条件到底怎么写才不容易错，再看它在快速排序 partition、按条件切分数组这类场景里的延伸用法。无论你是刚开始刷题的新手，还是准备面试想查漏补缺，这篇文章应该都能让你少走点弯路。
1. 题目的本质：表面是排序，底子是荷兰国旗问题
1.1 为什么这道题值得反复刷
这道题虽然只是一个中等难度的数组题，但它把两个非常重要的算法思想浓缩在了十几行代码里：一个是“不变量维护”，另一个是“三向切分”。很多人在初学阶段把排序理解成调用 sort 函数，或者在思考排序时只会冒泡、选择、插入这类比较排序。而颜色分类这道题完全没有用到任何比较大小之外的标准库排序，它靠的是手动维护区间。
我第一次刷的时候走了个弯路：直接用桶计数，统计 0、1、2 的个数，然后重新填充数组。这种解法叫计数排序，在这道题里其实是可行的，因为数据范围只有 0、1、2 三种取值，而且空间复杂度是 O(1) 的额外空间。但面试官通常不会满意，因为他们真正想考察的是单次遍历原地解决的能力。这个能力背后的工具就是三指针，也叫双指针的变体。
为什么说这道题值得反复刷？因为它卡得恰到好处：代码量不大，但每个指针的移动条件都是考点。你只要有一个地方想当然，比如交换 2 之后顺手让当前指针前进，测出来结果就乱套。它像是练习“边界思维”的绝佳素材，能帮你建立一种条件反射——写循环之前先把循环不变量写清楚。
1.2 从暴力解到双指针的思维跨越
先说我最初想到的计数排序法，写起来大概是这样：先遍历一遍数组，记录 0 出现了几次、1 出现了几次、2 出现了几次；然后按照 0 的个数把开头都设成 0，接着设成对应个数的 1，最后设成 2。这个方案的时间复杂度是 O(n)，空间复杂度 O(1)，其实完全满足题目的基本要求。但问题是它遍历了两次，而且它没有体现“排序过程”，只是把统计数据回填。
还有一种是直接调用语言内置排序，比如 Python 的 sort()，C++ 的 std::sort()，也能过。但要是面试，这种解法基本等于告诉面试官“我根本没想明白这题想考什么”。颜色分类这样的有限取值范围排序，用比较排序去做属于杀鸡用牛刀，还会把时间复杂度从 O(n) 拖到 O(n log n)。所以最优解的目标非常明确：一次遍历、原地操作、不依赖额外数组、时间复杂度严格 O(n)。
双指针解法处理这个需求的手法，本质上是把数组划分成三个语义区域：最左边全是 0，最右边全是 2，中间剩下的是还没扫描到的部分。维护这三个区域不需要额外的存储，只需要记录三个边界位置，然后通过交换元素来扩张区域。这就是荷兰国旗问题的解法，也是三路快排的分区雏形。顺着这个思路去理解，后面的代码实现就会非常自然。
2. 三指针的核心思路拆解
2.1 三个指针的分工：谁负责扫，谁负责守边界
很多讲这道题的文章会把三个指针称为 low、mid、high，或者 left、current、right，名字不重要，关键是要知道每个指针维护的是哪一段区间。
我习惯把指针定义成这样：
- left：下一个 0 应该放的位置，初始为 0，它左边的元素全是 0。
- right：下一个 2 应该放的位置，初始为数组末尾，它右边的元素全是 2。
- current：当前扫描到的元素位置，从 0 开始向右移动，它负责遍历整个数组。
在整个循环过程中，数组始终满足这样的不变量：
- 区间 [0, left) 内全部是 0
- 区间 [left, current) 内全部是 1
- 区间 (right, n-1] 内全部是 2
- 区间 [current, right] 是尚未处理的未知区域
这个不变量是整个算法的灵魂。我一开始没有刻意去写不变量，直接照着别人的代码敲，结果一旦程序出错就完全不知道问题出在哪。后来我学乖了，先在草稿纸上画一条数组线，标出三个指针位置，写上这四个区间的定义，再去写循环体，发现清晰非常多。你只要保证这个不变量在每一步交换后仍然成立，算法就是正确的。
2.2 循环终止条件：为什么是 current <= right 而不是 current < right
这三个指针的相对位置决定循环什么时候结束。很多人容易把终止条件写成 current < right，这是比较常见的错误。当 current == right 的时候，最后一个元素其实还没有被扫描，它处于 [current, right] 这个未处理区间内，也就是说 current 指向的这个位置仍然需要判断一次。如果把条件写成 current < right，最后一个位置就被跳过了。
我自己测试的时候遇到过这样的输入：[2, 0, 1]。如果循环条件是 current < right，运行到 current == 2、right == 2 时会停下来，但 nums[2] 是 1，还没有被正确处理，结果就错了。所以循环条件必须取等号，保证每个元素都被处理到。
再往深处想一下，为什么循环结束时 current 会大于 right？因为当 current 与 right 相遇后，如果 current 指向的元素是 0 或者 1，current 会向右移动，结果 current 超过 right，循环结束；如果 current 指向的元素是 2，交换后 right 左移，current 会与 right 错开。不管哪种情况，整个数组都会被三段区间覆盖完整，顺序正确，不变量成立。
3. 完整代码实现与逐行讲解
3.1 最直观的 Python 实现
先给出我用着最顺手的实现，语言是 Python。
def sortColors(nums): left, current, right = 0, 0, len(nums) - 1 while current <= right: if nums[current] == 0: nums[left], nums[current] = nums[current], nums[left] left += 1 current += 1 elif nums[current] == 1: current += 1 else: # nums[current] == 2 nums[current], nums[right] = nums[right], nums[current] right -= 1这段代码里最核心的逻辑是三个分支：
当遇到 0 时，把它交换到 left 指向的位置，然后 left 和 current 同时前进。为什么 current 可以前进？因为交换回来的元素，也就是 nums[left] 原来的值，只可能是 0 或 1。如果原来 left 位置是 0，交换后 current 位置是 0，它已经被处理过了；如果原来 left 位置是 1，交换后 current 位置是 1，而 1 本来就该留在中间区域，直接跳过即可。所以在这种情况下 current 前进是安全的。
当遇到 1 时，什么都不用做，它已经在正确的位置区间内，直接 current += 1。
当遇到 2 时，把它交换到 right 位置，然后 right -= 1。这里 current 不能前进，因为从 right 交换回来的元素可能是 0、1 或者 2，完全是未知的。如果贸然前进，这个未知元素就被跳过，后续不会被处理。很多错误的写法就是少考虑了这一步，我在 3.2 节会专门展开。
3.2 最容易写错的两个细节
第一个细节就是上面说的，遇到 2 时交换之后不能顺手 current += 1。我见过不少新手代码长这样：
else: # nums[current] == 2 nums[current], nums[right] = nums[right], nums[current] current += 1 right -= 1比如输入是 [2, 0, 1]，第一步 current 指向 2，交换后数组变成 [1, 0, 2]，如果 current 前进到 1，right 变成 1，接下来 current 指向 0，交换后变成 [0, 1, 2]，看起来好像碰巧对了。但换成 [2, 0, 2, 1] 就会出错。所以正确做法是交换后只 right -= 1，让 current 停住，下一轮继续处理交换回来的元素。
第二个细节是交换的时候，如果用中间变量 tmp 来写，要注意先赋值哪一个。用 Python 的并行赋值还好，但要换成 C++ 或 Java 写法，顺序写反就会把 left 或 right 覆盖掉，导致后面的操作全部错乱。建议这种交换逻辑统一用异或或者临时变量，并养成先读后写的习惯。
我再给一份 Java 版本，给习惯用 Java 刷题的朋友参考：
public void sortColors(int[] nums) { int left = 0, current = 0, right = nums.length - 1; while (current <= right) { if (nums[current] == 0) { int temp = nums[left]; nums[left] = nums[current]; nums[current] = temp; left++; current++; } else if (nums[current] == 1) { current++; } else { int temp = nums[current]; nums[current] = nums[right]; nums[right] = temp; right--; } } }这份代码本质上和 Python 版本是同一个逻辑，区别只在于手写交换。
3.3 为什么时间复杂度是 O(n)、空间复杂度是 O(1)
这道题的时间复杂度分析比普通排序更直白。整个算法只有一个 while 循环，每执行一轮循环，current 和 right 中至少有一个在朝着对方移动（current 右移，right 左移）。遇到 2 的情况，current 不动但 right 左移；遇到 0 或 1 的情况，current 右移。无论走哪个分支，未被处理区间都在收缩，因此循环最多执行 n 次左右，时间复杂度是 O(n)。
空间方面，只用了 left、current、right 三个变量做指针，交换操作就在原数组上完成，没有申请额外数组，所以额外空间是 O(1)。相比计数排序或者调用标准排序，这套解法的优势不只是常数级别的时间快慢，而是体现了一种非常强的设计意识：用两个边界把数组切成三段，就地整理。
4. 常见问题与排查技巧实录
4.1 死循环场景：为什么有时候程序一直跑不完
有一类错误是 while 循环里面，遇到 2 交换后既没有 right -= 1，也没有 current += 1，代码会无限循环。比如写成这样：
else: nums[current], nums[right] = nums[right], nums[current]交换后 right 没动，current 也没动，下一轮 current 还是指向同一个位置，如果是 2 就再交换一次，又回到原始状态，变成死循环。排查这类问题其实有个非常有效的土方法：把每一步交换后的数组打印出来。如果在连续几轮里数组状态完全没变化，说明指针没有正确收缩。
我调试这类指针题的习惯是写一个很小的辅助函数，在循环里打日志，打印出当前 left、current、right 和数组内容。看到数组不变就能立刻定位问题。等确认无误后再把日志删掉。
4.2 边界测试用例：这组数据让你一次测出所有隐蔽问题
刷题时如果只测示例用例，很容易带着错误提交后才被测试用例打脸。我用的一组测试用例包括：空数组、只有一个元素、全 0、全 1、全 2、0 和 2 交替、2 和 1 混合、最长的两端都是边界值的情况。你把这组用例跑过，基本能覆盖所有指针移动分支。
test_cases = [ [], [0], [1], [2], [0, 0, 0], [1, 1, 1], [2, 2, 2], [2, 0, 1], [1, 0, 2], [2, 2, 0, 0, 1, 1], [0, 1, 2, 0, 1, 2], [2, 1, 0, 2, 1, 0] ] for case in test_cases: sortColors(case) assert case == sorted(case), f"failed: {case}"上面的断言直接用 sorted 结果做对照，虽然测试代码里用了排序，但我们的算法本身并没有依赖排序库，只是拿它做校验而已。刷题阶段这样写很合适。
4.3 从错误提交中总结出的三条经验
我在不同时间刷这道题时犯过三种错，它们各有代表性。
第一种是循环条件写成 current < right，具体影响前面已经分析过，最后一个元素没有被处理。
第二种是遇到 2 之后 current += 1。这个问题在元素种类较多、重复较多时更容易暴露。
第三种是交换 0 和 2 的时候把 right 和 left 写混。比如在 nums[current] == 0 的分支里，把元素交换到 right 而不是 left，结果整个数组越整理越乱。
这些错误的共同根源都是没有先在心里确认“当前这个位置的值到底是什么，交换之后会变成什么值，哪个指针可以移动”。建议你写代码之前养成一个习惯：把每个分支中交换前和交换后的区间状态画出来，不在脑内推理全貌就动手，出错的概率极高。
5. 从颜色分类到三路快排和真实工程场景
5.1 快排 partition 的亲戚：三路快排
如果只看这道题本身，你会觉得它就是一个灵活运用双指针的小题目。但把它放进整个算法知识体系里看，它其实就是三路快排最核心的那个 partition 过程。
经典快速排序的 partition 通常把数组分成小于基准和大于等于基准两部分，也就是两路切分。当数组里存在大量重复元素时，两路切分会导致重复元素频繁跨区交换，性能下降。三路快排的解决办法是分成三个区：小于基准、等于基准、大于基准。你看颜色分类里的 0、1、2，完全可以替换成“小于基准的数、等于基准的数、大于基准的数”，也就是说这题就是三路快排针对固定三个标签值的特例。
我当时刷完这道题后，专门去对照着实现了一版三路快排，核心代码非常相似：
def quick_sort_3way(nums, lo, hi): if lo >= hi: return lt, i, gt = lo, lo + 1, hi pivot = nums[lo] while i <= gt: if nums[i] < pivot: nums[lt], nums[i] = nums[i], nums[lt] lt += 1 i += 1 elif nums[i] > pivot: nums[i], nums[gt] = nums[gt], nums[i] gt -= 1 else: i += 1 quick_sort_3way(nums, lo, lt - 1) quick_sort_3way(nums, gt + 1, hi)你发现没有，这个 partition 内部的循环结构和颜色分类几乎是同一套模板，只是把判断 0、1、2 改成了与基准值比较大小。理解了颜色分类，三路快排的很多边界细节就顺带理解了。
5.2 实际工作里的分类切分需求
刷题时我们关心指针和边界，但回到真实工程里，这种按多个条件将数据切分成多个区间的操作也有非常广的应用场景。比如一段日志数据里有不同等级的消息，你要把所有 error 放前面、warning 放中间、info 放后面，并且不希望额外申请大量内存，那就可以用类似三指针的思路原地整理；再比如处理一批用户画像标签，按“低中高”三档切分，也可以直接套这套逻辑。
不过实际开发中，如果数据量不大或者关注代码可读性，我一般不会真的写三指针原地修改，而是更倾向于用 Python 的列表推导或者 sorted(key=...) 来分组，因为代码更直白。这道题的双指针解法更大的价值在于培养思维，而不是让你在任何地方都用它替代标准库。懂得在什么场景用复杂算法、什么场景用标准库，也是经验的一部分。
5.3 面试延伸：把颜色分类改一改，你还认识它吗
面试官非常喜欢在这道题基础上做变形，目的是考察你理解了思想还是背了代码。常见的几个变体有：
- 把数组按照负数、0、正数分成三段，保持各自相对顺序不确定，只要求左负右正。
- 把数组按照某个阈值分成小于、等于、大于三组，这就是三路 partition 的朴素版。
- 把奇数和偶数分成两段，奇数在前偶数在后，并且不改变它们之间的相对顺序，这个就涉及稳定 partition，比颜色分类更难。
面对这些变形，核心永远是先想清楚三个问题：我的数组要被切成哪几段？段与段的边界由什么指针维护？每个分支里交换之后哪些指针可以移动、哪些不能移动。把这三个问题回答完，代码基本就能正确写出来。
我在面试辅导中见过不少同学，能一口气把颜色分类的原题写对，但一问到“如果改成偶数在前奇数在后，你的代码哪里要改”，就卡住了。原因是他们记住了代码的形态，没有理解分区的本质。所以我建议刷完这道题后，自己手动改一版负数/0/正数分类的代码，再改一版奇偶分类的代码，感受一下哪些逻辑需要调整，哪些逻辑是不变的。这样才算真正吃透了它。
最后说一点个人实操中的体会。我做这道题最大的收获不是记住了解法，而是养成了一个习惯：写任何涉及指针移动的循环之前，先在注释里把四条区间边界写清楚。看起来是多花了几秒钟，实际省下来的调试时间往往是几小时。颜色分类作为一道经典题，教给你的不只是 0、1、2 怎么排，更是一种组织代码边界的通用方法论。如果你现在还在靠背代码应付指针题，我强烈建议你从这道题开始，试试先画区间、再写逻辑，跑一轮测试用例，你会发现自己对“指针到底指向哪里”这件事的理解会上一个台阶。
