颜色分类为什么用三指针？荷兰国旗问题怎么原地排序？

简化版

颜色分类用三指针维护三个区域：[0, low) 全是 0，[low, i) 全是 1，(high, n-1] 全是 2。i 扫描未知区，遇到 0 就和 low 交换并一起前进，遇到 1 只前进，遇到 2 就和 high 交换并缩小右区，但 i 不动。

详细版

这题要求原地把只含 0、1、2 的数组排好。通用排序没有利用值域只有三种的条件；计数排序能做但通常要两趟。荷兰国旗算法用一次扫描完成分类，核心是维护三个指针和四个区域。

low 指向下一个 0 应放的位置，high 指向下一个 2 应放的位置，i 指向当前待判断元素。当 nums[i] == 0，交换到左区，low++、i++；当 nums[i] == 1，它属于中间区，i++；当 nums[i] == 2，交换到右区，high--，但 i 不动，因为右侧换回来的元素仍然未知。

时间复杂度 O(n)，额外空间 O(1)。面试重点不是背分支，而是讲清区域不变量和“遇到 2 后为什么不移动 i”。

完整版教学

一、为什么这题不是普通排序题

数组元素只有 0、1、2，目标是按颜色分组，而不是比较任意两个元素的大小。若直接用库排序，复杂度通常是 O(n log n)，也没有体现面试官想考的“原地线性分类”。

计数排序可以先统计 0、1、2 的数量再回填，时间 O(n)、空间 O(1)，但它需要先数后写。荷兰国旗算法更像“边扫描边分发”，一次遍历就把未知元素放到正确区域。

记忆钩子：颜色分类不是“排序比较”，而是“未知区元素分发到 0 区、1 区、2 区”。

二、三个指针和四个区域

定义 low、i、high 后，数组被切成四段：

[0, low)        -> 全是 0
[low, i)        -> 全是 1
[i, high]       -> 未知区
(high, n - 1]   -> 全是 2

初始时 low=0, i=0, high=n-1，前三个已确认区域都是空，整个数组都是未知区。循环条件必须是 i <= high，因为 high 位置仍属于未知区，不能漏处理。

三、三种分支如何维护不变量

当前值	操作	指针变化	为什么
0	交换 `nums[i]` 与 `nums[low]`	`low++`, `i++`	0 进入左区，换回来的来自 1 区或自身
1	不交换	`i++`	1 本来就属于中间区
2	交换 `nums[i]` 与 `nums[high]`	`high--`	2 进入右区，换回来的元素仍未知

最后一行是高频错误点。右边换回来的可能是 0、1、2 任意值，如果交换后马上 i++，就会跳过一个未分类元素。

四、代码模板

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

代码中每个分支都在扩大一个已确认区域，同时缩小未知区。只要每轮都保持区域定义成立，循环结束时未知区为空，数组自然有序。

五、数字例子手推

以 [2,0,2,1,1,0] 为例：

low=0, i=0, high=5
[2,0,2,1,1,0]  nums[i]=2 -> swap i/high
[0,0,2,1,1,2]  high=4, i 不动
[0,0,2,1,1,2]  nums[i]=0 -> low=1, i=1
[0,0,2,1,1,2]  nums[i]=0 -> low=2, i=2
[0,0,2,1,1,2]  nums[i]=2 -> swap i/high
[0,0,1,1,2,2]  high=3, i 不动

第一次把 2 换到右边后，i 位置变成了 0；如果当时移动 i，这个 0 就会留在中间，结果出错。

六、和计数排序的对比

做法	时间	空间	扫描次数	特点
通用排序	O(n log n)	依实现	多次	没利用值域
计数回填	O(n)	O(1)	两趟	简单稳定
荷兰国旗	O(n)	O(1)	一趟	指针边界更考理解

经典颜色分类不要求稳定性，三指针交换是最常见答案。若题目额外要求稳定排序，就不能随意交换，需要换成稳定分区或计数回填。

七、常见误区与追问

误区：遇到 2 交换后也让 i++。 右侧换回来的元素没有检查，可能漏掉 0。
误区：循环条件写成 i < high。 i == high 时仍有一个未知元素要分类。
误区：low 左侧只是小于等于 1。 精确不变量是 [0,low) 全 0，[low,i) 全 1。
追问：遇到 0 为什么可以 i++？ 换到 i 的元素来自已确认的 1 区或自身，不会是未知元素。
追问：如果有 4 种颜色怎么办？ 面试中更推荐计数排序；强行多指针会显著增加边界复杂度。
追问：算法稳定吗？ 不稳定，因为交换可能改变元素的原始相对顺序。

八、加强记忆

荷兰国旗问题只记一个不变量：左边 0，中间 1，右边 2，i..high 是未知区。0 去左边，1 留中间，2 去右边；只有遇到 2 时 i 不动。把“为什么不动”讲清楚，这题就从背代码变成了会证明。

简化版

详细版