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),从题意来说,这道题只要进行一下排序就可以了,因为数字比较小,也因为懒,就没写快排用的冒泡。

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

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

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

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

分类: 算法

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注