75.|75. 颜色分类 75.颜色分类

75. 颜色分类问题给定一个包含红色、白色和蓝色，一共个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:

【75.|75. 颜色分类】输入:
输出:

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。

首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

你能想出一个仅使用常数空间的一趟扫描算法吗？

解法1（偷懒的办法）进阶中给出了一种解决方案。两次循环就可以完成。
代码1 java实现

class Solution { public void sortColors(int[] nums) { if (nums==null || nums.length<2) { return; } //数组中0的数量 int i=0; //数组中1的数量 int j=0; //数组中2的数量不需要计算，因为当i与j都是0时，剩下的肯定都是2 //开始第一次循环，获取i与j for(int n:nums) { if (n==0) { i++; } else if (n==1) { j++; } } //开始第二次循环，将0，1，2重新写入数组 for(int l = 0; l0) { nums[l]=0; } else if (j>0) { nums[l] = 1; } else { nums[l] = 2; } } } }

解法2 这其实就是荷兰国旗算法。算法如下：

设置三个指针，，接下来循环时分为三种情况处理：
- 当时，交换与的值，并且
- 当时，不做任何处理，
- 当时，交换与的值，并且

整体算法比较直观，需要注意的一点是，当前值为时，并不往前推进，而是停留在原地。这个的原因在于，如果,在本次交换后，，下一轮需要将交换给。因此，这种情况下不能往前推进。
还有一个需要注意的地方在于，就是循环的终止条件，如果没有思考清楚，那么很有可能就写成了，但是这种情况是错的。考虑这样一个输入数组,在第一轮的判断时，是走的如上第三种情况，这样在第二轮时就是1了，如果是的判断的话，那么这一步就跳出循环了。最终结果就是，第二个元素并没有参与到比较中来。所以循环的规则应该是。
代码2 java实现

class Solution { public void sortColors(int[] nums) { if (nums == null || nums.length < 2) { return; } //三个指针的初始化， int begin = 0, curr = 0, end = nums.length-1; //循环的判断条件见解法中的说明 while (curr <= end){ //第一种情况 if (nums[curr] == 0) { nums[curr] = nums[begin]; nums[begin] = 0; curr++; begin++; } else if (nums[curr] == 1) { //第二种情况 curr++; } else { nums[curr] = nums[end]; nums[end] = 2; end--; } } }