Sort Colors

直白表述：给定一个数组，元素值只可能是0,1,2构成，其数组的组成随机，即三种元素混杂无序，找到一个算法，只借用固定量的外部空间，在一次遍历后，将数组成为升序。

说白了就是这么个问题。

我们需要的是0要排在前面，2呢就排在后面，1就不动，这样就好了，但是往前排往后排我们一般的都需要移动元素，这就不好了，题目要求一遍遍历，并且空间一定，那就只能交换了，具体怎么交换呢？就需要用到指示位，告诉我们从哪以前都是0，从哪以后都是2，当然夹在中间的就是1了。所以我们就遍历中间的部分，是0就跟前面 的交换，是2就跟后面的交换，1就跳过。

class Solution {
public:
    void sortColors(int A[], int n) {
       int r = 0;
       int j = 0;
       int b = n - 1;
       for(; j <= b;){
           if(A[j] == 0)//red
           swap(A[r++], A[j++]);
           else if(A[j] == 2)//blue
           swap(A[j], A[b--]);
           else ++j;//write
       }
    }
};

Sort Colors

原文：http://blog.csdn.net/shiquxinkong/article/details/18627339