# 75 Sort Colors

給一個長度為n的陣列，裡面有0,1,2三種數字，將陣列中的數字依照0,1,2的順序排列。

最直覺的想法是數0,1,2各有多少個，再依照數量放0,1,2。

follow up要求one-pass和constant space，所以需要更聰明的作法。

首先，0全部都要放在最左邊，2要放在最右邊，1在中間。

所以每次讀到2就放到右邊，讀到0就放到左邊，應該是可行的。

用p0,p2兩個pointer分別指0和2的位置，idx用來讀取nums的每個element。

idx移動時有些小細節要注意：

1. idx讀到0時，根據p0紀錄的目前從前面數過來的最後一個0的下一個位置，將nums[idx]和nums[p0]交換，nums[p0]放的應該是1，如果是2的話，早就被放到最後面了。所以交換完之後，idx++ p0++
2. idx讀到2時，根據p2紀錄的目前從最後面數過來的最後一個2的下一個位置，將nums[idx]和nums[p2]交換，p2--，nums[p2]裡面放的不知道是0,1,2哪一個，所以idx不能動，要繼續把換過來的數字放到正確位置。
3. idx讀到1時，idx++。
4. 迴圈終止條件：idx<=p2，後面已經都是2了，不用再算。

完整程式碼：

public class Solution {
    public void sortColors(int[] nums) {
        /*
        Concept:
        0 should be put on left side, 2 should be put on right side, 1 should stay in the middle.
        Use p0=0,p2=nums.length-1 two pointer, point to the position of 0 and 2.
        use pointer index to go through nums.
        when nums[index] == 0, set nums[index] = nums[p0], nums[p0] = 0, p0++, index++
        when nums[index] == 2, set nums[index] = nums[p2], nums[p2] = 2, p2--
        when nums[index] == 1, index++
        */

        int p0 = 0, p2 = nums.length-1, idx = 0;
        while(idx<=p2){
            if(nums[idx]==0){
                nums[idx] = nums[p0];
                nums[p0] = 0;
                p0++; idx++;
            }else if(nums[idx]==2){
                nums[idx] = nums[p2];
                nums[p2] = 2;
                p2--;
            }else{
                idx++;
            }
        }
    }
}