sort-colors
sort-colors
https://www.nowcoder.com/questionTerminal/4345e55fdb03498a89a97ec18e62b3ab?f=discussion
问题描述：
现在有一个包含n个物体的数组，其中物体颜色为颜色为红色、白色或蓝色，请对这个数组进行排序，让相同颜色的物体相邻，颜色的顺序为红色，白色，蓝色。
我们用0,1,2分别代表颜色红，白，蓝
注意：
本题要求你不能使用排序库函数
思路：三路快排的思想，以1作为标志，比1小的放在一边，比1大的放在另一边，但是要注意一点的是大的元素进行交换后由于该元素没有和标志1作比较，因此需要i=i-1。
代码实现：
public class Solution {
public void sortColors(int[] A) {
int n=A.length;
int begin=0,end=n-1,lt=0,gt=n-1;
for(int i=0;i<=gt;i++){ //此处设为gt，而不是n
if(A[i]<1){
A[i]=A[lt];
A[lt]=0;
lt++;
}
else if(A[i]>1){
A[i]=A[gt];
A[gt]=2;
gt--;
i=i-1; //大的元素进行交换没有和1比较，需要i=i-1；
}
}
}
} 
投递BOSS直聘等公司6个岗位