颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors

解法一 两次遍历

分析

第一次遍历，找出所有红色，放在数组前面；第二次遍历，找出蓝色，放在数组后面，剩下的就是白色。

代码

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int index = 0;
        for(int i=0;i<n;i++){
            if(nums[i]==0){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
        index = n-1;
        for(int i=n-1;i>=0;i--){
            if(nums[i]==2){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index--;
            }
        }
    }
}

方法二 一次遍历

分析

使用双指针，指针p0来交换0，p2来交换2，p0从左往右，p2从右往左。注意：找到2之后要不断与nums[p2]交换，直到不再为2。要先交换2再交换0。

代码

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, p2 = nums.length-1;
        for(int i=0;i<nums.length;i++){
            while(nums[i]==2&&i<=p2){
                int temp = nums[p2];
                nums[p2] = nums[i];
                nums[i] = temp;
                p2--;
            }
            if(nums[i]==0){
                int temp = nums[p0];
                nums[p0] = nums[i];
                nums[i] = temp;
                p0++;
            }
        }
    }
}