题目描述

现在有一个包含n个物体的数组，其中物体颜色为颜色为红色、白色或蓝色，请对这个数组进行排序，让相同颜色的物体相邻，颜色的顺序为红色，白色，蓝色。

我们用0,1,2分别代表颜色红，白，蓝

注意：

本题要求你不能使用排序库函数

扩展：

一个非常直接的解法是两步的计数排序的算法

首先：遍历一遍数组，记录0,1,2的数量，然后重写这个数组，先将0写入，再将1写入，再将2写入

你能给出一个只用一步，并且能在常数级空间复杂度解决这个问题的算法吗？

 public void sortColors(int[] A) {
       if(A==null || A.length==0){
           return;
       }
       int left=0; //左侧存放红色的下标
       int right=A.length-1; //右侧存放蓝色的下标
       for(int i=0;i<=right;i++){
           if(A[i]<1){//A[i]红色
              A[i] = A[left]; //A[left]不一定是红色
              A[left] = 0;//将当前红色A[i] 与 A[left]交换,此时A[left]是红色
              left++;
           }
           if(A[i]>1){//A[i]蓝色
               A[i] = A[right];
               A[right] = 2;//将当前的蓝色A[i] 与 A[right]交换
               right--;
               i--; //避免类似A[i-1]=白色，A[i]=红色 的情况
           }
       }
    }