颜色分类

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

双指针解法：

class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int leftVal = nums[left];
            int rightVal = nums[right];
            if(leftVal > rightVal){
                //左边比右边的数大就交换
                swap(nums,left,right);
            }
            //leftVal<=rightVal
            if(leftVal == 0 && rightVal == 2){
                left++;
                right--;
                continue;
            }
            if(rightVal == 2){
                right--;
                continue;
            }
            if(leftVal == 0){
                left++;
                continue;
            }
            if(leftVal == 1 && rightVal == 1){
                //从左往右找到一个不为1的数
                int tmp = left + 1;
                while(tmp != right && nums[tmp] == 1){
                    tmp++;
                }
                //如果tmp==right 说明left和right中间全是1  就不用再遍历了
                if(tmp == right)
                    break;
                //判断tmp位置的值
                if(nums[tmp] == 0){
                    //交换tmp和left
                    swap(nums,left,tmp);
                    left++;
                }else if(nums[tmp] == 2){
                    //交换tmp和right
                    swap(nums,tmp,right);
                    right--;
                }else{
                    //tmp==1
                    left++;
                }
            }
        }
    }


    private void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}