leetcoad链接：https://leetcode-cn.com/problems/sort-colors/
视频链接：https://www.algomooc.com/567.html
方法一：暴力解法

方法二：双指针
解题思路：不能重新构建新的数组，可以将输出的结果划分为三份，设置两个标定点，标定点左边位置是0，标定点的右边位置都是2

1. left指针，指向数组开始的位置，它指向的位置的左侧都是0
2. right指针，它指向数组结束的位置，它指向的位置的右侧都是2
3. index指针：指向数组开始的位置
4. index指针向后移动，越过right指针的时候，就可以跳出循环，不需要再进行相应的判断了（这里的理解很重要：因为前面已经锁定right指针右边都是2了）
   • 获取当前元素的值:cur = nums[index]
   • 如果index位置上的元素为0
     1. 说明是红色的，放在最前面去，让index指向的元素和left指向位置上的元素进行交换
     2. 同时让index和left都要向后面进行移动
   • 如果Index位置上的元素是1
     • 说明是白色，不用管，然后继续移动index
   • 如果index位置上的值是2
     1. 说明是蓝色，需要放到后面去
     2. 让index指针指向的元素和right指针指向的元素进行交换

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        left, index = 0 , 0

        right = len(nums) - 1

        while index <= right:
            cur = nums[index]
            if cur ==0:
                self.swap(nums,index,left)
                index +=1
                left +=1
            if cur == 1:
                index +=1
            if cur ==2:
                self.swap(nums,index,right)
                right -=1

    def swap(self, nums: List[int],i:int,j:int):
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp