Sort Colors leetcode

Given an array with n objects colored red, white or blue, sort them 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.

第一种简便的算法, 只扫描一次 所以为O(n)

就是有两个指针 一个代表0 一个代表1 扫描的i代表2 

如果出现0 所有指针赋值并且往前走 遇到1 1指针和i往前走 遇到2 i往前走

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int index0 = 0;
        int index1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                nums[i] = 2;
                nums[index1++] = 1;
                nums[index0++] = 0;
            } else if (nums[i] == 1) {
                nums[i] = 2;
                nums[index1++] = 1;
            }
        }
    }
}

方法2 :
我们先用两个指针，一个指向已经排好序的0的序列的后一个点，一个指向已经排好序的2的序列的前一个点。这样在一开始，两个指针是指向头和尾的，因为我们还没有开始排序。然后我们遍历数组，当遇到0时，将其和0序列后面一个数交换，然后将0序列的指针向后移。当遇到2时，将其和2序列前面一个数交换，然后将2序列的指针向前移。遇到1时，不做处理。这样，当我们遍历到2序列开头时，实际上我们已经排好序了，因为所有0都被交换到了前面，所有2都被交换到了后面。时间复杂度O(n)

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }    
        int left = 0, right = nums.length - 1, i = 0;
        while (i <= right) {
            if (nums[i] == 0) {
                swap(nums, left, i);
                left++;
                i++;//指针从左边过来 所以左边是有序的
            } else if (nums[i] == 2) {
                swap(nums, right, i);
                right--;
            } else {
                i++;
            }
        }
    }
    private void swap(int[] nums, int i1, int i2){
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}

另外一种计数排序.首先便利一次统计每个元素的个数 然后根据颜色出现的次数分别对原数组进行修改.这个方法遍历数组两次.时间也是O(n)

public class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int[] colors = new int[3];
        for (int i = 0; i < nums.length; i++) {
            colors[nums[i]]++;
        }
        int index = 0;
        for (int i = 0; i < colors.length; i++) {
            for (int j = 0; j < colors[i]; j++) {
                nums[index] = i;
                index++;
            }
        }
    }
}