1. 题目解析与需求拆解
这道题目要求我们对一个仅包含0、1、2三种元素的数组进行原地排序，使得所有0排在前面，1居中，2在末尾。题目有几个关键约束条件：
- 必须原地排序，不能使用额外空间（空间复杂度O(1)）
- 不能直接调用语言内置的排序函数
- 数组长度n的范围是1到300
在实际工程中，这类问题常见于需要快速分类的场景，比如电商平台根据商品状态（未上架/在售/已下架）进行筛选，或者日志系统中根据优先级（低/中/高）快速过滤信息。
2. 计数排序法详解
2.1 算法原理与实现
计数法的核心思想是先统计每种颜色出现的次数，然后按照0、1、2的顺序重新填充数组。这种方法的优势在于思路直观，容易理解和实现。
class Solution { public void sortColors(int[] nums) { int red = 0, white = 0, blue = 0; // 第一次遍历：统计各颜色数量 for (int num : nums) { if (num == 0) red++; else if (num == 1) white++; else blue++; } // 第二次遍历：重新填充数组 Arrays.fill(nums, 0, red, 0); Arrays.fill(nums, red, red + white, 1); Arrays.fill(nums, red + white, nums.length, 2); } }2.2 时间复杂度分析
- 第一次遍历：O(n)时间统计颜色数量
- 第二次填充：虽然看起来是三个操作，但每个元素只被写入一次，总体仍是O(n)
- 总时间复杂度：O(2n) = O(n)
注意：Arrays.fill()内部实现也是线性时间，但因为它只涉及内存写入，实际运行时会比常规遍历快很多。
2.3 适用场景与局限性
计数法特别适合：
- 元素取值范围很小且已知的情况
- 需要稳定排序的场景（虽然本题不要求）
- 对代码可读性要求较高的场景
局限性在于：
- 需要两次遍历（虽然时间复杂度相同）
- 对于元素取值范围大的情况不适用
3. 双指针法深度解析
3.1 算法原理与实现
双指针法通过维护两个指针p0和p2，分别表示下一个0应该存放的位置和下一个2应该存放的位置。遍历数组时，将遇到的0交换到p0位置，将遇到的2交换到p2位置。
class Solution { public void sortColors(int[] nums) { int p0 = 0, p2 = nums.length - 1; for (int i = 0; i <= p2; ) { if (nums[i] == 2) { swap(nums, i, p2--); } else if (nums[i] == 0) { swap(nums, i++, p0++); } else { i++; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }3.2 关键点与易错点
循环条件：必须是i <= p2而非i < nums.length。因为p2后面的元素已经确定是2，无需再处理。
交换顺序：遇到2时要先处理，因为从p2位置交换回来的元素可能是0或1，需要后续处理。
指针移动：
- 交换0后，i和p0都要前进（因为交换回来的元素只能是1）
- 交换2后，只有p2后退，i不前进（因为交换回来的元素需要重新检查）
3.3 时间复杂度分析
- 单次遍历：每个元素最多被交换两次（一次到头部，一次到尾部）
- 时间复杂度：O(n)
- 空间复杂度：O(1)
4. 两种方法的对比与选择
| 特性 | 计数法 | 双指针法 |
|---|---|---|
| 遍历次数 | 2次 | 1次 |
| 交换操作 | 无交换，直接填充 | 需要交换元素 |
| 代码复杂度 | 简单 | 中等 |
| 适用性 | 元素范围小 | 通用性更强 |
| 稳定性 | 稳定 | 不稳定 |
实际选择建议：
- 面试中优先展示双指针法（更能体现算法思维）
- 工程中如果元素种类固定且少，计数法更可靠
- 如果要求稳定排序，只能选择计数法
5. 常见问题与调试技巧
5.1 边界条件测试
最小输入测试：
Input: [0] Output: [0] Input: [1] Output: [1] Input: [2] Output: [2]已排序输入：
Input: [0,0,1,1,2,2] Output: [0,0,1,1,2,2]极端分布：
Input: [2,2,2,0,0,0] Output: [0,0,0,2,2,2]
5.2 调试技巧
打印指针位置：
System.out.println("i=" + i + " p0=" + p0 + " p2=" + p2);可视化交换过程：
初始: [2,0,2,1,1,0] i=0: 交换2到末尾 → [0,0,2,1,1,2] (p2=4) i=0: 是0，交换到p0 → [0,0,2,1,1,2] (p0=1) i=1: 是0，交换到p0 → [0,0,2,1,1,2] (p0=2) i=2: 是2，交换到p2 → [0,0,1,1,2,2] (p2=3) i=2: 是1，不处理
5.3 性能优化
对于双指针法，当p0和p2相遇时可以提前终止：
while (i <= p2 && p0 <= p2) { // ...原有逻辑... }对于计数法，如果检测到已经有序可以提前返回：
boolean isSorted = true; for (int i = 1; i < nums.length; i++) { if (nums[i] < nums[i-1]) { isSorted = false; break; } } if (isSorted) return;
6. 实际工程应用扩展
虽然题目简单，但类似的分类思想在工程中有广泛应用：
- 日志分级处理：将DEBUG/INFO/WARNING/ERROR日志分开处理
- 订单状态筛选：待支付/已支付/已发货/已完成订单分类
- 用户画像：根据活跃度将用户分为高/中/低活跃组
在更复杂的场景中，可以扩展为：
- 多指针分类（3种以上类别）
- 结合快速排序的分区思想
- 并行化处理大规模数据
我在实际项目中曾用类似方法处理过千万级用户标签数据，通过将分类逻辑改为非递归实现并加入批量处理，性能提升了40%。关键是要根据数据特征选择合适的分区策略，有时简单的计数法反而比复杂算法更高效。
