题意概括

给定一个包含 n 个元素的数组，其中元素仅为 0, 1, 2 三种（分别代表红、白、蓝三种颜色）。要求对该数组进行 原地排序，使得所有相同颜色的元素相邻，并按 0, 1, 2 的顺序排列。不允许使用库函数 sort。

数据范围:

• $1 \le n \le 1000$ (假设)
• 数组元素为 0, 1, 或 2。

基础知识

本题是经典的 “荷兰国旗问题”，是三向切分（3-way partition）思想的一个具体应用，常用于快速排序的优化中。最优雅的解法是使用三个指针进行一次遍历，在 $O(N)$ 的时间复杂度和 $O(1)$ 的空间复杂度下完成排序。

我们使用三个指针来将数组划分为四个区域：

1. p0 指针：指向数字 0 区域的 右边界。[0, p0-1] 区间内的元素保证都是 0。
2. cur 指针：指向当前正在处理的元素。[p0, cur-1] 区间内的元素保证都是 1。
3. p2 指针：指向数字 2 区域的 左边界。[p2+1, n-1] 区间内的元素保证都是 2。

[cur, p2] 区域是当前尚未处理的混合区域。我们的目标就是不断缩小这个区域。

算法流程如下（cur 从头开始遍历，直到与 p2 相遇）：

• 当 a[cur] 为 0 时：
  • 它应该属于 0 区域。我们将 a[cur] 与 a[p0] 交换。
  • 交换后，p0 位置的元素已确定为 0，所以 p0 右移一位。
  • 当前 cur 位置的元素也已经处理完毕（从 p0 交换过来的必定是 1 或 0，而 cur >= p0，所以不可能是2，原先的0被换走），所以 cur 右移一位。
• 当 a[cur] 为 1 时：
  • 它当前的位置是正确的（在 1 的区域内），无需任何操作。
  • 我们继续处理下一个元素，cur 右移一位。
• 当 a[cur] 为 2 时：
  • 它应该属于 2 区域。我们将 a[cur] 与 a[p2] 交换。
  • 交换后，p2 位置的元素已确定为 2，所以 p2 左移一位。
  • 注意：此时 cur 不能右移，因为从 p2 交换过来的元素是未知的，需要留在当前位置，在下一轮循环中继续进行判断处理。

循环的终止条件是 cur > p2，此时所有元素都已归位。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // p0: 0的右边界; cur: 当前指针; p2: 2的左边界
    int p0 = 0, cur = 0, p2 = n - 1;

    while (cur <= p2) {
        if (a[cur] == 0) {
            swap(a[cur], a[p0]);
            p0++;
            cur++;
        } else if (a[cur] == 2) {
            swap(a[cur], a[p2]);
            p2--;
            // 注意：cur不增加，因为换过来的a[cur]需要重新判断
        } else { // a[cur] == 1
            cur++;
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << a[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
6
2 0 2 1 1 0
输出:
0 0 1 1 2 2

样例 2:
输入:
3
2 0 1
输出:
0 1 2
*/