颜色分类 图解题解

这道题真正在问什么

数组只含 0、1、2 三种值，要求原地按 0、1、2 的顺序排好，不许调库排序，并且最好一趟扫描完成。值域只有三个，套通用排序是杀鸡用牛刀——真正的考点是利用「只有三类」这个信息，把排序退化成「分区」：把每个数直接归进它所属的区域。这就是经典的荷兰国旗问题。

计数排序为什么还不够好

最直观的做法是计数排序：第一趟数出 0、1、2 各有几个，第二趟按个数把数组重新填一遍。它同样是 O(n) 时间、O(1) 空间，逻辑最简单，但要扫两趟。当题目或面试官追问「能不能只扫一趟」时，就需要边扫边把每个数当场放进正确的区域——这正是三指针的用武之地。

三个指针各自守住什么不变量

l 指向 0 区右侧的第一个空位，r 指向 2 区左侧的第一个空位，cur 是当前考察位置。全程保持四段结构：l 左边全是 0，l 到 cur 之间全是 1，cur 到 r 是尚未考察的未知区，r 右边全是 2。cur 每看一个数就把它归位：是 0 就和 l 交换（0 区长一格），是 2 就和 r 交换（2 区长一格），是 1 就正好留在中段、直接右移。当 cur 越过 r，未知区清空，三段区域收拢相接，数组自然有序——正确性全靠这组不变量每一步都不被破坏。

为什么遇 2 交换后 cur 不能前进

这是全题最关键的不对称。和 r 交换时，换过来的数来自右侧的未知区，可能是 0、1、2 中任何一个、还没被考察过，所以 cur 必须留在原地对新来的值再判一次，否则一个 0 可能被漏在中间。而和 l 交换时不同：l 始终不超过 cur，l 位置上的数属于已处理区域，只能是 1（或者 l 与 cur 重合时的自换），换过来不需要重判，cur 可以放心前进。可以这样记：从左边换来的是旧相识，从右边换来的是陌生人，陌生人必须重新过一遍安检。

复杂度与最容易踩的两个坑

cur 与 r 相向而行，合计把数组扫一遍，时间 O(n)；只用三个下标变量，原地交换，空间 O(1)。两个高频坑：一是循环条件必须写 cur <= r 而不是 cur < n——r 右边已经是排好的 2 区，越过 r 继续处理会把排好的 2 再换乱；二是遇 0 交换后忘了让 cur 前进——l 与 cur 重合时交换前后值不变，cur 不前进就会永远停在原地死循环。

Python

def sortColors(nums):
    l, cur, r = 0, 0, len(nums) - 1  # 0区右界 / 当前 / 2区左界
    while cur <= r:
        if nums[cur] == 0:           # 0 扔左边
            nums[l], nums[cur] = nums[cur], nums[l]
            l += 1; cur += 1
        elif nums[cur] == 2:         # 2 扔右边
            nums[cur], nums[r] = nums[r], nums[cur]
            r -= 1                   # cur 不动!
        else:                        # 1 留中间
            cur += 1

C++

void sortColors(vector<int>& nums){
    int l = 0, cur = 0, r = nums.size() - 1;
    while(cur <= r){
        if(nums[cur] == 0){          // 0 扔左边
            swap(nums[l], nums[cur]);
            l++; cur++;
        }else if(nums[cur] == 2){    // 2 扔右边
            swap(nums[cur], nums[r]);
            r--;                     // cur 不动!
        }else{                       // 1 留中间
            cur++;
        }
    }
}

Java

public void sortColors(int[] nums) {
    int l = 0, cur = 0, r = nums.length - 1;
    while (cur <= r) {
        if (nums[cur] == 0) {        // 0 扔左边
            int t = nums[l]; nums[l] = nums[cur]; nums[cur] = t;
            l++; cur++;
        } else if (nums[cur] == 2) { // 2 扔右边
            int t = nums[cur]; nums[cur] = nums[r]; nums[r] = t;
            r--;                     // cur 不动!
        } else {                     // 1 留中间
            cur++;
        }
    }
}