企业官网建设流程全解析

当时刷到 hot100 榜单里的第 75 题“颜色分类”，我第一反应是：这不就是个排序题吗？数组里只可能有 0、1、2 三种值，排完之后就是一堆 0、一堆 1、一堆 2，题目把术语换成了红色、白色、蓝色，要求把三色球原地分成连续色带。

真正上手以后才发现，这题的门槛不在“排序”本身，而在于三条约束同时压上：单趟扫描、常数空间、原地操作。如果你只会写计数排序或者调内置排序，题目能过，但背后那个最有价值的东西——荷兰国旗算法的三向切分思想，就白白错过了。这题在 hot100 里排名靠前是有原因的，它可以顺手延伸到三向快排、数组分区、流式数据处理，属于“表面人畜无害、内里信息量很大”的代表。

这篇笔记不打算按题解模板讲，我会从第一直觉出发，拆清楚为什么计数排序不是最优解，然后把三指针算法完整走一遍，再讲几个我自己写代码时踩过的坑。

1. 从第一眼直觉说起：这道题为什么能和“排序”挂上钩

1.1 题库里为什么给这道题一个这么高的位置

我刷 hot100 的时候有个习惯，会把每道题标一个“知识点标签”。颜色分类的标签如果只写“数组排序”，那是浪费了它；更准确的标签应该是“三向分区”或者“荷兰国旗问题”。

常见的题目往往有两种，一种是偏、怪、难，需要大量小技巧；另一种是从朴素问题出发，最终收敛到一种极具代表性的算法范式。颜色分类属于后者。它高频出现在面试和竞赛准备里，不是说候选人不会写排序，而是考官想看你能否在严格的复杂度约束下，用最小的空间和单趟扫描完成一次三分。

在 hot100 里，这道题位置靠前，基本可以理解为“入门向的经典”。它考察的不是你记得多少 API，而是你对指针、循环不变量、原地交换这三样基本功的熟练度。

1.2 题目的输出形态与求解约束

具体题面我不多复述，只说关键点：给定一个长度为 n 的数组，里面只有 0、1、2，把数组原地重排成所有 0 在左边、所有 1 在中间、所有 2 在右边。

输出形态很明确：执行完后数组应当是 0*a + 1*b + 2*c 的组合顺序。题目还要求不能用语言自带排序去直接处理，并且明确或隐式地希望时间 O(n)、空间 O(1)。

这里就能看出一个分水岭：如果你第一反应是“统计频率再填回去”，那说明你默认允许两次遍历。当你开始思考“能不能一次遍历就完成”，才会自然走到三指针。这也是我把“两遍扫描的局限”单独拎出来讲的原因。

2. 两遍扫描的局限：明明能过测试，为什么要花心思优化

2.1 基于计数的直白做法

先看大多数人的第一种解：第一遍遍历数组，数出 0、1、2 出现的次数；第二遍按照数量依次把 0、1、2 填回原数组。

我用伪代码描述一下：

cnt0 = cnt1 = cnt2 = 0 for x in nums: if x == 0: cnt0 += 1 elif x == 1: cnt1 += 1 else: cnt2 += 1 idx = 0 for _ in range(cnt0): nums[idx] = 0; idx += 1 for _ in range(cnt1): nums[idx] = 1; idx += 1 for _ in range(cnt2): nums[idx] = 2; idx += 1

这个方案时间复杂度是 O(n)，空间复杂度只要三个计数器，看起来也很“常数空间”。它甚至能通过绝大多数测试用例。但仔细读题会发现，它完整扫描了两遍数组，第一遍读，第二遍写。在普通工程里，这根本不算事；但在算法题语境里，“单趟扫描”是明确的进阶约束，考察维度就完全不同。

2.2 为什么题目强调扫描一次

强调单趟扫描，本质上是考察“流式处理”能力。正常写业务代码，我们随时可以反复读取一个数组，甚至拷贝一份出来随便折腾。但很多真实场景里，数据是流水一样过来的，你只有一次机会观察每个元素，必须在经过它的时候做出决定、修正状态。

三指针算法就是这种流式处理思维的代表：你从左到右扫过数组，遇到 0 就往左边区送，遇到 2 就往右边区送，遇到 1 就放着不管，继续向前。整个过程每个元素最多被查看一两次，数组不需要第二次整体遍历。

我在给这个题想一个生活化类比时，想到的是快递分拣：传送带上不断送来包裹，分拣员面前有三个筐，红筐放 0、白筐放 1、蓝筐放 2。分拣员不能先把所有包裹收进仓库再统一分类，而是一边让传送带走、一边把包裹放进正确的筐。单趟扫描要求的就是这种“边到边分”的动作。

2.3 什么时候两遍扫描仍然合适

我也要泼一点冷水。算法题里的单趟要求，不等于两遍扫描永远不好。如果数据量特别大、读一遍和读两遍的 IO 成本差距明显，那单趟确实有优势；但如果数组已经完整存在内存里，两次遍历也没有真实性能瓶颈。

更关键的是，在实际业务里，“一遍扫描”往往不是强制条件，而“简单、正确、可维护”才是硬需求。计数排序的代码简单，不容易出错，所以工程上它经常是更好的选择。做题时追求单趟，是为了训练算法思维；工程上不要为了炫技而炫技，该两遍就两遍，该排序就排序。

这个区分想明白了，再回头看荷兰国旗算法，心态就对了：它不是用来替代计数排序的银弹，而是一种让你理解怎样用最少的状态完成复杂分区的思想工具。

3. 荷兰国旗问题拆解：三指针如何维护三条连续色带

3.1 荷兰国旗算法的由来

“荷兰国旗”这个名字来自荷兰国旗的红白蓝三色条纹。如果你有一堆红、白、蓝三色的球，要求整理成红段、白段、蓝段三个连续区域，这个问题最早由 Dijkstra 提出，作为他分区思想的升级版本。

经典的快速排序 partition 会把数组分成“小于主元”和“大于主元”两块，但如果数组里有大量等于主元的元素，两块分区会让这些相等元素散落各处，后续递归依然要处理很多重复元素。三向切分把区间分成“小于”“等于”“大于”三块，能显著提升大量重复元素场景下的排序性能。

颜色分类的特殊之处在于，主元是固定的：小于区是 0，等于区是 1，大于区是 2。所以它不需要再选主元，直接套三向切分框架即可。

3.2 三个指针各管哪一段

我习惯用 left、mid、right 三个指针，也有题解写成 i、j、k，概念都一样。

• left 维护 0 区间的右边界，[0, left) 范围内的元素全部是 0；
• mid 是当前正在扫描的位置，也是 1 区间的右边界，[left, mid) 范围内全部是 1；
• right 维护 2 区间的左边界，(right, n-1] 范围内全部是 2；
• [mid, right] 范围内是尚未处理的待扫描区域。

初始时 left = 0，mid = 0，right = n - 1。随着循环推进，0 区间向右扩，2 区间向左扩，中间未处理区域不断缩小，直到 mid 超过 right，整个数组就被三条色带完整切分。

这个指针划分可以写成一张直观的表格：

每次循环只需要看 nums[mid] 一个位置的值，就能决定下一步动作，不需要额外数组，也不需要比较扫描过的历史元素。

3.3 循环里的三种动作及其正确性

循环主体是 while (mid <= right)。在每一轮里，看 nums[mid] 的值：

1. 如果等于 0：把 nums[left] 和 nums[mid] 交换，left 和 mid 各加 1。
2. 如果等于 1：只把 mid 加 1。
3. 如果等于 2：把 nums[mid] 和 nums[right] 交换，right 减 1，mid 保持不变。

第 3 种情况最容易让人懵：为什么交换之后 mid 不动？因为从 right 位置换过来的那个数，可能是一个还没检查过的 0、1 或 2，它不一定是“中间值 1”。如果不先看它就直接跳过，就可能让 0 或 2 残留在未处理区之外，最终结果就错了。

再来看第 1 种情况为什么可以让 mid 前进。因为 left 指向的位置要么是 0、要么是 1，这不难推导：左侧全是 0，left 到 mid 之间全是 1，所以 nums[left] 只可能是 0 或者 1。把一个 0 或 1 换到 mid 位置，mid 位置就变成了 0 或 1，属于合法停靠，mid 可以放心前进。

这套逻辑的正确性可以用循环不变量来证明：每一步执行完毕，四个区间依然满足定义；当循环终止时，未处理区间为空，于是数组按 0、1、2 排列完毕。这个证明比背代码重要得多，我每次写这道题时都会先在脑子里过一遍不变量，确保指针移动没有破坏区间性质。

4. 手把手推演一遍：[2,0,2,1,1,0] 的完整交换过程

4.1 初始状态与符号约定

光说不练是空的。我拿一个最容易写错指针的样例来完整走一遍：nums = [2, 0, 2, 1, 1, 0]，长度 6。

初始状态：left = 0，mid = 0，right = 5。

数组下标对应值：0:2，1:0，2:2，3:1，4:1，5:0。

这里先提醒一个写法细节：循环条件应该是 mid <= right。有人一开始写成 mid < n，这在数组里没有 2 的时候也能跑对，但只要 right 开始收缩，mid 就可能越过 right 之后继续扫描已经被归位到右侧的 2，导致多余交换和判断，甚至破坏结果。

4.2 逐步交换过程

第一轮：mid = 0，left = 0，right = 5。nums[0] = 2，属于第 3 种情况。把 nums[0] 和 nums[5] 交换，数组变成 [0, 0, 2, 1, 1, 2]。right 减为 4，mid 仍然等于 0。关键点来了：换到下标 0 的新值还没有被检查，所以这一步绝不能推进 mid。

第二轮：mid = 0，left = 0，right = 4。nums[0] = 0，属于第 1 种情况。把 nums[0] 和 nums[0] 交换，自交换，结果不变。left 变为 1，mid 变为 1。

第三轮：mid = 1，left = 1，right = 4。nums[1] = 0，仍然属于第 1 种情况。交换 nums[1] 和 nums[1]，再次自交换。left 变为 2，mid 变为 2。

第四轮：mid = 2，left = 2，right = 4。nums[2] = 2，第 3 种情况。把 nums[2] 和 nums[4] 交换，数组变成 [0, 0, 1, 1, 2, 2]。right 减为 3，mid 停留在 2。

此刻如果不理解逻辑，很容易以为已经排完了，直接推 mid。但实际上 nums[2] 现在是 1，还需要被 mid 扫描确认一次。

第五轮：mid = 2，left = 2，right = 3。nums[2] = 1，第 2 种情况，mid 变为 3。

第六轮：mid = 3，left = 2，right = 3。nums[3] = 1，第 2 种情况，mid 变为 4。

此时 mid = 4，right = 3，mid <= right 不再成立，循环停止。最终数组为 [0, 0, 1, 1, 2, 2]，正确。

4.3 从这个例子中能看出的两个关键现象

第一个现象：从 right 换回来的未知数，必须被原地重新检查。第二轮里 nums[0] 是 0，看起来像自交换，其实是因为 left 和 mid 正好指向同一位置；而第四轮换回来的是 1，mid 就必须停一次才能让它归位。

第二个现象：第 1 种情况里的交换，经常是“自交换”。left 等于 mid 时，交换的是同一个元素，逻辑上无害，但有的初学者喜欢在这里加一个 if (nums[left] == 1) 或者别的优化判断，完全没有必要。自交换也是常数时间，不会造成额外的开销，加判断反而让代码每个分支都要单独解释，容易出问题。

5. 代码实现与易错点：两个版本、两个陷阱

5.1 Python 版实现

Python 版本的代码最接近算法描述：

def sort_colors(nums): n = len(nums) left = 0 mid = 0 right = n - 1 while mid <= right: if nums[mid] == 0: nums[left], nums[mid] = nums[mid], nums[left] left += 1 mid += 1 elif nums[mid] == 2: nums[mid], nums[right] = nums[right], nums[mid] right -= 1 else: mid += 1

这个代码里最值得写注释的地方，是第 8 到 10 行：遇到 2 交换后，right 减 1，但 mid 没有加 1。如果你在抄这个模板，一定要把“为什么不加 1”写在旁边，否则下次你自己也会忘。

5.2 C++ 版实现

C++ 版本结构完全相同：

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

我在 C++ 里特别关注的是 vector 是否为空。如果 nums 是空数组，right 初始化为 -1，mid 初始化为 0，循环条件 mid <= right 为假，不会越界。这个细节很容易被忽略，但一旦你后面改成别的写法，空数组就是第一个崩溃点。

5.3 陷阱一：遇到 2 交换之后错误地把 mid 前进

前面已经反复强调，这里我再放一个错误示例：

if (nums[mid] == 0) { swap(nums[left], nums[mid]); ++left; ++mid; } else if (nums[mid] == 2) { swap(nums[mid], nums[right]); --right; ++mid; // 错误 } else { ++mid; }

如果把 ++mid 写进去，从 right 换回来的元素就直接跳过了。比如 nums[right] 原来是 0，交换过来后 mid 位置是 0，但 mid 已经加 1，这个 0 就会残留在未处理段的错误位置，最终结果可能是 0 和 1 的顺序错乱。我最初犯这个错误时，怎么都想不通为什么随机数组会偶尔出错，后来在纸上推演了一遍才意识到问题。

5.4 陷阱二：用三个独立 if 而不是 if-elif-else

如果把分支写成：

if nums[mid] == 0: ... if nums[mid] == 2: ... else: ...

那么在某一轮里，可能先执行了一次 0 交换，又执行了一次 2 交换。虽然某些数据下结果也凑巧正确，但指针推进的顺序变得不可控，调试体验极差。

我建议坚持 if / elif / else 结构：每一轮循环只做一件事，要么换 0，要么换 2，要么推进 1。这样循环不变量分析最简单，代码也最好读。

6. 边界用例与调试心得：不是过了样例就万事大吉

6.1 我日常测试的边界用例

刷题最怕的不是不会写，而是写出来之后只测了示例就跑。颜色分类的代码再短，也得能扛住极端输入。我平时至少会跑这些：

空数组：[]。right 为 -1，循环直接不执行，返回空数组，正确。

单元素数组：[0]、[1]、[2]。单元素要么直接返回，要么自交换，结果不变，正确。

双元素数组：[0, 2]、[2, 0]、[1, 1]、[2, 2]。双元素重点验证 2 交换之后是否能正确处理换回来的值。

全 0 数组：[0, 0, 0]，全 1 数组：[1, 1, 1]，全 2 数组：[2, 2, 2]。这三类主要防止某个分支死循环或者越界。

混合两种值的数组：[0, 1, 1, 0]，[2, 1, 2, 2]，[0, 2, 0, 0]。这类用例最容易暴露单趟扫描里指针停滞或提前推进的问题。

我把这些用例整理成表格，放在手边复盘时对照：

6.2 用一个随机数据验证思路

在本地做算法练习时，我习惯写一个简单对数器来验证正确性。做法不复杂：随机生成只包含 0、1、2 的数组，长度从 1 到 200 不等，分别调用我的 sort_colors 和语言内置排序得到标准结果，然后逐个位置对比。

跑一万组随机用例只需要几秒钟，但它能发现很多样例测不出来问题。我改过一版指针逻辑之后，就是靠这种随机数据测试抓到了一个很隐蔽的 bug：在某次交换之后，我把 mid 提前推进了，导致某些数组里 2 和 0 的顺序看起来对，但 1 的分布不连续。内置排序一对比立刻原形毕露。

如果你不想写完整对数器，也可以退而求其次：至少把数组长度设为奇数、偶数、很大、很小四种情况，再分别覆盖三种数字全有、缺一种、只一种等分布场景。这样虽然不如对数器彻底，也足以验证大部分实现。

6.3 我踩过的一个真实小坑：从 right 换回来的还是 2

有个边界情况特别容易让人迷糊：如果 right 这一侧的区间里连续好几个 2，那么从 right 换回来的值很可能还是 2。这时如果代码里给 2 分支加了 mid++，连续的 2 就会泄漏到中间区域。

比如数组 [2, 2, 2, 1, 0, 2] 这类分布，第一步把 mid 位置的 2 和 right 位置的 2 做交换，看起来像白换一次，但 right 缩短了，mid 却因为错误地增加而被推向下一个位置，导致接下来要处理的那个 1 没有被正确扫描，算法就陷入混乱。

正确的做法是让 mid 停留在原处，继续检查新换来的值，直到换回来的不再是 2。这里的关键不是省一次交换次数，而是保证未处理区间每一个元素都被真正检查过。

7. 衍生与延伸：从颜色分类到三向切分

7.1 三向切分与快速排序的关系

颜色分类算法并不仅仅是这道题的专属解法，它和快速排序里的三向切分完全同构。标准三向快排选择某个主元 v，把数组切分成小于 v、等于 v、大于 v 三段；颜色分类只是把主元固定成了 1，小于区是 0，大于区是 2。

理解了这层关系，以后看到“把数组按某个阈值分成小于、等于、大于三块”的题目，就可以直接套用这套指针模板，只是把判断条件从“等于 0”换成“小于主元”，从“等于 2”换成“大于主元”，指针推进规则完全不变。

我复盘时会额外做几道变形题，比如把奇偶数分区、把正负数分区，来检验自己是不是真的理解了三分逻辑。如果每次都能不假思索地写出正确实现，才说明这种思想进入了脑子，而不是只背了一个题解。

7.2 一类常见变体：两向分区

如果把数组只分成两类，比如把偶数和奇数分开，也可以用左右双指针，一个向右找第一个奇数，一个向左找第一个偶数，然后交换。它的逻辑比三指针更简单，但核心思想一脉相承：用指针维护“已归位区间”和“未处理区间”的边界。

如果你把颜色分类的 0、1、2 换成布尔值的真假、把数组换成自定义对象数组，这套原地交换、区间维护的思路依然成立。很多实际工程里的分区逻辑，比如压缩数据时把非空字段集中到前段，本质都是这种指针分区的应用场景。

7.3 自己在复盘之后的一点体会

最后说说个人感想。这道题让我真正觉得有价值的，不是记住了荷兰国旗算法的代码，而是把一个看似简单的排序问题，拆成了“区间定义 + 单趟扫描 + 循环不变量”的标准化思考过程。刷题最忌讳的是一遍样例通过就赶紧翻下一篇，热题 100 的题目大部分都有这种“二刷价值”。

我后来再写快排优化代码时，遇到大量重复元素就会想到三向切分；写流式数据处理接口时，也会习惯性问自己：这个数据能不能一遍扫完就完成分组？这些问题的答案，很多就是从颜色分类这道题里长出来的。

如果你正在按题单顺序刷题，我建议你在写完计数排序版本后，不要急着提交，先逼自己写一个不漏的荷兰国旗实现。多花二十分钟推演一遍三指针，比你多做两道无关的简单题更划算。