数组：颜色分类（两路排序）

一个数组中，分别以0，1，2代表红、白、蓝三种颜色，要求对数组进行排序，使表示相同颜色的元素相邻，且按照红、白、蓝的顺序进行排序。

方法一：使用交换的方法，依次访问时，把0放到左边，把2放到右边，1不动，交换完成之后，排序就完成了

public void sortColors(int[] nums) {
        int red = 0, blue = nums.length - 1, i = 0;
        while(i <= blue){
            if(nums[i] == 0){ //交换后i并不改变，因为交换后i位置的元素还没有确定位置
                if(i == red){ //red的位置放置的就是0，不用动
                    i++;
                    red++;
                }
                else{ //把0交换到red的位置
                    int tmp = nums[i];
                    nums[i] = nums[red];
                    nums[red] = tmp;
                    red ++;
                }
            }
            else if(nums[i] == 2){ 
                if(i == blue){ //blue的位置就是2，不用动
                    i++;
                    blue--;
                }
                else{ //把2交换到blue的位置
                    int tmp = nums[i];
                    nums[i] = nums[blue];
                    nums[blue] = tmp;
                    blue --;
                }
            }
            else i++; //元素是1，不动，i往后移动
        }
    }

上面的方法还可以稍微简化：

public void sortColors(int[] nums) {
    // 1-pass
    int p1 = 0, p2 = nums.length - 1, index = 0;
    while (index <= p2) {
        if (nums[index] == 0) {
            nums[index] = nums[p1];
            nums[p1] = 0;
            p1++; //p1向后移动，index也向后移动，因为index前面的数据都已经排好序了，从p1交换过来的肯定是1
        }
        if (nums[index] == 2) {
            nums[index] = nums[p2];
            nums[p2] = 2;
            p2--; //p2向前移动，但index不动，因为交换过来的数据还未确定其位置，需再访问一遍
            index--;
        }
        index++;
    }
}

方法二：遍历一遍数组，分别计算数组中0、1和2的个数，然后直接把数组的三部分设置成相应个数的0、1、2。这种方法需要遍历两次，但每次遍历所做的操作较少。

void sortColors(int A[], int n) {
    int num0 = 0, num1 = 0, num2 = 0;
    
    for(int i = 0; i < n; i++) {
        if (A[i] == 0) ++num0;
        else if (A[i] == 1) ++num1;
        else if (A[i] == 2) ++num2;
    }
    
    for(int i = 0; i < num0; ++i) A[i] = 0;
    for(int i = 0; i < num1; ++i) A[num0+i] = 1;
    for(int i = 0; i < num2; ++i) A[num0+num1+i] = 2;
}

方法三：记录三种颜色的下标，遍历的时候，如果遇到0，则三个下标都往后移动一位，并且把数组中的所有遍历过的元素都往后移动一位（相当于在0下标的位置增加了一个0）；如果遇到1，则1和2的下标往后移动一位，把值为1和2的元素都往后移动一位（相当于在1下标的位置增加了一个1）；如果遇到2，则把2的下标和值往后移动（相当于在2下标位置增加了一个2）

void sortColors(int A[], int n) {
    int n0 = -1, n1 = -1, n2 = -1;
    for (int i = 0; i < n; ++i) {
        if (A[i] == 0) 
        {
            A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
        }
        else if (A[i] == 1) 
        {
            A[++n2] = 2; A[++n1] = 1;
        }
        else if (A[i] == 2) 
        {
            A[++n2] = 2;
        }
    }
}