Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

lc 75

三路归并典型思路，lc就三题除了这一题就是wiggle sort

class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int start = 0;
        int end = nums.length - 1;
        int i = 0;
        while (i <= end) {
            if (nums[i] < 1) {
                int temp = nums[i];
                nums[i] = nums[start];
                nums[start] = temp;
                start++;
                i++;
            } else if (nums[i] > 1) {
                int temp = nums[i];
                nums[i] = nums[end];
                nums[end] = temp;
                end--;
            } else {
                i++;
            }
        }
    }
}

class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int[] count = new int[3];
        int[] res = new int[nums.length];
        //count
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]] ++;
        }
        //accumate to generate stop index
        for (int i = 1; i < 3; i++) {
            count[i] += count [i - 1]; 
        }
        //generate start index
        for (int i = 2; i > 0; i--) {
            count[i] = count [i - 1]; 
        }
        count [0] = 0;
        //start to count
        for (int i = 0; i < nums.length; i++) {
            int index = count[nums[i]];
            res[index] = nums[i];
            count[nums[i]]++;
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = res[i];
        }
    }
}