14 三色排序练习题

有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。

给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等于500。

测试样例：

返回：[0,0,1,1,2,2]

思路：双指针

import java.util.*;

public class ThreeColor {
    public int[] sortThreeColor(int[] A, int n) {
      int index0=0;
      int index2=n-1;
        for(int i=0;i<=index2;i++){
          if(A[i]<1){

            swap(A,i,index0++);           
          }
          if(A[i]>1){
            swap(A,i, index2--);
            i--;
          }
        }
        return A;
    }
    public void swap(int[] A,int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}