排列颜色

这个问题被称为荷兰国旗问题：

解题思路：利用三个指针p0, curr, p2，其中p0指向0的右边界，p2指向2的左边界，curr指向当前元素。整个过程确保了[0,p0)的区间都是1，(p2, n-1]的区间都是2。

完整过程：

1. 将p0初始化为0，curr初始化为0，p2初始化为n-1
2. 如果curr <= p2:
   1. 如果A[curr]==0，交换curr和p0，将curr和p0都右移
   2. 如果A[curr]==2，交换curr和p2，将p2左移（curr不动）
   3. 如果A[curr]==1，将curr右移

代码如下：

//
// Created by jt on 2020/9/24.
//
#include <algorithm>
using namespace std;

class Solution {
public:
    void sortColors(int A[], int n) {
        int p0 = 0, curr = 0, p2 = n-1;
        while (curr <= p2) {
            if (A[curr] == 0) {
                swap(A[curr], A[p0]);
                ++curr;
                ++p0;
            } else if (A[curr] == 2) {
                swap(A[curr], A[p2]);
                --p2;
            } else ++curr;
        }
    }
};