【LeetCode】0075 颜色分类

https://leetcode-cn.com/problems/sort-colors/

# -*- coding:utf-8 -*-

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n):
            for j in range(i, n):
                if nums[i] > nums[j]:
                    nums[i], nums[j] = nums[j], nums[i]
        return nums
if __name__ == '__main__':
    nums = [2, 0, 2, 1, 1, 0]
    print(Solution().sortColors(nums))

思路： 这道题应该是经典的荷兰国旗问题（虽然也是我后来才知道的233），从题意来说，这道题只要进行一下排序就可以了，因为数字比较小，也因为懒，就没写快排用的冒泡。

从这道题还了解了双路快排三路快排。

正常的快速排序是每一趟都会有一个元素放在最后的位置，在这个元素左右的元素依然是无序排列。

而双路排序不仅会将一个元素放在最后的位置，还会对其他元素进行一个大概的排序，比关键字小的在关键字左边，比关键字大的在右边。（也就是说比关键字小的直接扔到表头，比关键字大的直接扔到表尾）。

三路排序就更厉害了，不仅找比关键字大的，比关键字小的，还和关键字一样大的。