给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

解题思路

这道题也叫做 荷兰国旗问题 。

三指针法，将数组分为0区，1区，2区：

• 指针一：P0，指向0区的右边一个元素
• 指针二：P2，指向2区的左边一个元素
• 指针三：curr，用于遍历
  • 如果 curr 是 0，说明要去左边，跟P0交换， curr 和 P0 都++
  • 如果 curr 是 2，说明要去右边，跟P2交换， P2-- ，但 curr 不用，因为从右边 p2 换过来的数字还没有被检查过，所以 curr 需要停留在原地，并在下一次循环中检查这个新换过来的数
  • 如果 curr 是 1，说明它待在了正确的位置，直接 ++

Java实现

    public void sortColors(int[] nums) {
        if (nums.length <= 1){
            return;
        }
        int p0 = 0;
        int curr = 0;
        int p2 = nums.length - 1;
        while (curr <= p2){
            if (nums[curr] == 0){
                swap(nums, curr, p0);
                curr++;
                p0++;
            } else if (nums[curr] == 2){
                swap(nums, curr, p2);
                p2--;
            } else {
                curr++;
            }
        }
    }
    
    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }