LeetCode 75 “颜色分类”Sort Colors是经典的荷兰国旗问题Dutch National Flag Problem。题目要求给定一个只包含“0”红、“1”白、“2”蓝的数组原地将其排序为“0、1、2” 的顺序且不能使用内置排序函数。解题思路三路快排Three-way Partitioning由于数组中只有三种取值我们可以用三个指针在一次遍历中完成排序“p0”指向下一个“0” 应该放置的位置0 区域的右边界“p2”指向下一个“2” 应该放置的位置2 区域的左边界“curr”当前正在遍历的元素遍历规则当“curr p2” 时如果“nums[curr] 0”将其与“nums[p0]” 交换“p0” 和“curr” 同时右移“curr” 移是因为换过来的要么是 0 要么是 1已经处理过了。如果“nums[curr] 1”直接“curr” 右移1 自然落在中间。如果“nums[curr] 2”将其与“nums[p2]” 交换仅“p2” 左移“curr” 不动因为从后面换过来的数还没检查过。Python3 实现一次遍历原地排序from typing import Listclass Solution:def sortColors(self, nums: List[int]) - None:“”Do not return anything, modify nums in-place instead.“”p0 0 # 0 区域的末尾指针p2 len(nums) - 1 # 2 区域的开头指针curr 0 # 当前遍历指针while curr p2: if nums[curr] 0: # 交换到 0 区域 nums[p0], nums[curr] nums[curr], nums[p0] p0 1 curr 1 elif nums[curr] 1: # 1 自然在中间直接跳过 curr 1 else: # nums[curr] 2 # 交换到 2 区域 nums[p2], nums[curr] nums[curr], nums[p2] p2 - 1 # 注意curr 不移动需要检查换过来的新元素其他解法参考方法二计数排序两次遍历虽然不符合“一次遍历”的优雅但非常直观且空间复杂度依然是“O(1)”因为只有3个颜色。class Solution:def sortColors(self, nums: List[int]) - None:count [0, 0, 0]for num in nums:count[num] 1idx 0 for i in range(3): for _ in range(count[i]): nums[idx] i idx 1方法三调用内置排序偷懒写法面试不推荐 nums.sort()复杂度分析方法 时间复杂度 空间复杂度 特点三路快排推荐“O(n)”“O(1)” 一次遍历原地交换面试满分答案计数排序“O(n)”“O(1)” 两次遍历逻辑简单适合快速实现内置排序“O(n log n)”“O(1)” 违反题目本意仅用于通过测试关键点总结为什么交换 2 的时候“curr” 不前进 因为“p2” 指向的是未处理区域的末尾交换后“curr” 位置换了一个来自数组后端的数这个数可能是“0”、“1” 或“2”需要重新判断。为什么交换 0 的时候“curr” 要前进 因为“p0” 指向的是已处理好的“0” 区域的下一个位置而“curr” 至少追平“p0”所以换过来的只可能是“0” 或“1”已经是排好序的可以放心前进。需要我帮你把这个算法改写成递归形式虽然这题迭代最优或者讲解类似题目如按奇偶排序数组的思路吗