颜色排序

描述

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

样例

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

标签

数组&排序&双指针

相关题目

分割数组 & 摆动排序 & 摆动排序2 & 颜色排序2

代码实现

class Solution {
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     * 
     * 假设数组nums 索引值0之前全是0，索引值nums.length-1右边全是2
     * 
     */
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int left = 0;
        int right = nums.length-1;
        int i = 0;
        while (i <= right) {
            //i=right有可能需要再进行调换,因为有可能原始的最后一个是2，被调换至前面
            if (nums[i] == 1) {
                i++;
            } else if(nums[i] == 0) {
                swap(nums, i, left);
                left++;
                i++;
            } else {
                swap(nums, i, right);
                right--;
                /* 不能i++，因为从右调过来的数可能是0 或者2
                *i++就 会直接跳过
                */
            }
        }
    }
    private void swap(int[] a,int i,int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}