京公网安备11010502063487号给定一个只含 0、1、2 的数组（分别代表红、白、蓝），原地排序，让相同的颜色相邻并按 0、1、2 的顺序排列，不允许使用库里的排序函数。最直接的想法是计数排序：扫描一遍数出 0、1、2 各有几个，再扫描一遍写回去。荷兰国旗算法只需要一遍扫描：用三个指针把数组分成四段，[0, lo) 全是 0，[lo, i) 全是 1，[i, hi] 是还没处理的，(hi, 末尾] 全是 2。本文用真实数据展示"与 2 交换之后指针前进"这个细节错误会造成多少排序错误，比较三种做法的真实耗时，给出五种语言的实现，并把三个指针的移动做成分步演示。
完整题目见官方页面（链接在文末）。基准解就是直接排序（sorted），与荷兰国旗的指针交换完全不同。一共 14 组用例，覆盖：官方两个示例、单个元素、全是同一种颜色、逆序、顺序、需要多次交换的乱序：
输入 [[2,0,2,1,1,0]] 输出 [0,0,1,1,2,2] 输入 [[2,0,1]] 输出 [0,1,2] 输入 [[0]] 输出 [0] 输入 [[1]] 输出 [1] 输入 [[2]] 输出 [2] 输入 [[0,0,0]] 输出 [0,0,0]
扫描指针 i 指向的元素如果是 0，就和 lo 位置交换，并且 lo、i 都前进：因为 lo 位置原来是 1（[lo, i) 里全是 1），换到 i 的一定是 1，已经处理完了。但如果 i 指向的是 2，就和 hi 位置交换，hi 后退，这时换到 i 位置的是原来 hi 位置的元素，还没检查过，可能是 0、1 或 2，所以 i 不能前进，必须再检查一次。下面是让 i 也前进的错误写法：
# 与 2 交换之后 i 也前进的写法 [2, 0, 1]: 该写法 -> [0, 1, 2] solve -> [0, 1, 2] [2, 0, 2, 1, 1, 0]: 该写法 -> [0, 0, 1, 1, 2, 2] solve -> [0, 0, 1, 1, 2, 2] [2, 1, 0]: 该写法 -> [0, 1, 2] solve -> [0, 1, 2] [0, 1, 2]: 该写法 -> [0, 1, 2] solve -> [0, 1, 2] 最短的一个反例（穷举 0、1、2 组成的数组，按长度从短到长）：[1, 2, 0] -> 该写法得到 [1, 0, 2]，正确是 [0, 1, 2] 随机 20000 个数组：该写法排错的有 10236 个（51.2%）
前面四个示例（例如官方的两个）碰巧都排对了，这个错误只在换过来的元素恰好是 0 的时候才出问题：最短的反例是 [1, 2, 0]，i 指向 2 时与末尾的 0 交换，换过来的 0 被跳过，得到 [1, 0, 2]，而正确答案是 [0, 1, 2]。在随机的 20000 个数组里，这种写法排错的有 10236 个，占 51.2%。所以官方示例通过并不能说明这个细节是对的。
lo、i、hi 三个指针，循环条件是 i <= hi。如果 nums[i] 是 0：与 nums[lo] 交换，lo 和 i 都加一；如果是 2：与 nums[hi] 交换，hi 减一，i 不动；如果是 1：i 加一。i 越过 hi 时，数组就排好了。每个元素最多被检查两次。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): lo, i, hi = 0, 0, len(nums) - 1 # [0, lo) 全是 0，[lo, i) 全是 1，(hi, 末尾] 全是 2，[i, hi] 还没处理 while i <= hi: if nums[i] == 0: nums[i], nums[lo] = nums[lo], nums[i] # 0 换到前面；换回来的一定是 1（[lo, i) 里都是 1），所以 i 可以前进 lo += 1 i += 1 elif nums[i] == 2: nums[i], nums[hi] = nums[hi], nums[i] # 2 换到后面；换回来的元素还没检查过，所以 i 不能前进 hi -= 1 else: i += 1 # 1 留在中间 return nums
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,0,2,1,1,0]] → [0,0,1,1,2,2] [[2,0,1]] → [0,1,2] [[0]] → [0] [[1]] → [1] [[2]] → [2] [[0,0,0]] → [0,0,0]
Java · 解法代码class Solution { public void sortColors(int[] nums) { int lo = 0, i = 0, hi = nums.length - 1; // [0, lo) 全是 0，[lo, i) 全是 1，(hi, 末尾] 全是 2，[i, hi] 还没处理 while (i <= hi) { if (nums[i] == 0) { int t = nums[i]; nums[i] = nums[lo]; nums[lo] = t; // 0 换到前面；换回来的一定是 1，所以 i 可以前进 lo++; i++; } else if (nums[i] == 2) { int t = nums[i]; nums[i] = nums[hi]; nums[hi] = t; // 2 换到后面；换回来的元素还没检查过，所以 i 不能前进 hi--; } else { i++; // 1 留在中间 } } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,0,2,1,1,0]] → [0,0,1,1,2,2] [[2,0,1]] → [0,1,2] [[0]] → [0] [[1]] → [1] [[2]] → [2] [[0,0,0]] → [0,0,0]
Go · 解法代码func sortColors(nums []int) { lo, i, hi := 0, 0, len(nums)-1 // [0, lo) 全是 0，[lo, i) 全是 1，(hi, 末尾] 全是 2，[i, hi] 还没处理 for i <= hi { if nums[i] == 0 { nums[i], nums[lo] = nums[lo], nums[i] // 0 换到前面；换回来的一定是 1，所以 i 可以前进 lo++ i++ } else if nums[i] == 2 { nums[i], nums[hi] = nums[hi], nums[i] // 2 换到后面；换回来的元素还没检查过，所以 i 不能前进 hi-- } else { i++ // 1 留在中间 } } }
$ go build -o bin . && ./bin < cases.jsonl [[2,0,2,1,1,0]] → [0,0,1,1,2,2] [[2,0,1]] → [0,1,2] [[0]] → [0] [[1]] → [1] [[2]] → [2] [[0,0,0]] → [0,0,0]
JavaScript · 解法代码function sortColors(nums) { let lo = 0, i = 0, hi = nums.length - 1; // [0, lo) 全是 0，[lo, i) 全是 1，(hi, 末尾] 全是 2，[i, hi] 还没处理 while (i <= hi) { if (nums[i] === 0) { [nums[i], nums[lo]] = [nums[lo], nums[i]]; // 0 换到前面；换回来的一定是 1，所以 i 可以前进 lo++; i++; } else if (nums[i] === 2) { [nums[i], nums[hi]] = [nums[hi], nums[i]]; // 2 换到后面；换回来的元素还没检查过，所以 i 不能前进 hi--; } else { i++; // 1 留在中间 } } }
$ node run.js < cases.jsonl [[2,0,2,1,1,0]] → [0,0,1,1,2,2] [[2,0,1]] → [0,1,2] [[0]] → [0] [[1]] → [1] [[2]] → [2] [[0,0,0]] → [0,0,0]
C++ · 解法代码#include <utility> #include <vector> using namespace std; class Solution { public: void sortColors(vector<int>& nums) { int lo = 0, i = 0, hi = (int)nums.size() - 1; // [0, lo) 全是 0，[lo, i) 全是 1，(hi, 末尾] 全是 2，[i, hi] 还没处理 while (i <= hi) { if (nums[i] == 0) { swap(nums[i], nums[lo]); // 0 换到前面；换回来的一定是 1，所以 i 可以前进 lo++; i++; } else if (nums[i] == 2) { swap(nums[i], nums[hi]); // 2 换到后面；换回来的元素还没检查过，所以 i 不能前进 hi--; } else { i++; // 1 留在中间 } } } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[2,0,2,1,1,0]] → [0,0,1,1,2,2] [[2,0,1]] → [0,1,2] [[0]] → [0] [[1]] → [1] [[2]] → [2] [[0,0,0]] → [0,0,0]
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
荷兰国旗的优势是"一遍扫描"，计数排序需要扫描两遍。我在 Python 里对长度 10 万、100 万的随机 0/1/2 数组比较了三种做法（每个取三次中最快的一次）：
三种做法的耗时（长度 n 的随机 0/1/2 数组，各取三次中最快）： n= 100000: 荷兰国旗一遍扫描 5.08 ms 计数排序两遍 2.04 ms 内置 sorted 3.84 ms n= 1000000: 荷兰国旗一遍扫描 51.79 ms 计数排序两遍 23.78 ms 内置 sorted 40.92 ms
计数排序（先用一遍扫描数个数，再用列表乘法写回）最快：100 万时 21.0ms；内置 sorted 41.1ms；荷兰国旗的一遍扫描最慢，52.1ms。我没有做进一步分析，一个可能的解释是：荷兰国旗每个元素都要在解释器里做多次比较和交换，而计数排序的第一遍只做一次自增，第二遍是 C 实现的列表乘法，这只是猜测。这只是 Python 里的实测，在 Java、C++ 这类编译型语言里，一遍扫描的荷兰国旗很可能更有优势，本文没有测。
Python 版本另外和直接排序做了随机对拍：长度 1 到 15，取值 0、1、2：
随机对拍 20000 组（长度 1 到 15、取值 0、1、2 的随机数组），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
数组长度分别为 1 万、10 万、100 万，每个规模取三次中最快的一次，基准是内置的 sorted（C 实现，并且对只有三种取值的数据很快）：
数组长度 n | 暴力解 | 本文解法
10000 | 0.235 ms | 0.422 ms
100000 | 2.402 ms | 4.248 ms
1000000 | 27.212 ms | 43.016 ms荷兰国旗在 Python 里比内置 sorted 慢约 1.6 倍（100 万时 43.4ms 对 27.7ms），两者都是线性增长。这不说明算法差，只说明在 Python 里，纯解释执行的循环比 C 实现的排序慢。
下面的演示用 [2, 0, 2, 1, 1, 0]。i = 0 的 2 与末尾的 0 交换，hi 后退，i 不动；下一步 i = 0 的元素变成 0，与 lo 交换（同一个位置，等于没动），lo、i 一起前进；之后陆续处理 2 和 1，最后 i 越过 hi，数组变成 [0, 0, 1, 1, 2, 2]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。