T618763 荷兰国旗问题

“荷兰国旗问题”（Dutch National Flag Problem）是由 Dijkstra 提出的一个经典的一趟划分（one-pass partition）算法，核心思想是把只包含三种可能取值的数组，原地划分成三段——小于、等于、大于主元（pivot）。

给定长度为 $n$ 的数组 $a[0..n-1]$，其中每个元素只可能是三种颜色中的一种（通常用数字 `0`,`1`,`2` 表示）。要求原地（in-place）、一次遍历（one-pass）后，把所有 `0` 放到最左边，所有 `1` 放中间，所有 `2` 放右边。

* **输入**：一个只含 $\{0,1,2\}$ 的数组 $a$。 首先输入 $n$ 代表这个数组有 $n$ 个元素。然后输入这个 $n$ 个元素 $a_i$ $1

* **输出**：重排后的数组，使得 $$ [\underbrace{0,0,\dots,0}_{\text{所有0}} \;|\; \underbrace{1,1,\dots,1}_{\text{所有1}} \;|\; \underbrace{2,2,\dots,2}_{\text{所有2}}] $$

* **关键点**：一次遍历、原地交换。 * **适用场景**：除了 $\{0,1,2\}$ 的情况，只要把等于基准看成1，小于基准看成0，大于基准看成2，也可以用于快速排序中对含大量重复元素的优化（三路划分快排）。