三色排序

题目

有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。
给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等于500。

测试样例：[0,1,1,0,2,2],6
返回：[0,0,1,1,2,2]

思路

类似快速排序的划分过程，维护一个0区间和2区间，分别从-1和数组长度n开始。在遍历数组A的过程当中，
如果遍历的数字等于0，则与0区间的下一个数字交换，交换的数字一定是1。
如果遍历的数字等于2，则与2区间的上一个数字交换,此时交换的数字可能是0,1,2，所以需要再对此数进行判断。

import java.util.*;

public class ThreeColor {
    public int[] sortThreeColor(int[] A, int n) {
        int zeroZone=-1;
        int twoZone=n;
        for(int i=0;i<twoZone;i++){
            if(A[i]==0) swap(A,i,++zeroZone);
            else if(A[i]==2) {swap(A,i,--twoZone);i--;}
        }
        return A;
    }
    
     private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}