Leet Code : Sort Colors.cpp

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

使用三个指示器 ：
i 存放0的位置
cur 当前处理的元素
j 存放2的位置

遍历0到j的位置，因为要处理0-n 但是j后面的元素已经都交换为2了，所以判断cur是否在j前面

遇到0 swap(A[++i],A[cur++]) 因为i的下一个位置为1所以交换后cur位置变为1 cur后移
遇到2 swap(A[ --j ],A[cur]) j的前一个位置未处理，可能为0 1 2 ，交换后继续处理所以cur不变
遇到1 cur++

 i   cur                               j
 ↓   ↓                                ↓
   |    |   |   |   |   |   |   |   |   |

         i   cur            j
         ↓   ↓             ↓
   |    |   |   |   |   |   |   |   |   |