Sort Colors 是 LeetCode Hot 100 里面一道非常经典的数组题。
这道题表面上是在“排序”，但它和一般的排序题又不太一样。因为数组中并不是任意整数，而是只会出现三种数字：
-
0 -
1 -
2
-
红色
-
白色
-
蓝色
要求你原地对数组进行排序，使得相同颜色的元素相邻，并按照红、白、蓝的顺序排列。
你给出的这份 Java 代码，使用的是这道题非常容易理解的一种做法：
计数排序
这种写法的核心思路非常直接：
-
先统计
0、1、2分别出现了多少次 -
再按数量把数组重写一遍
虽然这题还有一个更经典的进阶解法叫“荷兰国旗问题”，可以在一次遍历中完成排序，但从理解角度来说，你现在这份计数写法其实特别适合作为博客主解法来讲，因为它简单、清晰，而且很容易让读者一下子看懂。
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定一个包含红色、白色和蓝色，一共 n 个元素的数组 nums，要求你 原地 对它们进行排序，使得相同颜色的元素相邻，并且顺序为：
红色（0） -> 白色（1） -> 蓝色（2）
题目中使用数字来表示颜色：
-
0表示红色 -
1表示白色 -
2表示蓝色
例如：
nums = [2,0,2,1,1,0]
排序后应该变成：
[0,0,1,1,2,2]
这道题的关键点在于：
-
数组中只有三种取值
-
要求原地修改
-
不能直接调用库函数排序
示例
示例 1
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
因为数组中：
-
0有两个 -
1有两个 -
2有两个
所以重新排列后就是：
[0,0,1,1,2,2]
示例 2
输入：nums = [2,0,1]
输出：[0,1,2]
三个颜色各有一个，按顺序排好即可。
最直接的想法是什么？
如果不看题目的特殊结构，很多人第一反应可能是：
-
直接排序
-
或者自己写一个快排 / 归并排序
当然，这样也能把数组排好，但会显得有点“大材小用”。
因为这道题和普通排序题最大的不同在于：
数组中的元素只可能是 0、1、2 三种值。
既然取值范围这么小，我们其实完全没必要使用复杂排序。 更自然的思路应该是：
-
统计三种数字各出现几次
-
然后按照数量把它们重新填回数组
这就是计数排序思想。
核心思路：计数排序
你这份代码的核心可以概括成两步：
第一步：统计频率
先遍历数组，记录：
-
0出现多少次 -
1出现多少次 -
2出现多少次
第二步：重写数组
根据统计结果，把数组改写成：
-
前
cnt[0]个位置全部放0 -
接下来
cnt[1]个位置全部放1 -
最后
cnt[2]个位置全部放2
这样就完成了排序。
由于题目中元素取值范围非常小，这种做法既简单又高效。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public void sortColors(int[] nums) {
// cnt[0] 统计 0 的个数
// cnt[1] 统计 1 的个数
// cnt[2] 统计 2 的个数
int[] cnt = new int[3];
// 第一次遍历：统计每种颜色出现次数
for (int num : nums) cnt[num]++;
// 第二次遍历：按照计数结果重写数组
for (int i = 0; i < cnt[0]; i++) nums[i] = 0;
for (int i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;
for (int i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;
}
}
代码拆解
这段代码非常短，但它把“计数排序”的思想体现得很完整。 下面一步一步来看。
1. 为什么可以直接开一个大小为 3 的计数数组？
int[] cnt = new int[3];
因为题目已经保证，数组中的元素只会是：
-
0 -
1 -
2
所以我们只需要一个长度为 3 的数组，就可以把三种数字的出现次数全部记录下来：
-
cnt[0]表示 0 的数量 -
cnt[1]表示 1 的数量 -
cnt[2]表示 2 的数量
这一步的本质是：
把值域很小的排序问题，转化成频率统计问题。
2. 为什么 cnt[num]++ 就能统计频率？
for (int num : nums) cnt[num]++;
因为 num 的值只会是 0、1、2，所以它可以直接作为下标使用。
例如：
-
如果当前元素是
0，就执行cnt[0]++ -
如果当前元素是
1，就执行cnt[1]++ -
如果当前元素是
2，就执行cnt[2]++
假设数组是：
[2,0,2,1,1,0]
遍历结束后，cnt 的值就是：
cnt[0] = 2
cnt[1] = 2
cnt[2] = 2
这就表示三种颜色各出现了两次。
3. 为什么统计完之后可以直接重写数组？
因为排序的最终目标只是让数组变成：
所有 0 在前
所有 1 在中间
所有 2 在后
而一旦我们已经知道：
-
0 有多少个
-
1 有多少个
-
2 有多少个
那么数组的最终形态其实已经完全确定了。
例如：
cnt[0] = 2
cnt[1] = 3
cnt[2] = 1
那么结果一定是：
[0,0,1,1,1,2]
所以根本不需要再比较元素大小，直接按数量把数组写出来就可以了。
4. 为什么第一段循环写成这样？
for (int i = 0; i < cnt[0]; i++) nums[i] = 0;
因为前 cnt[0] 个位置都应该放 0。
例如如果 cnt[0] = 2，那么：
-
nums[0] = 0 -
nums[1] = 0
这样数组最前面就填好了所有红色。
5. 为什么第二段循环从 cnt[0] 开始？
for (int i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;
因为前面已经有 cnt[0] 个位置被 0 占掉了。 所以 1 的起始位置自然应该从：
cnt[0]
开始。
而 1 一共要写 cnt[1] 次，所以结束位置是：
cnt[0] + cnt[1] - 1
循环条件写成：
i < cnt[0] + cnt[1]
刚好覆盖这一段区间。
6. 为什么第三段循环从 cnt[0] + cnt[1] 开始？
for (int i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;
同理：
-
前面
cnt[0]个位置是 0 -
中间
cnt[1]个位置是 1
所以剩下的位置自然都应该填成 2。
而 2 的起始位置就是：
cnt[0] + cnt[1]
这也说明数组最终被分成了连续三段：
[0 .... 0][1 .... 1][2 .... 2]
手动模拟一遍
我们用经典例子来走一遍：
nums = [2,0,2,1,1,0]
第一步：统计次数
初始化：
cnt = [0,0,0]
遍历后得到：
-
0 出现 2 次
-
1 出现 2 次
-
2 出现 2 次
所以：
cnt = [2,2,2]
第二步：重写数组
先写 0：
nums[0] = 0
nums[1] = 0
数组变成：
[0,0,2,1,1,0]
再写 1：
nums[2] = 1
nums[3] = 1
数组变成：
[0,0,1,1,1,0]
最后写 2：
nums[4] = 2
nums[5] = 2
最终数组变成：
[0,0,1,1,2,2]
排序完成。
为什么这个方法是正确的？
因为这道题的数组元素只有三种值。 而“排序”对于这种特殊数组来说，其实并不需要真的比较元素大小，只需要保证：
-
所有 0 放在最前面
-
所有 1 放在中间
-
所有 2 放在最后面
一旦统计出这三种值各自的数量，数组最终的排列顺序就被唯一确定了。
因此：
-
统计阶段不会漏掉任何元素
-
重写阶段也不会多写或少写任何元素
-
最终结果一定满足题目要求
所以这个算法是完全正确的。
复杂度分析
时间复杂度
代码分成两次线性遍历：
-
第一次遍历统计频率
-
第二次遍历重写数组
因此总时间复杂度是：
O(n)
空间复杂度
额外只用了一个长度为 3 的数组 cnt：
O(1)
因为这个空间大小和输入规模 n 无关，是常数级。
这道题真正想考什么？
这道题表面上看是排序题，但本质上考察的是：
第一，能不能利用题目的特殊条件
很多人一看到“排序”就习惯性地想快排、归并排序。 但这道题中的值域只有 0、1、2 三种，所以最关键的并不是套通用排序模板，而是：
看出这是一个很适合计数的问题。
第二，是否理解“值域小”时可以考虑计数排序
计数排序并不是所有排序题都能用，但当数据范围很小、而且值域固定时，它往往会是非常高效的思路。
这也是这道题很值得掌握的一点。
这题为什么还经常提“荷兰国旗问题”？
因为这道题的官方进阶要求通常是：
-
只扫描一遍
-
使用常数空间
-
原地完成排序
而最经典的满足方式就是：
三指针 / 荷兰国旗问题
它的思路是：
-
用一个指针维护 0 区域
-
用一个指针维护 2 区域
-
当前指针扫描数组并交换元素
-
最终在一次遍历中完成分类
这个解法更“高级”，也是面试中更常被追问的版本。
不过从博客写作角度来说，你现在这份计数排序代码作为基础解法非常合适。 因为它更容易让读者先把题意和结构理解透。 等基础版本讲清楚后，再补一句“本题还有一个进阶的三指针做法”，会更完整。
和普通排序题有什么区别？
普通排序题通常面对的是：
-
任意整数
-
比较关系复杂
-
值域很大
而这道题非常特殊：
-
只有 0、1、2 三种值
-
值域极小
-
排序目标其实就是“分类”
所以它本质上更像一道“分类整理”题，而不是真正意义上的复杂排序题。
这也是为什么计数思路会比通用排序更自然。
总结
这道题的核心思想可以概括成一句话：
由于数组中只包含 0、1、2 三种值，所以可以先统计三种数字的出现次数，再按数量把数组重写成 0、1、2 三段。
具体步骤就是：
-
开一个长度为 3 的计数数组
-
遍历原数组，统计 0、1、2 的个数
-
前
cnt[0]个位置写 0 -
接下来
cnt[1]个位置写 1 -
最后
cnt[2]个位置写 2
这样就能在：
O(n)
的时间复杂度和：
O(1)
的空间复杂度下完成排序。
这是一道非常经典、也非常值得理解的数组题。 因为它会让你真正体会到：
-
做题时不要只盯着题目表面
-
关键是抓住数据的特殊结构
-
当值域很小的时候，计数往往比比较排序更自然
把这道题真正吃透之后，再去看：
-
前 K 个高频元素
-
数组中重复元素处理
-
桶排序 / 计数排序
-
荷兰国旗问题
这些题时，你会更容易意识到：
