/**
1. 最后的结果是所有的0在前, 所有的2在后,
    1.1 首先从后向前扫描0, 把所有0swap到头部
    1.2 最后从前向后扫描2, 把所有2swap到尾部

2. 有另一个成型的算法, 由dijkstra提出, 其实就是把1中内容聚合到一个循环中.
*/

class Solution {
    public void sortColors(int[] nums) {
        dijkstra(nums);
        // sort(nums);
    } 

    void dijkstra(int[] nums){
        if(nums == null || nums.length < 1) return;
        int n = nums.length, l = 0, r = n -1;
        for (int i = l ; i <= r ; i ++){
            if (nums[i] == 0) swap(nums, i, l++);
            else if (nums[i] == 2) swap(nums, i--, r--);
        }
    }

    void sort(int[] nums){
        if (nums == null || nums.length < 1) return;
        int n = nums.length;
        for (int i = n-1, j = 0; i >= j ; i--){
            if (nums[i] == 0){
                while (j < n && nums[j] == 0 ) j++;
                if (i > j) swap(nums, i, j++);
            }
        }

        for (int i = 0, j = n-1;  i <= j ; i ++){
            if (nums[i] == 2){
                while (j >= 0 && nums[j] == 2) j--;
                if (i < j) swap(nums, i, j--);
            }
        }
    }

    void swap (int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}