1. 问题背景与题目解析这道题目来自力扣LeetCode的HOT100系列编号T.75题目名为颜色分类。题目要求我们将一个包含红色、白色和蓝色元素的数组进行原地排序使得相同颜色的元素相邻且按照红色、白色、蓝色的顺序排列。在本题中我们使用整数0、1和2分别表示红色、白色和蓝色。这道题看似简单但它实际上是荷兰国旗问题的一个经典实例也是快速排序算法中partition过程的一个特例。理解这个问题的解法对于掌握快速排序的核心思想非常有帮助。注意题目要求必须在不使用库的sort函数的情况下完成原地排序这意味着我们需要手动实现排序逻辑。2. 快速排序与三指针法2.1 快速排序基础快速排序的核心思想是分治法通过选择一个基准元素将数组分成两部分一部分小于基准一部分大于基准然后递归地对这两部分进行排序。在标准的快速排序中partition过程通常使用双指针法选择一个基准元素通常是最后一个元素初始化一个指针i表示小于基准的区域的边界遍历数组将小于基准的元素交换到i的位置并递增i最后将基准元素放到正确的位置2.2 三指针法适应本题对于颜色分类问题我们需要将数组分成三个部分0、1、2因此标准的双指针partition需要扩展为三指针法left指针指向当前0元素应该插入的位置right指针指向当前2元素应该插入的位置current指针用于遍历数组算法流程初始化left0, rightn-1, current0当current right时循环 a. 如果nums[current] 0交换nums[current]和nums[left]left, current b. 如果nums[current] 1current c. 如果nums[current] 2交换nums[current]和nums[right]right--注意不增加current3. 算法实现与代码解析3.1 Java实现class Solution { public void sortColors(int[] nums) { int left 0, right nums.length - 1; int current 0; while (current right) { if (nums[current] 0) { swap(nums, current, left); left; current; } else if (nums[current] 1) { current; } else { swap(nums, current, right); right--; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } }3.2 代码解析初始化三个指针left始终指向下一个0应该放置的位置right始终指向下一个2应该放置的位置current用于遍历数组当current遇到0时将current位置的0交换到left位置因为left位置之前已经处理过所以可以安全地递增left和current当current遇到1时不做交换直接跳过1应该在中间区域只递增current指针当current遇到2时将current位置的2交换到right位置由于从right位置交换过来的元素可能是0或1所以不能递增current需要在下一次循环中重新检查关键点当交换2时不能增加current指针因为从right位置交换过来的元素可能还需要处理。4. 算法复杂度分析4.1 时间复杂度该算法只需要一次遍历数组每个元素最多被访问两次当交换2时可能被重新检查因此时间复杂度是O(n)其中n是数组的长度。4.2 空间复杂度算法只使用了常数个额外空间几个指针变量因此空间复杂度是O(1)满足题目要求的原地排序条件。5. 边界条件与测试用例5.1 常见测试用例基本用例输入[2,0,2,1,1,0]输出[0,0,1,1,2,2]已排序数组输入[0,0,1,1,2,2]输出[0,0,1,1,2,2]逆序数组输入[2,2,1,1,0,0]输出[0,0,1,1,2,2]全0数组输入[0,0,0]输出[0,0,0]全1数组输入[1,1,1]输出[1,1,1]全2数组输入[2,2,2]输出[2,2,2]空数组输入[]输出[]5.2 特殊边界情况单元素数组输入[1]输出[1]只有0和1输入[1,0,1,0]输出[0,0,1,1]只有1和2输入[1,2,2,1]输出[1,1,2,2]只有0和2输入[2,0,0,2]输出[0,0,2,2]6. 常见错误与调试技巧6.1 常见实现错误交换2后增加current指针错误可能导致未被检查的元素被跳过正确交换2后不应增加current因为从right交换过来的元素可能还需要处理循环条件错误错误使用current nums.length作为循环条件正确应该是current right因为right之后的元素已经处理过指针越界错误未检查数组为空的情况正确应首先检查数组长度是否为06.2 调试技巧打印中间状态在每次交换后打印数组和指针位置帮助理解算法执行过程使用小测试用例从最小可能的输入开始测试如[2,0,1]逐步增加复杂度边界测试特别注意全0、全1、全2的数组以及空数组和单元素数组7. 算法优化与变种7.1 计数排序法虽然三指针法是最优解但也可以使用计数排序的思路统计0、1、2的个数按照统计结果重写数组这种方法需要两次遍历虽然时间复杂度也是O(n)但不如三指针法优雅。7.2 多颜色分类问题如果颜色种类不止三种比如k种可以考虑使用k-1次partition将数组分成k部分或者使用计数排序7.3 快速排序的partition优化理解本题的三指针法可以帮助优化快速排序的partition过程特别是当数组中存在大量重复元素时。8. 实际应用场景颜色分类问题虽然简单但其解法在实际中有广泛应用快速排序优化处理大量重复元素的数组数据分类将数据分成几个类别进行处理图像处理像素值分类系统设计任务优先级调度9. 力扣HOT100打卡建议这道题作为HOT100系列的第14题是算法学习中的一个重要里程碑。以下是一些打卡建议理解优先不要满足于AC要真正理解三指针法的原理举一反三思考如何将这种方法应用到其他分区问题上多种实现尝试用不同语言实现该算法复杂度分析养成分析时间/空间复杂度的习惯测试驱动编写自己的测试用例验证算法正确性我在实际刷题中发现真正掌握这道题后对快速排序和各种分区问题的理解会有质的提升。建议在AC后可以尝试解决类似的partition问题如移动零、按奇偶排序数组等巩固这种解题思路。