Sort Colors
给你一个数组 nums，其中每个值都是 0、1 或 2，分别代表红色、白色和蓝色这三种颜色。请重新排列数组，让所有 0 排在最前面，然后是所有 1，最后是所有 2，并返回这个数组。不要使用库中的排序函数来解决这个问题。
函数
- numsinteger-array
- 这些颜色，每种颜色为 0、1 或 2
- 返回值integer-array
- 相同的值，先是所有 0，然后是所有 1，最后是所有 2
约束条件
1 ≤ nums.length ≤ 1.5 × 104- 每个
nums[i]都是0、1或2。 - 颜色可能缺失，数组中也可能只有一种颜色。
示例
- 输入
- nums = [2, 1, 0, 2, 0, 1, 1]
- 输出
- [0, 0, 1, 1, 1, 2, 2]
- 解释
- 数组中有两个 0、三个 1 和两个 2，所以结果正是如此：两个 0，接着是三个 1，然后是两个 2。
- 输入
- nums = [2, 0, 2]
- 输出
- [0, 2, 2]
- 解释
- 这里完全没有 1。唯一的 0 移到最前面，两个 2 跟在它后面。
- 输入
- nums = [1]
- 输出
- [1]
- 解释
- 单个值本来就已经有序，所以数组会保持不变。
进阶
如果颜色不是三种，而是 k 种，并且 k 远小于数组的长度，你会做哪些改动？
提示
逐个打开提示，每个都会多透露一点。
只会出现三种不同的值。这能让你做到什么，而通用排序做不到？
数出 0、1 和 2 的数量并重写数组，需要两趟扫描。对于其中一趟，想象三个区域同时扩展：前面是 0，中间是 1，后面是 2。
保留三个索引：
low、mid和high。读取nums[mid]：如果是 0，就与low交换；如果是 2，就与high交换；如果是 1，就保持不变。与high交换后，再次读取同一位置。
题解
只会出现 0、1 和 2，所以你可以统计它们的数量，再分两遍重写数组。用三个指针标记 0 的结束位置和 2 的开始位置，就能一遍遍历完成，在读取每个值时将它放到正确的位置。这种划分方法就是荷兰国旗算法。
手动进行冒泡排序
结果正确，但无法在最大的测试中运行完毕
思路
如果不使用排序库，基准就是自己编写的排序算法。冒泡排序会遍历数组，并交换任何顺序不对的相邻元素。每一轮都会把遇到的最大值移到末尾，因此经过 n-1 轮后，每个位置都已确定。
它大约会进行 n²/2 次比较：当 n = 1.5 × 10^4 时，比较次数超过 10^8，而且这些比较都没有利用只有三种值这一事实。
算法
- 对数组执行 n-1 轮遍历。
- 在每一轮中，比较所有尚未排定的相邻元素对
nums[j]和nums[j + 1]，如果左边的元素更大，就交换它们。 - 完成第
done轮后（从 0 开始计数），最后的done + 1个位置已确定最终值，因此下一轮会在这些位置之前停止。 - 返回
nums。
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums统计每种颜色的数量，然后重写
思路
相等的值可以互换，所以只需要关心它们的数量。在第一个示例中，两个 0、三个 1 和两个 2 已经确定了答案，你不需要移动任何值。
遍历一次数组，统计每个值的数量，然后从头开始覆盖它：count[0] 个 0，count[1] 个 1，count[2] 个 2。这就是计数排序。两次遍历和三个计数器，时间复杂度为 O(n)，空间复杂度为 O(1)。
算法
- 创建三个计数器，初始值都为 0。
- 读取每个值，并将对应计数器加 1。
- 从开头写入
count[0]个 0，接着写入count[1]个 1，再写入count[2]个 2。 - 返回
nums。
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return nums使用三个指针遍历一次（荷兰国旗问题）
思路
读取数组时，逐步划分出三个区域。low 之前的所有元素都是 0，从 low 开始到 mid 之前的所有元素都是 1，high 之后的所有元素都是 2，而 nums[mid] 到 nums[high] 之间的元素尚未读取。
读取 nums[mid]。如果是 1，它已经在对应的区域中，因此将 mid 向前移动。如果是 0，就和 nums[low] 交换，并将两者都向前移动：从 low 位置换回来的值是 1；如果还没遇到过 1，则是同一个 0，所以它已经在正确的位置上。如果是 2，就和 nums[high] 交换，并将 high 向后移动，但 mid 保持不动，因为从 high 位置换来的值还未读取。
每一步都会让 mid 向前移动，或让 high 向后移动，因此循环会在 n 步后结束。对于 [2, 0, 2]，第一个 2 会和最后一个元素交换，high 减到 1；索引 0 处仍然是 2，它会和 0 交换；之后 0 留在原位，得到 [0, 2, 2]。
算法
- 将
low = 0、mid = 0设为初始值，并将high设为最后一个索引。 - 当
mid ≤ high时，读取nums[mid]。 - 如果它是 0，就将它与
nums[low]交换，并将low和mid向右移动一步。 - 如果它是 1，就将
mid向右移动一步。 - 如果它是 2，就将它与
nums[high]交换，并将high向左移动一步。让mid保持原位。 - 返回
nums。
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
易错点和边界情况
- 与
high交换后将mid向前移动。交换后到达的值尚未读取：对于[1, 2, 0]，2 与 0 交换，跳过 0 后会返回[1, 0, 2]。 - 在
mid < high时循环。两者相遇时，该位置仍未读取：对于[1, 0]，循环会在读取 0 之前停止，并返回[1, 0]。 - 使用无符号索引时让
high降到 0 以下。对于只包含 2 的数组，例如[2]，high会变成 -1，这会导致 Rust 的usize下溢。应让high始终指向未读取部分之后的位置。
常见问题3
什么是荷兰国旗问题？
Edsger Dijkstra 提出了这个问题：将三种颜色的物体排成一行，颜色分别是荷兰国旗上的红、白、蓝，要求每种颜色都聚在一起，并且只通过交换、只遍历一遍来完成。颜色排序问题也是同一个问题，只不过使用 0、1 和 2，而他的解法是三指针划分。
Sort Colors 的时间复杂度和空间复杂度是多少？
单次遍历的答案耗时为 O(n)，因为每一步都会让未读取的部分缩小一个单元。它只使用 O(1) 的额外空间：三个索引和一个用于交换的临时值。计数排序的复杂度界限相同，但会读取数组两次。
计数排序可以作为 Sort Colors 的答案吗？
它满足 O(n) 时间和 O(1) 空间的要求，许多面试官会接受它作为初步答案。接下来，面试官可能会要求你只遍历一次。颜色很多时，计数是更好的方法，因为分区只会分成三组。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def sortColors(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [2, 1, 0, 2, 0, 1, 1]
预期输出
[0, 0, 1, 1, 1, 2, 2]