1. 问题背景与核心挑战

颜色分类（Sort Colors）是LeetCode题库中的经典题目，编号75。题目要求对包含红、白、蓝三种颜色的数组进行原地排序，使得相同颜色相邻且按红、白、蓝顺序排列。这个问题看似简单，却蕴含着算法设计的精妙之处。

在实际开发中，类似场景比比皆是。比如电商平台的商品按价格区间分类、日志系统按紧急程度过滤消息，甚至游戏开发中按对象类型批量处理实体。理解这个问题的解法，能帮助我们掌握处理分类问题的通用思路。

题目给出的约束条件非常关键：

• 必须使用原地排序算法（空间复杂度O(1)）
• 只能遍历数组一次（时间复杂度O(n)）
• 颜色用整数0、1、2表示

这些限制排除了简单的计数排序和标准库sort方法，迫使我们寻找更巧妙的解决方案。

2. 解法一：双指针交换法

2.1 基本思路

双指针法是解决这类问题的黄金标准。我们维护两个指针：

• left指针：标记0（红色）的右边界
• right指针：标记2（蓝色）的左边界
• 当前指针i用于遍历数组

核心思想是通过交换操作将0移到左侧，2移到右侧，自然1就会留在中间。

public void sortColors(int[] nums) { int left = 0, right = nums.length - 1; int i = 0; while (i <= right) { if (nums[i] == 0) { swap(nums, left++, i++); } else if (nums[i] == 2) { swap(nums, right--, i); } else { i++; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

2.2 关键点解析

1. 边界条件处理：当nums[i]==2时，i不递增是因为交换过来的元素可能还是2
2. 循环终止条件：i <= right而非i < nums.length
3. 指针移动逻辑：只有确认当前元素是1时才移动i

注意：在面试中，面试官通常会要求解释为什么nums[i]==2时不递增i。这是最容易出错的地方，需要重点准备。

3. 解法二：计数排序变种

3.1 实现方案

虽然题目要求原地排序，但了解计数排序的变种对理解问题本质很有帮助：

public void sortColors(int[] nums) { int[] count = new int[3]; for (int num : nums) count[num]++; int index = 0; for (int i = 0; i < count.length; i++) { while (count[i]-- > 0) { nums[index++] = i; } } }

3.2 适用场景分析

这种方法虽然不满足题目要求，但在实际工程中：

• 当颜色种类固定且较少时（如本例的3种）
• 需要稳定排序时
• 允许使用额外空间时

是更直观且易维护的选择。面试时可以先提出这种解法，再优化为双指针法展示思维过程。

4. 算法复杂度对比

5. 边界条件与测试用例设计

完整的测试应该包含以下场景：

1. 空数组输入
2. 单元素数组
3. 全0/全1/全2数组
4. 已排序数组
5. 逆序数组
6. 随机混合数组
7. 超大数组（性能测试）

@Test public void testSortColors() { // 常规测试 int[] test1 = {2,0,2,1,1,0}; sortColors(test1); assertArrayEquals(new int[]{0,0,1,1,2,2}, test1); // 边界测试 int[] test2 = {2}; sortColors(test2); assertArrayEquals(new int[]{2}, test2); // 性能测试 int[] largeArray = new int[1000000]; // 填充测试数据... }

6. 实际工程应用案例

6.1 电商价格区间筛选

假设我们需要对商品按价格区间快速分类：

• 0-100元（0）
• 100-500元（1）
• 500元以上（2）

使用双指针法可以在用户滑动筛选条时实时更新商品列表。

6.2 日志级别过滤

系统日志通常分为：

• ERROR（0）
• WARN（1）
• INFO（2）

需要快速过滤显示特定级别的日志时，同样的算法可以高效处理。

7. 常见面试问题与回答策略

1. Q: 为什么nums[i]==2时不递增i？ A: 因为交换过来的元素可能还是2，需要再次检查。而交换0时我们可以确定换过来的只能是1（因为左边的都已经处理过）

2. Q: 如何证明算法的正确性？ A: 可以维护循环不变式：left左侧全是0，right右侧全是2，left到i之间全是1

3. Q: 如果颜色增加到5种怎么办？ A: 双指针法可以扩展为多指针，但更推荐使用计数排序或标准库sort

4. Q: 这个算法是稳定的吗？ A: 不是，相同颜色的相对顺序可能会改变。如果需要稳定排序，应该使用其他方法

8. 算法优化与变种

8.1 三指针实现

对于颜色种类更多的情况，可以扩展为三指针：

// 假设颜色为0,1,2,3 int low = 0, mid = 0, high = nums.length - 1; while (mid <= high) { if (nums[mid] == 0) { swap(nums, low++, mid++); } else if (nums[mid] == 1) { mid++; } else if (nums[mid] == 2) { swap(nums, mid, high--); } else { // 处理颜色3... } }

8.2 并行化处理

对于超大数组，可以考虑分块并行处理：

1. 将数组分成k个块
2. 每个线程统计自己块内的颜色计数
3. 汇总计数后计算每个块的写入位置
4. 并行执行写入

9. 与其他算法题的关联

颜色分类与以下算法题有密切联系：

1. 移动零（LeetCode 283）：可以看作只有0和非0两种"颜色"
2. 按奇偶排序数组（LeetCode 905）：二进制分类问题
3. 荷兰国旗问题：完全相同的题目

理解这些问题的共性，可以建立分类问题的通用解决框架。

10. 刷题建议与学习路径

对于准备面试的开发者，建议：

1. 先掌握基础的双指针实现
2. 理解算法正确性的证明方法
3. 练习各种边界条件的测试用例
4. 尝试用不同语言实现
5. 思考实际工程中的应用场景

进阶学习可以关注：

1. 多指针技巧
2. 并行算法优化
3. 稳定性与性能的权衡
4. 泛型实现（如果语言支持）

这个问题的价值不仅在于解法本身，更在于培养分类处理问题的思维方式。在实际工程中，类似的需求随处可见，掌握这类算法能显著提升代码效率和质量。