颜色分类，不靠“调色盘”：双指针 VS 计数排序的正面PK

颜色分类，不靠“调色盘”：双指针 VS 计数排序的正面PK

---

在算法圈混得久了，总有一些题目是面试官的心头好，刷题人绕不过的“鬼门关”。“颜色分类”（LeetCode 75）就是其中之一，看似小儿科，其实暗藏杀机。

你以为它就是个数组排序？错！这道题真要靠你用逻辑+策略去取胜，不是直接一个 sort() 一行干完的事。今天我就带你深入剖析两种主流解法：计数排序 和 双指针法（也叫三路快排变体）。

---

一、题目回顾：颜色分类到底想考啥？

原题描述：

给定一个包含红色、白色和蓝色（分别用 0、1 和 2 表示）的数组 nums，请你原地对它进行排序，使得相同颜色的元素相邻，并按照红、白、蓝的顺序排列。

举个栗子：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

听起来像个排序问题对吧？但重点来了：

要求原地排序，不能用库函数排序，且只遍历一次数组（或尽可能少次）。

这就限制了常规的快速排序、归并排序，逼得我们得从“计数”或“指针走位”下手。

---

二、解法一：计数排序，暴力但可靠

这个方法很像“先过一遍数一数颜色，再照着配色方案重刷一遍墙”。

思路：

1. 第一次遍历：统计 0、1、2 出现的次数；
2. 第二次遍历：按次数把对应颜色写回数组。

优点：

• 思路简单，代码易写，适合“开局不懂策略”的同学。

缺点：

• 遍历了两次数组，不够“优雅”；
• 如果换成 100 种颜色？你统计都得累死。

---

三、解法二：双指针法，经典且优雅

我们来重点聊聊这个算法圈“万金油”——双指针策略在本题的变体应用。

双指针本质上是一种左右协同、互不干扰的处理方式，用来在遍历中同时维护多个区段。

本题中，我们可以维护三段区域：

[0...p0] 全是0（红色）
[p0+1...i-1] 全是1（白色）
[i...p2] 未处理区域
[p2+1...n-1] 全是2（蓝色）

步骤：

1. 初始化指针 p0=0，i=0，p2=n-1；
2. 遍历数组时，根据当前值执行不同策略：
   • 如果是 0，交换到 p0 位置，p0 与 i 同时右移；
   • 如果是 2，交换到 p2 位置，p2 左移，i 不动（因为换过来的可能是 0，要再判断）；
   • 如果是 1，i 右移；
3. 遍历终止条件是 i > p2。

优点：

• 真·原地排序；
• 只遍历一次数组，效率高；
• 不依赖辅助数组或额外空间。

---

四、代码实现：每行都讲给你听

这里我把双指针法代码贴出来，并逐行解释：

def sortColors(nums):# p0指向应该放0的位置，p2指向应该放2的位置p0, i, p2 = 0, 0, len(nums) - 1while i <= p2:if nums[i] == 0:# 遇到0，和p0位置交换，0就安顿好了nums[i], nums[p0] = nums[p0], nums[i]p0 += 1i += 1elif nums[i] == 2:# 遇到2，和p2位置交换，但i不动（因为换来的不确定）nums[i], nums[p2] = nums[p2], nums[i]p2 -= 1else:# 遇到1就跳过，已经在中间的家了i += 1

举例演示：

比如 nums = [2,0,2,1,1,0]，

我们会经历以下几个状态：

• 初始：[2,0,2,1,1,0]
• 第一步：遇到2，换到末尾 → [0,0,2,1,1,2]
• 第二步：遇到0，换到p0 → [0,0,2,1,1,2]
• …
• 最终：[0,0,1,1,2,2]

是不是很像“三向切分的快速排序”？没错，这就是Dijkstra三路划分算法的具体应用。

---

五、什么时候选哪种方法？

场景	推荐算法	理由
颜色种类极少（0/1/2）	双指针法	高效，遍历一遍，原地处理
颜色种类多（如100种）	计数排序	可扩展性强，不容易混乱
不要求原地	普通排序	sort() 一行写完，图个快

---

六、最后总结一下，老朋友

“颜色分类”这题其实是一道考察“数组变换思维”的经典题，你可以把它当作：

• 熟悉双指针的训练场；
• 分区思想（类似荷兰国旗问题）的实战；
• 计数排序在小范围内的应用模型。

别小看这类题，它不是考你写出代码，而是考你理解数据结构如何流转，用最小的资源达到最优解。真正面试遇到类似题，你能当场写出三种方法，优缺点一说，HR多半当场就“哇哦”了。