/**
*
* @author gentleKay
* Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
* Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
* Note:
* You are not suppose to use the library's sort function for this problem.
* click to show follow up.
* Follow up:
* A rather straight forward solution is a two-pass algorithm using counting sort.
* First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
* Could you come up with an one-pass algorithm using only constant space?
*
* 给定一个数组，其中n个对象的颜色为红色、白色或蓝色，对它们进行排序，使相同颜色的对象相邻，颜色的顺序为红色、白色和蓝色。
* 这里，我们将使用整数0、1和2分别表示红色、白色和蓝色。
* 注：
* 对于这个问题，您不应该使用库的排序函数。
* 单击以显示“跟进”。
* 跟进：
* 相当直接的解决方案是使用计数排序的两次通过算法。
* 首先，迭代数组计数数0、1和2，然后用总数0、1和2覆盖数组。
* 你能想出一个只使用常量空间的一次性算法吗？
*/
/**
*
* @author gentleKay
* Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
* Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
* Note:
* You are not suppose to use the library's sort function for this problem.
* click to show follow up.
* Follow up:
* A rather straight forward solution is a two-pass algorithm using counting sort.
* First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
* Could you come up with an one-pass algorithm using only constant space?
*
* 给定一个数组，其中n个对象的颜色为红色、白色或蓝色，对它们进行排序，使相同颜色的对象相邻，颜色的顺序为红色、白色和蓝色。
* 这里，我们将使用整数0、1和2分别表示红色、白色和蓝色。
* 注：
* 对于这个问题，您不应该使用库的排序函数。
* 单击以显示“跟进”。
* 跟进：
* 相当直接的解决方案是使用计数排序的两次通过算法。
* 首先，迭代数组计数数0、1和2，然后用总数0、1和2覆盖数组。
* 你能想出一个只使用常量空间的一次性算法吗？
*/
public class Main29 {
public static void main(String[] args) {
int[] A = {0,1,2,0,1,2,2,1,1,2,1,2,2,1,1,1,0,0};
Main29.sortColors(A);
for (int i=0;i<A.length;i++) {
System.out.print(A[i] + " ");
}
}
public static void sortColors(int[] A) {
int[] a = new int[A.length];
int count = 0;
if (A.length <= 0 ) {
return ;
}
for (int i=0;i<A.length;i++) {
if (A[i] == 0) {
a[count] = A[i];
count++;
continue;
}
}
for (int i=0;i<A.length;i++) {
if (A[i] == 1) {
a[count] = A[i];
count++;
continue;
}
}
for (int i=0;i<A.length;i++) {
if (A[i] == 2) {
a[count] = A[i];
count++;
continue;
}
}
for (int i=0;i<a.length;i++) {
A[i] = a[i];
}
}
}