leetcodeday75 –颜色分类

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

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

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

快速排序：选定基准，大于基准的在右边，小于基准的在左边

快速排序(Quick Sort)是对冒泡排序的一种改进，其的基本思想:选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成（类比二叉树的思想)。

# @lc app=leetcode.cn id=75 lang=python3
#
# [75] 颜色分类
#

# @lc code=start
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def quick_sort(lists,i,j):
            if i >= j:
                return list
            pivot = lists[i]
            low = i
            high = j
            while i < j:
                while i < j and lists[j] >= pivot:
                    j -= 1
                lists[i]=lists[j]
                while i < j and lists[i] <=pivot:
                    i += 1
                lists[j]=lists[i]
            lists[j] = pivot
            quick_sort(lists,low,i-1)
            quick_sort(lists,i+1,high)
            return lists

        quick_sort(nums,0, len(nums) - 1)
# @lc code=end