企业官网建设流程全解析

刷算法题的朋友一定碰到过这样一道“简单但经典”的题：数组里只放着 0、1、2 三种数字，代表三种颜色，要求你原地把数组排成 0 在前、1 在中间、2 在后的样子。这就是颜色分类问题，也叫三色分区问题，老派算法书里通常称它为“荷兰国旗问题”。我第一次看到这题时觉得很简单，直接数数字不就好了？后来才发现，这道题真正想考察的是在一轮遍历内完成原地归位的能力。文章会从最直观的解法讲起，再落到三指针的写法、循环不变量、边界条件和调试技巧，希望能帮准备面试或刚开始刷题的读者真正吃透它。

题目本身“看着越简单，越容易翻车”，比如处理 2 时的指针移动，几乎所有初学者都踩过。这篇文章不打算只贴代码，而是把为什么这么写、哪里容易错、如何自检一次讲清楚。无论你是刷题小白，还是想再夯实基础的老手，都能从“数组分区”这个思想里获得点东西。

1. 先把问题拆明白：什么是颜色分类

1.1 题目到底在问什么

给定一个长度为 n 的数组，数组里只可能出现三个值：0、1、2。你可以把它们理解成三种商品类别、三档优先级，或者三种颜色。要求最终得到的数组中，所有 0 排在最前面，所有 1 排在中间，所有 2 排在最后，也就是一个按 0、1、2 顺序排列的有序数组。题目通常会额外强调两点：一是必须原地修改数组，不能新建一个大数组再拷贝回去；二是不推荐直接调用内置排序函数，因为这样就把题目的价值抹掉了。

我在实际动手之前，会先和面试官确认几个输入细节：数组是否允许被修改，函数是否需要返回排序后的数组，输入能否保证只有 0、1、2。这些看着像废话，但确实会决定代码形态。比如有的题目允许自建数组，那统计重写就是最简单直接的方案；但如果要求严格原地且只能遍历一轮，就必须上三指针。问题描述里的“颜色分类”其实很像一个场景包装，本质可以抽象成“把三类数据按指定顺序分区”，这对后面的解法选择很重要。

1.2 为什么“三色分区”是这道题的灵魂

与其说这道题在考排序，不如说它在考分区。整个过程不是比较数字大小，而是把元素放进对应的区域：左边放 0，中间放 1，右边放 2。因为颜色只有三种，分区天然可以用“边界指针”来完成，而不是用那些复杂的排序算法。这种思想一旦建立，你再看其他类似题目就会很轻松，比如把数组按奇偶分成两段，把负数、零、正数分成三段，本质上都是同一个套路。

三色分区还有一个很有意思的地方：数组里的元素没有相对顺序的要求，只要求“同一类的归在一起”。这意味着你不需要关心交换的稳定性。正因为不需要稳定性，原地交换才不会丢信息。如果题目改成“希望相同颜色的元素保持原顺序”，那代码难度会明显提升，三指针方案就不够用了。所以在做题前想清楚“稳定性是否是硬要求”，是第一步。

1.3 一道简单题的隐藏考点

这道题在算法题库里的难度标得不高，但它被反复拿出来做面试题，主要是因为背后的考察点非常密集：

• 时间复杂度的敏感性。数据规模可能很大，O(n log n) 的排序虽然能过，但不是最优解。
• 空间复杂度的约束。要求原地操作时，能不能忍住不用额外数组，直接体现对内存的敏感度。
• 边界条件的严谨性。指针初始化、循环终止条件、交换后的指针移动，每一个细节都会让代码功亏一篑。
• 对循环不变量的解释能力。能讲清楚“为什么这样操作之后数组始终满足区域划分”，比跑通代码更能打动面试官。

我见过一些代码写得飞快的人，闭上眼睛能默写三指针，但被问到“遇到 2 交换后 cur 为什么不能动”，一下子就卡住了。这也是我写这篇文章的原因：不仅给出答案，更要把答案背后的逻辑链完整地摆出来。

2. 方案选型：三种常见思路的取舍

2.1 方案一：先统计再重写

最容易想到的方案就是统计重写。第一遍遍历数组，用三个计数器分别数出 0、1、2 的个数；第二遍再根据计数结果，按顺序把数组重新填成 000...111...222。这个方案时间复杂度是 O(n)，空间复杂度 O(1)，只需要几个计数器，不需要额外数组，所以它完全满足“原地”的要求。很多第一次刷到这道题的人，第一反应就是写这个。

写成代码大概是这样：

def sort_colors_count(nums): cnt = [0, 0, 0] for x in nums: cnt[x] += 1 idx = 0 for color in range(3): for _ in range(cnt[color]): nums[idx] = color idx += 1

代码本身没有错，结果也正确。但有个致命缺点：它遍历了两遍数组。如果面试官追问“能不能一次遍历就完成排序”，这个答案就不够看了。三指针方案之所以是标准答案，不是因为统计重写不行，而是因为它没有把题目的全部分数拿满。实际面试中，我会把统计重写当作破题思路先抛出来，让对方看到我能快速理解题目，然后再给出更优的三指针方案。

2.2 方案二：左右双指针的初次尝试

还有一种很自然的思路：维护一个左指针 p0，专门用来放 0；维护一个右指针 p2，专门用来放 2。如果遇到 0，就和 p0 位置交换；如果遇到 2，就和 p2 位置交换。听起来只需要两个指针就够了，但真写起来会发现一个问题：你还需要一个“当前扫描位置”的指针。如果只有 p0 和 p2，你无法保证中间区域的每个元素都被遍历过。

举一个简单场景：数组是 [1, 2, 0, 1]。如果你只用左指针放 0、右指针放 2，扫到下标 1 的 2 时，把它交换到右边，然后再从左往右扫，可能把已经交换到左边的 0 又处理一次，或者漏掉某些元素。原因就是缺少一个独立的 cur 指针来标记“当前检查到哪个位置”。这个思考过程非常关键，它天然地把人引向三指针：左边一个边界，右边一个边界，中间一个扫描指针，三者配合才能一遍扫描搞定。

2.3 方案三：三指针单遍扫描

三指针方案的核心思路很清晰：p0 维护 0 区的右边界，p2 维护 2 区的左边界，cur 从左往右扫描未处理区域。初始时，p0 和 cur 都指向数组开头，p2 指向数组末尾。cur 每走一步，根据当前元素的值做三种处理：遇到 0，就扔到左边；遇到 2，就扔到右边；遇到 1，直接跳过。当 cur 越过 p2 时，整个数组已经被划分成三段，排序也随之完成。

这个方案的优势非常明显：只需要一次遍历，不需要统计数字出现次数，空间上只有三个整数变量，原地修改数组。它利用了“元素只有三个值”这个特性，把排序问题简化成“分区问题”。正因如此，它才是这道题在面试中的最优解。

2.4 方案对比：选哪种更合身

从面试角度看，三指针是标准答案。直接排序虽然第一眼就能想到，但它没有利用元素只有 0、1、2 这一关键信息，复杂度也不是最优。统计重写适合当作热身思路，如果面试官没有特别要求“单次遍历”，它是可接受的答案。但只要你亮出三指针，并解释清楚循环不变量，通常就能拿到这道题的满分。

2.5 选型时的几个判断维度

我在实际刷题中总结过一套选型标准，可以迁移到很多类似题目：值域是否有限且已知？是否可以原地修改？是否需要稳定排序？是否必须一次遍历？对于颜色分类这道题，四个问题的答案分别是：是、是、不需要、必须。三指针方案正好同时满足所有硬性约束。如果题目改成“对任意整数数组排序”，值域无限，那三指针就不适用了，应该考虑快速排序或归并排序。如果要求稳定，那三指针交换会破坏相同元素的相对顺序，需要改用统计加重写数组，或者用额外空间做稳定归并。选解法之前，先列需求清单，能少走很多弯路。

3. 三指针实现：核心逻辑与循环不变量

3.1 指针分工和区域模型

三个指针的功能需要非常明确：

• p0：下一个 0 应该放置的位置，初始指向数组开头。
• cur：当前正在扫描检查的位置，初始也指向数组开头。
• p2：下一个 2 应该放置的位置，初始指向数组末尾。

如果把数组画成一条线段，那么整个过程里它始终被分成四段：

0 区 | 1 区 | 未处理区 | 2 区 p0 cur p2

其中，p0 左边所有元素都是 0，p0 到 cur 之间所有元素都是 1，p2 右边所有元素都是 2。cur 到 p2 之间是仍未被检查的元素。这个描述就是这道题的循环不变量。只要每一次交换和指针移动都维持这个结构不变，那么当循环结束时，所有区域自然正确。我每次写代码前都会在草稿纸上画出这个图，它能避免绝大多数指针错乱的问题。

3.2 三种情况下的交换规则

当 nums[cur] 的值不同，处理方式完全不同，这是整个算法的核心。

如果 nums[cur] 是 0，说明这个元素应该出现在最左边。此时把它和 nums[p0] 交换，然后 p0 向后移动一位，cur 也向后移动一位。为什么 cur 可以放心前进？因为 p0 位置上的值只可能是 0 或 1，不可能是 2。如果 p0 位置上原本是 1，交换后 cur 位置变成 1，这正好属于中间区域，cur 可以直接跳过；如果 p0 位置上原本是 0，说明 p0 和 cur 指向同一个位置，交换等于原地不动，cur 前进也没有问题。

如果 nums[cur] 是 1，说明它本来就该呆在中间区域，什么都不需要交换，直接 cur++。

如果 nums[cur] 是 2，说明它应该被放到最右边。此时把它和 nums[p2] 交换，然后 p2 向前移动一位，但 cur 不能动。因为你从 p2 位置换回来的值可能是 0、1、2 中的任意一个，这个值还没有被检查过，必须停留在当前位置再走一轮循环。很多错误代码都是在这里顺手加了 cur++，结果换回来的 0 被直接跳过，排序结果就错了。

3.3 代码实现：Python 版

把上面的规则翻译成代码，就是下面这个样子：

def sort_colors(nums): n = len(nums) p0, cur, p2 = 0, 0, n - 1 while cur <= p2: if nums[cur] == 0: nums[p0], nums[cur] = nums[cur], nums[p0] p0 += 1 cur += 1 elif nums[cur] == 2: nums[p2], nums[cur] = nums[cur], nums[p2] p2 -= 1 else: # nums[cur] == 1 cur += 1 return nums

这段代码直接在原数组上修改，最后返回 nums 只是为了方便测试。很多语言版本都和这个写法等价，只有交换语句和指针更新的顺序需要特别注意。如果你用的是 C 或 Java，记得把数组以引用方式传进去，函数内修改后外部数组也会变化。Python 的列表本身就是引用语义，所以不需要额外处理。

3.4 手动模拟全过程

空讲规则不够直观，我用手写一遍完整案例。假设输入是 [2, 0, 2, 1, 1, 0]。

初始状态：p0 = 0，cur = 0，p2 = 5，数组为 [2, 0, 2, 1, 1, 0]。

1. cur = 0，nums[0] = 2，与 p2 = 5 交换。数组变成 [0, 0, 2, 1, 1, 2]，p2 变为 4，cur 保持 0。
2. cur = 0，nums[0] = 0，与 p0 = 0 交换。数组不变，p0 变为 1，cur 变为 1。
3. cur = 1，nums[1] = 0，与 p0 = 1 交换。数组不变，p0 变为 2，cur 变为 2。
4. cur = 2，nums[2] = 2，与 p2 = 4 交换。数组变成 [0, 0, 1, 1, 2, 2]，p2 变为 3，cur 保持 2。
5. cur = 2，nums[2] = 1，cur 变为 3。
6. cur = 3，nums[3] = 1，cur 变为 4。

此时 cur = 4，p2 = 3，while 条件 cur <= p2 不成立，循环结束。最终数组是 [0, 0, 1, 1, 2, 2]，完全正确。

模拟中最容易让人困惑的是第 2、3 步，出现自己和自己交换的情况。这不是 bug，而是因为 p0 和 cur 重合时，当前位置已经是一个 0，交换后虽然没有改变数组，但 p0 和 cur 的推进保证了“0 区”的范围在扩大，逻辑上是必要的。理解了这一点，再看这段代码就不会觉得有多余操作。

3.5 终止条件与正确性论证

循环条件写成 cur <= p2，而不是 cur < p2。原因很简单：当 cur 等于 p2 时，当前指针指向的元素还没有被检查。它可能是 0、1 或 2，必须再执行一轮处理。如果写成 cur < p2，循环会提前退出，最后一个元素可能没有被正确归位。我会在下一章专门用一个反例说明这个问题。

为什么算法一定会终止？因为每次循环，要么 cur 增加至少 1，要么 p2 减少至少 1，两个指针不断靠近，最终必然出现 cur > p2 的情况。由于循环不变量始终成立，当循环结束后，p0 和 p2 之间已经不存在未处理元素。于是 0 都在 p0 左边，2 都在 p2 右边，中间自然全是 1。这就是一个完整的正确性论证，面试时值得把它说出来。

4. 实操记录：边界、坑位与测试用例

4.1 边界情况逐个击破

数组可能很空，也可能全是同一种颜色。我分别验证一下三指针代码的行为。

空数组：n = 0，p0 = 0，cur = 0，p2 = -1。while 条件 cur <= p2 为 false，直接返回，不需要额外处理。

单元素数组：如果是 [0]，cur = 0，p2 = 0，进入循环，nums[0] = 0，交换后 p0 = 1，cur = 1，循环结束。如果是 [1]，直接 cur++。如果是 [2]，与自身交换后 p2 变为 -1，循环结束。三种情况都正确。

全是 0：cur 会一路向右移动，p0 也跟着移动，p2 始终不动，数组一直保持正确。全是 1：cur 从 0 一路走到 n，循环结束，数组不变。全是 2：cur 每次遇到 2 都与 p2 位置交换，交换到最后一次可能是自己和自己交换，p2 不断向左移动，最终数组还是全 2，结果正确。

我最担心的一种输入是“只有 0 和 2，没有 1”。比如 [2, 0, 2, 0]。三指针依然能正确运行，只是中间区域可能为空，但这不影响最终数组。边界情况需要刻意测试，因为有时候代码在常规用例上表现完美，遇到极端输入才暴露出指针更新的隐患。

4.2 三个高频坑，我用踩过的惨痛经验换来的

第一个坑：遇到 2 交换后冲动地写了 cur++。我第一次写三指针时，习惯性地把“交换后移动 cur”当成通用规则，结果在 [1, 2, 0] 上翻车。错误代码会把 0 从右边换到中间，然后 cur 直接跳过，最终得到 [1, 0, 2]，这当然是错的。正确做法是交换后 cur 原地停留，让下一轮循环去判断换回来的值。只要记住“从右边换回来的元素是陌生的，必须再看一眼”，这个坑就能避开。

第二个坑：循环条件写成 cur < p2。前面说过，cur 和 p2 相等时，还剩一个元素没有检查。比如输入 [1, 2, 0]，用 cur < p2 会得到 [1, 0, 2]，而不是 [0, 1, 2]。原因是当 cur 等于 p2 时，p2 位置刚好经过一次 2 的交换，里面留下了未检查的 0，循环却提前结束。条件写成 cur <= p2 是最稳妥的。

第三个坑：分支结构写错。应该用 if / elif / else 处理三种值，不能在处理完 0 之后又用独立 if 去判断同一个位置的 2。例如写成先if nums[cur] == 0: 交换，再写if nums[cur] == 2: 交换，在交换后 nums[cur] 可能已经改变，第二个 if 判断的就不再是原始值，容易误交换。用 elif 可以保证三个分支互斥，逻辑干净。

4.3 测试用例清单

我自己刷这道题时，会准备一组覆盖各种情况的测试用例。以下表格可以直接拿来验收：

除了手写这些用例，我还会写一个随机生成数组的测试脚本，用 Python 内置的sorted作为对照，随机跑几百次，确保三指针结果和内置排序一致。这种方法对验证指针类代码特别有效，能快速发现隐藏的索引越界或死循环问题。

4.4 如果颜色变成 k 种，怎么扩展

三指针方案之所以叫三指针，是因为只有三种颜色。如果题目变成“数组里有 k 种不同的值，要求按大小排序”，三指针就不够用了。此时更合适的是计数排序：第一次遍历统计每个值的出现次数，第二次遍历按顺序回填。如果 k 不大，计数排序时间复杂度仍然是 O(n)，空间复杂度 O(k)。

如果 k 很大，或者值域无法提前确定，那就退化成普通排序问题，直接用快速排序或归并排序。这里有一个很容易混淆的点：三向切分快速排序和这道题的三指针思想很像。快速排序在处理大量重复元素时，会把数组分成“小于基准”、“等于基准”、“大于基准”三个区域，正好也是三指针分区。所以把颜色分类吃透，对理解快速排序的优化版本也有帮助。

5. 常见问题与排查技巧实录

5.1 为什么遇到 2 交换后 cur 不前进？再说一次

这个问题值得反复强调。遇到 2 时，我们执行nums[cur], nums[p2] = nums[p2], nums[cur]，然后把 p2 减一。关键点在于，从 nums[p2] 换过来的值是原来右边区域的元素，这个元素从来没有被 cur 检查过。它可能是 0，也可能是 1，甚至也可能是 2。如果此时 cur++，就相当于把这个未知元素直接跳过，后面再也没有机会处理它了。

用一个生活化的类比：你在流水线上检查物品，看到一件“该放右边”的物品，你把它丢到右端的箱子里，同时从右边箱子里随手抓了一件物品放到流水线当前位置。你当然要先看看抓来的是什么，再决定怎么处理。如果看都不看就直接推进，那件物品就可能永远留在错误区域。

5.2 为什么遇到 0 交换后 cur 可以前进？

遇到 0 时，交换源是 nums[p0]。p0 指向的是 0 区右侧的第一个位置，这个位置只可能是 0 或 1，绝不可能是 2。为什么？因为所有 2 都被交换到 p2 右边了，p0 到 p2 之间的元素只可能是 0、1、2 中的 0 和 1，而 p0 左侧都是 0，p0 到 cur 之间都是 1。所以 p0 位置的值要么是 0（当 p0 和 cur 重合，还没碰到过 1），要么是 1（已经碰到过 1 被保留在中间区域）。交换后，cur 位置的值变成 0 或 1，都不会破坏区域划分，因此 cur 可以安全地前进。这个逻辑是整个算法的关键证明，面试时特别加分。

5.3 快速定位错误的调试方法

如果代码跑出来不对，不要靠肉眼死盯，我推荐“打印状态法”。在 while 循环里，每轮处理完输出四个东西：nums、p0、cur、p2。观察每一步是否符合循环不变量。比如 p0 左边是否全是 0，p2 右边是否全是 2，p0 到 cur 之间是否全是 1。一旦哪一步不满足，错误位置立刻就暴露了。

你也可以在代码里临时加断言。例如在循环开始时检查：

assert all(x == 0 for x in nums[:p0]) assert all(x == 1 for x in nums[p0:cur]) assert all(x == 2 for x in nums[p2+1:])

如果断言没有触发，就说明当前状态始终满足分区要求。这种方法比打印更自动，适合跑大量随机测试。等代码确认正确后，再把调试用的断言删掉，保持提交干净。

5.4 面试官追问时怎么应答

这道题被问得最多的问题就是“为什么不直接用计数排序”。我的回答思路是先肯定计数排序可行，再指出它需要两遍遍历：一遍统计，一遍回填。三指针的优势是单遍扫描、常数空间，而且把“排序”转化成了“分区”，这更贴合题目“颜色分类”这个场景。如果面试官追问稳定性，我会如实说明：三指针使用交换操作，会改变相同颜色元素的相对顺序，因此不稳定；如果需要稳定结果，要改用额外空间或统计回填。如果追问正确性，就把循环不变量和终止条件讲清楚。这些应答点其实都是前面内容的浓缩。

5.5 一个抽象出来的模板：分区思想

做完这道题，不要只把它当成一道题，而是把它抽象成一个模板：维护左边界指针、右边界指针、扫描指针，按条件把元素丢到左边或右边。当丢到右边时，扫描指针不能前进。这个模板可以用来解决很多看似完全不同的题目，比如“把数组中的 0 都移到末尾，保持其他元素相对顺序”“把负数放左边，正数放右边，零放中间”“按某个阈值把数组分成大于等于小于三段”。

我自己在后续刷题中，不止一次被这个模板救过场。尤其是遇到“不使用额外空间”“原地调整顺序”这类约束时，第一个想到的就是三指针分区。所以别看颜色分类只是一道简单题，它背后藏着的是一整套数组操作的方法论。

最后分享一个我自己的习惯。刷完这道题后，我会把“三指针分区 + 循环不变量”记成模板，后来做快排优化、数组奇偶分离、按条件稳定分区时都能直接套。尤其是面试时，遇到任何“不用额外空间把数组分成两类/三类”的题，第一反应就该是这个框架。所以别小看这道题，真正值钱的是它背后的思考方式，而不只是答案本身。