描述

给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。我们可以使用整数 0，1 和 2 分别代表红，白，蓝。

注意事项

不能使用代码库中的排序函数来解决这个问题。排序需要在原数组中进行。

样例

给你数组 [1, 0, 1, 2], 需要将该数组原地排序为 [0, 1, 1, 2]。

挑战

一个相当直接的解决方案是使用计数排序扫描 2 遍的算法。首先，迭代数组计算 0,1,2 出现的次数，然后依次用 0,1,2 出现的次数去覆盖数组。你否能想出一个仅使用常数级额外空间复杂度且只扫描遍历一遍数组的算法？

代码

public class Solution {
    /*
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        // i 从第一个数开始遍历，代表当前数值点
        // pl 指向第一个不是 0 的数，pl 的左边应该全是 0
        // pr 指向第一个不是 2 的数，pr 的右边应该全是 2
        int pl = 0;
        int pr = nums.length - 1;
        int i = 0;
        // pr 指向的不是 2 所以要遍历 pr 位置，此处写 <=
        while (i <= pr) {
            if (nums[i] == 0) {
                // 因为左边点只有是 1 的时候直接跳过，2 的时候会处理，所以在 0 和 1 位置交换后直接进行 i++
                swap(pl, i, nums);
                i++;
                pl++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                /* 注意此处不能 i++， i 代表当前数值点
                 * nums[i] 和 nums[pr] 交换后，如果出现类似于 nums[i] =nums[pr] = 2 
                 * 说明当前交换除了执行 pr--外对左边值并未处理，应该针对当前值进行下一轮判断操作
                 * 如果直接 i++，数组毫无疑问会出现所有和 pr 交换完的点都没进行处理
                 */
                swap(pr, i, nums);
                pr--;
            }
        }
    }
    
    private void swap(int m, int n, int[] nums) {
        int temp = nums[m];
        nums[m] = nums[n];
        nums[n] = temp;
    }
}