75. sort colors 颜色分类
一、刷题内容
原题链接
https://leetcode-cn.com/problems/sort-colors/
内容描述
给定一个包含红色、白色和蓝色，一共 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]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]
提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
进阶：
你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？
二、解题方法
1.方法一：单指针
我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。
具体地，我们使用一个指针 ptr 表示「头部」的范围，ptr 中存储了一个整数，表示数组 nums 从位置 0 到位置 ptr−1 都属于「头部」。ptr 的初始值为 0，表示还没有数处于「头部」。
在第一次遍历中，我们从左向右遍历整个数组，如果找到了 0，那么就需要将 0 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 0 都被交换到「头部」的范围，并且「头部」只包含 0。
在第二次遍历中，我们从「头部」开始，从左向右遍历整个数组，如果找到了 1，那么就需要将 1 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 1 都被交换到「头部」的范围，并且都在 0 之后，此时 2 只出现在「头部」之外的位置，因此排序完成。
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
ptr = 0
for i in range(n):
if nums[i] == 0:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
for i in range(ptr, n):
if nums[i] == 1:
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。
2.方法二：双指针
方法一需要进行两次遍历，那么我们是否可以仅使用一次遍历呢？我们可以额外使用一个指针，即使用两个指针分别用来交换 0 和 1。
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0 = p1 = 0
for i in range(n):
if nums[i] == 1:
nums[i], nums[p1] = nums[p1], nums[i]
p1 += 1
elif nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
if p0 < p1:
nums[i], nums[p1] = nums[p1], nums[i]
p0 += 1
p1 += 1
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。
3.方法三：双指针
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0, p2 = 0, n - 1
i = 0
while i <= p2:
while i <= p2 and nums[i] == 2:
nums[i], nums[p2] = nums[p2], nums[i]
p2 -= 1
if nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
p0 += 1
i += 1
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。