排列颜色

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length < 2)
            return;
        int l = -1;//0区的右边界
        int r = A.length;//2区的左边界
        int m = 0;//1区的右边界
        while(m < r){//当1区右边界和2区左边界相遇时停
            if(A[m] == 0){
                swap(A, ++l, m++);
            }else if(A[m] == 2){
                swap(A, m, --r);
            }else{//A[m] == 1
                m++;
            }
        }
    }
    
    public void swap(int[] arr, int i, int j){
        if(i != j){
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }
}

class Solution {
    public void sortColors(int[] nums) {
        //首先形式上：如果是考数组的算法 双指针算是常规套路了。。这个荷兰🇳🇱国旗问题用的三指针
        //其次 本质上 也还是蛮巧妙的。
        int p0, p1, p2, tmp;
        p0 = 0;
        p1 = 0;
        p2 = nums.length - 1;

        while(p1 <= p2){
            if(nums[p1] == 0){
                //如果p1对应的元素是0 交换p0和p1对应的元素,然后向后++一位
                tmp = nums[p0];
                nums[p0++] = nums[p1];
                nums[p1++] = tmp;
            }
            else if(nums[p1] == 2){
                //交换，--
                tmp = nums[p1];
                nums[p1] = nums[p2];
                nums[p2--] = tmp;
            }
            else{
                p1++;
            }
        }
    }
}

public class Solution {
    public void sortColors(int[] A) {
        int l1 = 0;
        //int l2 =  0;
        int l3 = 0;
        //创建新数组，拷贝原数组，原数组置1
        int[] a = new int[A.length];
        for(int i = 0;i<A.length;i++){
            a[i]=A[i];
            A[i]=1;
        } 
        //遍历新数组元素，遇到一个0，原数组前面的变0，遇到一个2，后面的变2
        for(int i = 0;i<a.length;i++){
            if(a[i]==0){
                A[l1]=0;
                l1++;
            }
            
            if(a[i]==2){
                A[A.length-l3-1]=2;
                l3++;
            }
        } 
        
    }
}

import java.util.Arrays;

public class Solution {
    public void sortColors(int[] A) {
        int zeroIndex = 0;
        int twoIndex = A.length - 1;
        int i = 0;
        while (i <= twoIndex) {
            if (A[i] == 0) {
                swap(A, i, zeroIndex);
                zeroIndex++;
                i++;
            } else if (A[i] == 2){
                swap(A, i, twoIndex);
                twoIndex--;
            } else {
                i++;
            }
        }
    }

    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

public class Solution {
    public void Swap(int A[], int i, int j)
    {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
    public void sortColors(int[] A) {
        //开始的一定为0；最后的一定为2
        int start = 0;
        int end = A.length-1;
        for(int i=0;i<=end;i++){
            if(A[i]==0){
                Swap(A,i,start++);
            }
            if(A[i]==2){
                Swap(A,end--,i);
                //end与i交换后需要重新比较一次i
                --i;
            }
        }
    }
}

public class Solution {
    public void sortColors(int[] A) {
        int length=A.length;
        if(length<2)
            return;
        int last=0;
        for(int count=0;count<3;count++)
        for(int i=last;i<length;i++){
            if(A[i]==count){
        int temp=A[last];
        A[last]=count;
        A[i]=temp;
        last++;
            }
        }
    }
}

public class Solution {
   public void sortColors(int[] A) {
		int begin = 0;
		int end = A.length - 1;
		int cur = 0;
		while (cur <= end) {
			// 所有的0放到数组前边
			if(A[cur] == 0) {
				A[cur] = A[begin] ^ A[cur] ^ (A[begin] = A[cur]);
				begin ++ ;
				cur ++ ;
			// 所有2放到数组后边
			} else if(A[cur] == 2) {
				A[cur] = A[end] ^ A[cur] ^ (A[end] = A[cur]);
				end -- ;
			} else cur ++ ;
		}
	}
}