題目
有一個(gè)只由0挫以，1，2三種元素構(gòu)成的整數(shù)數(shù)組窃祝，請(qǐng)使用交換掐松、原地排序而不是使用計(jì)數(shù)進(jìn)行排序。
給定一個(gè)只含0粪小，1大磺，2的整數(shù)數(shù)組A及它的大小，請(qǐng)返回排序后的數(shù)組糕再。保證數(shù)組大小小于等于500量没。
測(cè)試樣例：[0,1,1,0,2,2],6
返回：[0,0,1,1,2,2]
思路
類似快速排序的劃分過程玉转，維護(hù)一個(gè)0區(qū)間和2區(qū)間突想，分別從-1和數(shù)組長(zhǎng)度n開始。在遍歷數(shù)組A的過程當(dāng)中究抓，
如果遍歷的數(shù)字等于0猾担，則與0區(qū)間的下一個(gè)數(shù)字交換，交換的數(shù)字一定是1刺下。
如果遍歷的數(shù)字等于2绑嘹，則與2區(qū)間的上一個(gè)數(shù)字交換,此時(shí)交換的數(shù)字可能是0,1,2，所以需要再對(duì)此數(shù)進(jìn)行判斷橘茉。
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;
}
}
