给定一个包含红色、白色和蓝色，一共n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:

不能使用代码库中的排序函数来解决这道题。

示例:

输入:[2,0,2,1,1,0]输出:[0,0,1,1,2,2]

打眼一看就是个排序的题，因为前阵子做个冒泡，这次写个快排。很久没写了，虽然快排的逻辑自己清楚，但是怎么用代码实现出来还是废了很大的功夫。

快速排序的原理是二分法，找一个基准数，先从右到左找比它小的，再从左到右找比它大的，然后这两个数交换位置，一直找到两边相遇。然后吧基准数置换到相遇位置。然后，从相遇的位置把列表分成两个列表，递归上面的操作，直到结束。

代码如下：

class Solution:

    def sortColors(self, nums: List[int]) -> None:

        """

        Do not return anything, modify nums in-place instead.

        """

        start = 0

        end = len(nums)-1

        self.QuickSort(nums, start, end)

    def QuickSort(self,myList, start, end):

        # 判断low是否小于high,如果为false,直接返回

        if start < end:

            i, j = start, end

            # 设置基准数

            base = myList[i]

            while i < j:

                # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现

                while (i < j) and (myList[j] >= base):

                    j = j - 1

                # 如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等

                myList[i] = myList[j]

                # 同样的方式比较前半区

                while (i < j) and (myList[i] <= base):

                    i = i + 1

                myList[j] = myList[i]

            # 做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base

            myList[i] = base

            # 递归前后半区

            self.QuickSort(myList, start, i - 1)

            self.QuickSort(myList, j + 1, end)