2020--07--17 sort-colors

题目描述 现在有一个包含n个物体的数组，其中物体颜色为颜色为红色、白色或蓝色，请对这个数组进行排序，让相同颜色的物体相邻，颜色的顺序为红色，白色，蓝色。 我们用0,1,2分别代表颜色红，白，蓝 注意： 本题要求你不能使用排序库函数 扩展： 一个非常直接的解法是两步的计数排序的算法 首先：遍历一遍数组，记录0,1,2的数量，然后重写这个数组，先将0写入，再将1写入，再将2写入 你能给出一个只用一步，并且能在常数级空间复杂度解决这个问题的算法吗？

在用常数N的复杂度解决问题
首先，判断数组长度为1和2的情况，定义左右标记left和right
其次，用fori遍历数组，等于0和left交换，等于2和right交换，否则i才可以往后移动
最后注意的细节是循环结束条件应该是i<=right,i等于left并且此时为0时i可以直接往后移动

实现的代码：

public void swap(int[] A,int left,int right){
        int temp = A[left];
        A[left] = A[right];
        A[right] = temp;
    }
    public void sortColors(int[] A) {
        if (A.length==1)return;
        if (A.length==2)if (A[0]>A[1])swap(A,0,1);
        int left=0,right=A.length-1;
        for (int i = 0; i < A.length; ) {
            if(i<=right) {
                if (A[i] == 0&&i!=left) {
                    swap(A, i, left);
                    left++;
                } else if (A[i] == 2) {
                    swap(A, i, right);
                    right--;
                } else if (left==right){break;}
                else i++;
            }
            else
                break;
        }
    }