本文概览：本文讲解颜色分类（荷兰国旗问题）：只有 0、1、2 三个值，0 要排到最前面、2 要排到最后面，中间剩下的自然是 1；方法一是统计个数后重写，方法二用左右两个指针各守一端，一边遍历一边把 0 往左扔、2 往右扔，只需一遍扫描

一、题目

image-20260928093000001

二、题目分析

1. 题目要求

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

用整数 0、1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：nums = [2, 0, 2, 1, 1, 0] → [0, 0, 1, 1, 2, 2]

示例 2：nums = [2, 0, 1] → [0, 1, 2]

2. 怎么想这题？

题目说得很死：数组里只有 0、1、2 三种值，最后要排成"所有 0 在前面、所有 1 在中间、所有 2 在后面"。

最直接的做法是先数再填：扫一遍统计出 0、1、2 各有多少个，然后照着个数把数组从头到尾重写一遍。思路没问题，但要扫两遍数组。

还能不能再省？注意这里只有三个值，而且规矩特别简单：0 的归宿是最前面，2 的归宿是最后面，1 夹在中间——也就是说，只要把 0 和 2 都送对了地方，剩下的位置自然全是 1，压根不用管。

那就可以在遍历的过程中"边看边归位"：遇到 0 就往数组头部扔，遇到 2 就往数组尾部扔。既然要往两端扔，就得有两个指针分别记住"头部扔到哪了、尾部扔到哪了"。这就是双指针的思路，一遍扫描就能排好。

3. 需要解决哪几个问题？

问题一：两个指针各自指向哪里、分别代表什么含义？

问题二：遇到 0 或 2 时需要交换，交换之后两个指针和遍历下标分别怎么移动？

问题三（最容易错的细节）：为什么遇到 0 时遍历下标要往后走一格，遇到 2 时却要停在原地再看一次？

三、方法一：统计个数后重写，两遍遍历

1. 思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void sortColors(int[] nums) {
    int count0 = 0, count1 = 0, count2 = 0;
    // 第一遍：数出各有多少个
    for (int num : nums) {
        if (num == 0) count0++;
        else if (num == 1) count1++;
        else count2++;
    }
    // 第二遍：按个数把数组重新填满
    int idx = 0;
    for (int k = 0; k < count0; k++) nums[idx++] = 0;
    for (int k = 0; k < count1; k++) nums[idx++] = 1;
    for (int k = 0; k < count2; k++) nums[idx++] = 2;
}

思路简要说明：

  1. 第一遍统计：数出 0、1、2 各有多少个
  2. 第二遍填充：按 0、1、2 的个数依次覆盖回数组
  3. **时间复杂度 O(n)**，空间 O(1)（只用三个计数器）
  4. 缺点：要扫两遍数组

2. 思路详解

这个方法的逻辑和"桶排序"是一回事：既然知道了每种值该占多少格，直接按格子填就行了。

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

1
2
3
4
第一遍数完：count0 = 2, count1 = 2, count2 = 2
第二遍填充：前 2 格填 0 → [0, 0, _, _, _, _]
           接着 2 格填 1 → [0, 0, 1, 1, _, _]
           最后 2 格填 2 → [0, 0, 1, 1, 2, 2] ✓

简单可靠，代价是要遍历两遍。既然一趟就能解决，就值得往下想。

3. 复杂度分析

**时间复杂度 O(n)**：两遍线性扫描。

**空间复杂度 O(1)**：三个计数器。

四、能不能一遍扫完？

回顾一下刚才那个观察：0 的归宿是数组最左边，2 的归宿是最右边，而 1 只要站在中间就行。

既然两个"极端值"各有明确的目的地，那就可以一边遍历一边送它们回家：

  • 遇到 0，把它和当前最左边还没确定的位置交换——这样 0 就落到该去的地方，那个位置可以划进"0 区"了；
  • 遇到 2，把它和当前最右边还没确定的位置交换——2 就落到尾部，那个位置划进"2 区"；
  • 遇到 1，先别动它，让它在原地等着（等 0 和 2 都归位，它自然就落在中间了）。

于是需要两个指针，一个盯左、一个盯右，分别记录"0 区"和"2 区"已经推进到哪儿。下面是具体怎么落地。

五、方法二：双指针三路分区，一遍遍历

1. 思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void sortColors(int[] nums) {
    int left = 0;                    // 0 区的下一个空位
    int right = nums.length - 1;     // 2 区的上一个空位
    int i = 0;                       // 当前考察的位置
    while (i <= right) {
        if (nums[i] == 0) {
            // 把 0 换到左边界
            int temp = nums[i];
            nums[i] = nums[left];
            nums[left] = temp;
            left++;
            i++;
        } else if (nums[i] == 2) {
            // 把 2 换到右边界
            int temp = nums[i];
            nums[i] = nums[right];
            nums[right] = temp;
            right--;
        } else {
            // 是 1，留在原地，继续往后看
            i++;
        }
    }
}

思路简要说明：

  1. **left**：[0, left) 这一段已经全是 0，left 指向 0 区的下一个空位
  2. **right**：(right, n-1] 这一段已经全是 2，right 指向 2 区的上一个空位
  3. **i**：当前正在考察的位置，它前面的 [left, i) 全是 1
  4. **循环条件 i <= right**：[i, right] 才是还没处理的区间，i 越过 right 就说明处理完了
  5. **时间复杂度 O(n)**，空间 O(1)

2. 思路详解

第一步：两个指针 + 一个遍历下标，各自管什么？

把整个数组看成四段：

1
2
[ 0 区 ) [ 1 区 ) [ 待处理区 ] ( 2 区 ]
 0      left      i        right      n-1
  • [0, left)：已排好的 0，全是 0；
  • [left, i)：已排好的 1；
  • [i, right]：还没看过的部分；
  • (right, n-1]：已排好的 2。

每处理完一个元素，就把它塞进对应的段里，待处理区随之缩小。等 i > right，待处理区空了，整段数组就排好了。

第二步：三种情况分别怎么处理？

情况一：nums[i] == 0。 它该去最前面。把它和 nums[left] 交换——left 那个位置正是 0 区的下一个空位，换过去正好落位。然后 left++（0 区往前扩一格）、i++（这一位已经处理完了，往后看下一个）。

情况二：nums[i] == 2。 它该去最后面。把它和 nums[right] 交换——right 是 2 区的上一个空位，换过去落位。然后 right--（2 区往前扩一格）。

情况三：nums[i] == 1。 1 不用挪，让它待在原地即可，直接 i++ 往后看。等 0 和 2 各自归位，这些留在中间的 1 自然就聚成了中间的 1 区。

第三步：为什么 0 要 i++，2 却不 i++？

这是这个方法唯一值得琢磨的地方，关键看换过来的那个数是谁。

遇到 0 时，和 nums[left] 交换。而 left 永远落在 i 的左边（left ≤ i），它左边那段 [0, left) 全是 0、[left, i) 全是 1——所以 nums[left] 位置上待着的一定是一个 1（当 left < i 时），而这个 1 早就被考察过了（它属于已排好的 1 区）。换过来之后 nums[i] 变成了 1，这个 1 本来就该待在中间，不用再管，所以 i++ 可以直接往后走。

遇到 2 时，和 nums[right] 交换。而 right 永远在 i 的右边，它属于还没考察过的待处理区。也就是说，nums[right] 可能是 2、可能是 1、也可能是 0——换到 nums[i] 上的这个新值谁也不知道是什么。所以这一位必须留在原地重新考察一遍，此时 i 不能动。

一句话概括：0 换过来的是"已经看过的 1"，放心往前走；2 换过来的是"从没见过的数"，必须停下再看一眼。

第四步：完整执行过程

以示例 1，nums = [2, 0, 2, 1, 1, 0] 为例。初始 left = 0, right = 5, i = 0：

1
2
3
4
5
6
7
8
9
10
11
12
13
初始:  [2, 0, 2, 1, 1, 0]        left=0  right=5  i=0

i=0: nums[0]=2 → 和 nums[5] 换 → [0, 0, 2, 1, 1, 2]   right=4  i=0
     （换过来的是 0，还得再看，i 不动）
i=0: nums[0]=0 → 和 nums[0] 换（自己换自己）  → [0, 0, 2, 1, 1, 2]   left=1  i=1
i=1: nums[1]=0 → 和 nums[1] 换（自己换自己）  → [0, 0, 2, 1, 1, 2]   left=2  i=2
i=2: nums[2]=2 → 和 nums[4] 换 → [0, 0, 1, 1, 2, 2]   right=3  i=2
     （换过来的是 1，是刚看过的类型，但要按"未考察"处理，所以留在原地再看）
i=2: nums[2]=1 → 是 1，不挪，i=3
i=3: nums[3]=1 → 是 1，不挪，i=4
此时 i=4 > right=3，待处理区空了，循环结束

结果: [0, 0, 1, 1, 2, 2] ✓

再看示例 2，nums = [2, 0, 1]：

1
2
3
4
5
6
7
8
初始:  [2, 0, 1]        left=0  right=2  i=0

i=0: nums[0]=2 → 和 nums[2] 换 → [1, 0, 2]   right=1  i=0
i=0: nums[0]=1 → 是 1，i=1
i=1: nums[1]=0 → 和 nums[0] 换 → [0, 1, 2]   left=1  i=2
此时 i=2 > right=1，循环结束

结果: [0, 1, 2] ✓

可以看到 i=0 那一步：换过来的 1 还没被考察过，所以停在原地看了一下才发现它是 1，才往后走——这正是"2 不 i++"的必要性。

3. 复杂度分析

**时间复杂度 O(n)**：每个元素最多被处理常数次，i 一路向右、right 一路向左，合起来推进 O(n) 步。

**空间复杂度 O(1)**：只有三个下标变量，原地交换。

六、总结

方法 遍历次数 时间 空间 关键点
统计个数后重写 两遍 O(n) O(1) 先数再填，简单但要多扫一遍
双指针三路分区 一遍 O(n) O(1) 0 往左扔、2 往右扔，1 留在中间

这题的灵魂在于发现"只有三个值，而且两个极端值各有明确归宿"：

  • 0 该在最左、2 该在最右，所以用左右两个指针各守住一端；
  • 剩下的 1 不用管，它会被自然地夹在中间。

真正容易写错的是移动下标的时机：遇到 0 交换后 i++，因为换回来的一定是已经看过的 1；遇到 2 交换后 i 不动，因为从右边换回来的是一个从没考察过的数，必须重新判断。把这一点想通了，这个双指针就是标准的"荷兰国旗问题"解法（三路分区），只扫一遍、只用常数空间。