Dutch Flag

荷兰国旗问题就是经典的三色排序，这个题比一般排序变化的地方在于实际上数组已经限定了只有三种不同的元素给你排，基于这个前提条件，排序的复杂度就从O(nlgn)下降到了O(n)，使用的方法就是一个活动指针加上两个类似墙壁的指针来实现，首先规定zero指针表示当前的零所到达的位置的前面一格，two表示当前的排好序的2到达的位置前面一格，然后利用活动指针cur来进行移动排序，当nums[cur]等于0时，我们需要与nums[zero + 1]的数进行互换，因为nums[zero + 1]肯定是之前比较过的数，且因为它在边界上，所以这个元素肯定是1不可能是零，我们将两数互换后就可以把zero加一格范围然后cur继续前进，当nums[cur]是一时，我们直接忽略继续前进，当nums[cur]是2时，我们要把当前元素与nums[two - 1]互换，这样就把2换到了后面，但要注意的是，此时换过来的元素是之前没有遍历过的，所以这种情况cur指针不能移动，必须原地继续进行比较，下面是代码

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        zero, two = -1, n
        cur = 0 

        while cur < two:
            if nums[cur] == 0:
                nums[cur], nums[zero + 1] = nums[zero + 1], nums[cur]
                zero += 1
                cur += 1
            elif nums[cur] == 1:
                cur += 1
            else:
                nums[cur], nums[two - 1] = nums[two - 1], nums[cur]
                two -= 1