颜色分类为什么可以一趟完成？荷兰国旗三路划分怎么写？

简化版

颜色分类只有 0、1、2 三种值，不需要通用排序。用三个指针维护 [0..zero-1] 全是 0、[zero..i-1] 全是 1、[two+1..n-1] 全是 2，扫描 i 时遇到 0 就和 zero 换并一起右移，遇到 2 就和 two 换且只移动 two，遇到 1 才移动 i，一趟 O(n)、原地 O(1)。

详细版

这题是 LeetCode 75 的典型问法，本质是快速排序 partition 的三路版本。因为元素只有三类，所以目标不是比较排序，而是把数组原地切成三段：0 段、1 段、2 段。

关键在不变量：zero 指向下一个 0 应该放的位置，two 指向下一个 2 应该放的位置，i 扫描未知区。若 nums[i] == 0，把它换到左边，zero++、i++；若 nums[i] == 1，它已经在中间区域，i++；若 nums[i] == 2，把它换到右边，two--，但 i 不能动，因为换回来的元素还没检查。

void sortColors(int[] nums) {
    int zero = 0, i = 0, two = nums.length - 1;
    while (i <= two) {
        if (nums[i] == 0) {
            swap(nums, zero++, i++);
        } else if (nums[i] == 1) {
            i++;
        } else {
            swap(nums, i, two--);
        }
    }
}

复杂度是 O(n) 时间、O(1) 额外空间。面试重点通常不是代码长度，而是能否解释为什么遇到 2 后 i 不能加，以及三段区间的不变量。

完整版教学

一、这题为什么不该套通用排序

通用排序解决的是“任意可比较元素如何有序排列”，下界通常是 O(n log n)。颜色分类的输入只有 0、1、2 三个离散值，信息量非常低，因此可以利用值域固定这一前提做线性整理。面试官问这题，常常是在考你是否能先观察约束，而不是看到“排序”就直接调用库函数。

例如数组 [2,0,2,1,1,0]，真正要做的是把 0 推到左边、2 推到右边，剩下自然就是 1。它不要求稳定性，不要求比较器，也不要求保留相同颜色内部顺序，所以原地交换是可接受的。约束一旦变成“对象按颜色稳定排序”，答案就要改成计数后重写或稳定算法，这就是前提的重要性。

方案	时间	空间	是否一趟	适合回答
调库排序	O(n log n)	取决于库	否	不推荐，没利用值域
计数排序	O(n)	O(1)	两趟	简单但不是一趟
荷兰国旗	O(n)	O(1)	是	最常见面试答案

二、三段不变量是代码正确性的骨架

写这题前先不要急着写 if，先把数组分成四个区域：已经放好的 0 区、已经确认的 1 区、未知区、已经放好的 2 区。三个指针的含义是：zero 是下一个 0 应该落的位置，i 是当前检查的位置，two 是下一个 2 应该落的位置。

[0 ... zero-1] [zero ... i-1] [i ... two] [two+1 ... n-1]
     全是 0          全是 1        未知          全是 2

循环条件必须是 i <= two，因为 i == two 时仍有一个未知元素没看。循环结束时未知区为空，前三段自然拼成完整有序数组。这个不变量比背模板更可靠，因为任何交换后都能用它检查指针该不该移动。

记忆钩子：zero 管左边的 0，two 管右边的 2，i 只负责把未知元素“审判”成左、中、右三类。

三、遇到 0 为什么可以同时移动 zero 和 i

当 nums[i] == 0 时，0 应该进入左侧 0 区，于是交换 nums[i] 和 nums[zero]。交换后，zero 位置被填成 0，因此 zero++。那为什么 i 也能加？因为交换前 [zero..i-1] 全是 1，若 zero < i，换回到 i 的一定是 1；若 zero == i，只是自己和自己换，也已经处理完。

用 [1,0,2] 举例，初始 zero=0,i=0,two=2。先看到 1，i=1；再看到 0，和 zero=0 的 1 交换，数组变 [0,1,2]，此时 zero=1,i=2，中间的 1 已经确认过，不需要回头。这个细节是“0 分支可以 i++”的依据。

if (nums[i] == 0) {
    swap(nums, zero, i);
    zero++;
    i++;
}

四、遇到 2 为什么不能移动 i

当 nums[i] == 2 时，2 应该进入右侧 2 区，于是交换 nums[i] 和 nums[two]，然后 two--。但从右边换回来的元素属于未知区，可能是 0、1、2 中任意一个，不能跳过。如果此时 i++，就可能漏处理一个 0。

例子 [1,2,0] 很能说明问题：i=1 时看到 2，和 two=2 的 0 交换，数组变 [1,0,2]。如果错误地 i++，循环结束后得到 [1,0,2]，显然没排好。正确做法是 two-- 后继续检查当前位置 i=1，看到 0 再把它换到左边。

错误路径：
[1,2,0] -> 交换 2 和 0 -> [1,0,2] -> i 跳过 0 -> 失败
正确路径：
[1,2,0] -> 交换 2 和 0 -> [1,0,2] -> i 不动，继续处理 0

五、和快速排序三路划分有什么关系

荷兰国旗问题可以看成快速排序“三路划分”的最简版本。快速排序在大量重复值时，如果只做二路划分，会把等于 pivot 的元素反复递归，退化风险变高；三路划分会直接切出 < pivot、== pivot、> pivot 三段，等于 pivot 的中间段不再参与递归。

颜色分类中的 pivot 可以理解为 1：0 放左边，1 留中间，2 放右边。它之所以能一趟完成，是因为值域只有三个且目标顺序固定。如果扩展到任意整数的三路快排，仍然是同一类不变量，只是比较条件从 ==0/==2 变成 < pivot / > pivot。

场景	左段	中段	右段	价值
颜色分类	0	1	2	一趟原地排序
三路快排	小于 pivot	等于 pivot	大于 pivot	处理重复值更稳
分桶前处理	低优先级	中优先级	高优先级	原地分组

六、复杂度和边界怎么讲清楚

时间复杂度是 O(n)，因为每一步至少会让 i 右移或 two 左移，未知区 [i..two] 的长度严格减少。空间复杂度是 O(1)，因为只用了三个指针和常数次交换。它不是稳定排序，两个相同颜色对象的相对顺序可能因为远距离交换被打乱。

边界用例要覆盖空数组、单元素、全 0、全 2、已经有序、完全逆序、0 和 2 交替。例如 [2,2,2] 会不断和右端交换，two 左移直到 i > two；因为 i 不动但未知区在缩小，所以不会死循环。[0,0,0] 则每次 zero 和 i 同步右移，也不会越界。

未知区长度 = two - i + 1
遇到 0：i++，长度减少 1
遇到 1：i++，长度减少 1
遇到 2：two--，长度减少 1

七、常见误区与追问

误区：遇到 2 交换后也可以 i++。 右边换回来的元素还没检查，可能是 0；跳过会导致 [1,2,0] 这类用例失败。
误区：循环条件写成 i < two 更安全。 i == two 时仍有一个未知元素，少处理它可能留下逆序。
误区：这是计数排序的代码变体。 计数排序通常先统计再回填，两趟完成；荷兰国旗是原地一趟三路划分。
追问：如果要稳定排序怎么办？ 原地交换版不稳定；可以用计数后按原数组顺序写入新数组，或使用稳定排序，但会增加空间或时间成本。
追问：如果颜色有 k 种还能一趟吗？ k 很小时可以多指针或计数；k 较大时通常用计数排序、桶排序或通用排序，复杂度取决于值域和稳定性要求。
追问：它和快排有什么联系？ 它是三路 partition 的特殊场景；三路快排用同样思想处理大量重复 pivot。

八、加强记忆

记这题要抓住“未知区缩小”而不是背交换顺序。数组被切成 0 区 | 1 区 | 未知区 | 2 区，zero 是左边入口，two 是右边入口，i 是检查员。0 放左边后换回来的必然已处理，所以 i++；2 放右边后换回来的仍未知，所以 i 不动。只要能用这个不变量解释每次移动，代码边界和追问就都能稳住。

简化版

详细版