颜色分类
Sort Colors
数组只含 0、1、2，原地排序，使相同数字相邻并按 0、1、2 排列。
在力扣中练习题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
解释：
该数组包含两个 0、两个 1 和两个 2。将它们原地排序后，所有 0 排在最前面，接着是所有 1，最后是所有 2。
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
解释：
数组中有且仅有一个 0、一个 1 和一个 2，按 0、1、2 的顺序原地排列。
提示：
n == nums.length1 <= n <= 300nums[i]为 0、1 或 2
进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
解题思路
三指针 · 一趟扫描
把数组分成“已定 0 / 未处理 / 已定 2”三段
最直接的做法是数出每个数字出现几次，再按次数重写数组：两趟扫描，时间 O(n)、空间 O(1)。但题目通常希望一趟完成，三指针可以做到。
维护三个边界：
[0, low)全是 0；[low, i)全是 1；(high, n-1]全是 2；[i, high]是还没检查的区域。
每一步看 nums[i]：
- 是 0：和
low交换，low++、i++； - 是 2：和
high交换，high--，i 不动； - 是 1：
i++。
自拟主例 [1,2,0,1,2,0] 中，第一个 2 换到右端后，换来的 0 还没检查，所以 i 必须留在原地；接着两个 0 连续归到左边，最后右端的 2 让 high 左移并结束。
nums[0] = 1：1 已经在中段，i 直接右移。
- low
- 0
- i
- 1
- high
- 5
nums[2] = 0：和 low 交换后归到左边，low 和 i 一起右移。
- low
- 2
- i
- 3
- high
- 4
时间 O(n)，空间 O(1)。
易错点
- 与 high 交换后也 i++：换过来的数还没检查，可能把 0 或 2 漏掉。
- 循环条件写成 i < n：high 之后的元素已经归位，继续扫描会打乱它们。
- low 与 i 的职责混淆：low 指向 0 区末尾，i 指向未处理区开头。
计数排序 · 两趟扫描
先数清楚 0/1/2 各几个，再按次数覆盖
时间同为 O(n)、空间 O(1)，但需要扫描两趟，且只适用于取值只有 3 种的情况；三指针是一趟原地交换。
因为取值只有 0、1、2，可以直接统计每个值出现的次数，然后按 0、1、2 的顺序把数组重写一遍。
第一趟计数，第二趟按 count[0]、count[1]、count[2] 依次写入。时间 O(n)，计数数组固定长度 3，空间 O(1)。
它比三指针更好写，但需要两趟；如果题目改成“一趟扫描”或“不能改变相对顺序”，就要换方法。
- 1count[3] 全部置 0。
- 2第一趟统计每个值出现次数。
- 3按 0、1、2 的顺序，把 count[v] 个 v 写回数组。
易错点
- count 下标越界：题目保证只有 0/1/2，若输入有其他值需要额外处理。
- 写回时用 nums[i] 而不是当前写入位置 k：会覆盖还没读取的计数。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [1,2,0,1,2,0]low = 0，i = 0，high = 5；待处理区间是 [low, high]，区间外已经归位。
- low
- 0
- i
- 0
- high
- 5
查看 C++ 代码
延伸阅读
- 三指针本质是快速排序的三路划分（Dutch national flag partition），也用于处理大量重复元素的快排优化。
- 如果颜色种类不是 3 而是 k，计数排序仍然是 O(n+k)；三指针只适合三类。