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

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

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

    示例:

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

    进阶：

    • 一个直观的解决方案是使用计数排序的两趟扫描算法。

    首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

    • 你能想出一个仅使用常数空间的一趟扫描算法吗？

    • [x] 题解1

    按照计数排序来解比较容易理解，当然代码也比较容易编写

    1. class Solution:
    2.     def sortColors(self, nums: List[int]) -> None:
    3.         """
    4.         Do not return anything, modify nums in-place instead.
    5.         """
    6.         cnt0 = nums.count(0)
    7.         cnt1 = nums.count(1)
    8.         cnt2 = nums.count(2)
    9.         nums[:] = [0] * cnt0 + [1] * cnt1 + [2] * cnt2
    • 题解2

    对列表进行快速排序，而且快速排序是交换排序，不需要额外空间
    ❓ 在leetcode上执行下述代码的时候会提示超出递归深度的错误，但是使用官方提供的测试用例[2,0,2,1,1,0]，在本机上单独执行如下代码是可以输出正确结果的
    image.png
    关于快速排序：
    快速排序是一种交换排序。

    • 基本思想：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
    • 基本流程：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

    • 结合以上原理，快速排序函数需要如下三个参数：

      1. 待排序的序列
      2. 序列最小下标 left

      3. 序列最大下标 right

        1. class Solution:
        2. def quick_sort(self, lst, left, right):
        3.   if left >= right:
        4.       return 
        6.   low = left
        7.   high = right
        8.   base = lst[0]
        9.   while left < right:
        10.       while left < right and lst[right] > base:
        11.           right -= 1
        12.       lst[left] = lst[right]
        13.       while left < right and lst[left] <= base:
        14.           left += 1
        15.       lst[right] = lst[left]
        16.   lst[right] = base
        17.   self.quick_sort(lst, low, left - 1)
        18.   self.quick_sort(lst, left - 1, high)
        20. def sortColors(self, nums: List[int]) -> None:
        21.   """
        22.   Do not return anything, modify nums in-place instead.
        23.   """
        24.   self.quick_sort(nums, 0, len(nums) - 1)

    引用：
    [1]. 快速排序方法——python实现