# LeetCode | Sort Colors（荷兰国旗问题）

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.

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?

``````class Solution {
public:
void sortColors(int A[], int n) {
int mid = Partition(A,0,n-1,0);
Partition(A,mid,n-1,1);
}

int Partition(int A[],int begin,int end,int key){
int i,j;

for(i = j = begin;j <= end;j++){
if(A[j] == key){
Swap(&A[i],&A[j]);
i++;
}
}
return i;
}

void Swap(int *a,int *b){
int temp = *a;
*a = *b;
*b = temp;
}
};``````

1、当j为1的时候，就j++，不进行交换

2、当j为0的时候，就和i处的元素交换，然后i++和j++。（这里的j++是因为保证了j前面的元素要么为0，要么为1，如果加强条件i==j时不交换，更省一点点时间

3、当j为2的时候，就和k处的元素交换，然后k–，但j不变，重新判断j处的新值（也可以判断k处的值再交换，不过增添了麻烦，直接交换比较好）

``````class Solution{
public:
void sortColors(int A[],int n){
int i,j,k;
i = j = 0;
k = n-1;

while(j<=k){
if(A[j] == 0){
if(i != j)
Swap(&A[i],&A[j]);
i++;
j++;
}else if(A[j] == 1) //该加else就必须加，不能单独形成else，不然这句j+1后，下句判断就以新的j来判断了
j++;
else{
Swap(&A[j],&A[k]);
k--;
}
}
}

void Swap(int *a,int *b){
int temp = *a;
*a = *b;
*b = temp;
}
};``````