sort colors

class (object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        i = 0
        j = len(nums) - 1 # keep tracking the first !=2 pos
        k = 0 # keep tracking the first != 0 pos
        while i <= j and i >= k: # trick I, 要注意不要让i越界，否则怎会重复swap
            if nums[i] == 0:
                self.swap(nums, i, k)
                k += 1
                i += 1           
                # trick II，如果nums[i]是0，表示当前前面所有的 0 ～ i-1 
                # 已经按照01逻辑排好，所以swap的结果肯定是 1 和 0 或者0 和 0 的置换，
                # 而同样的规则在交换i, j的时候则不适用
            elif nums[i] == 2:
                self.swap(nums, i, j)
                j -= 1
            else:
                i += 1
        
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]