Leetcode75这道题在LeetCode上被称为“颜色分类”，在算法导论中它有一个更著名的名字——荷兰国旗问题 (Dutch National Flag Problem)。这是一个由计算机科学奠基人 Dijkstra 提出的经典问题。

在NOI/NOIP竞赛体系中，这道题考察的核心不是排序本身（因为用 std::sort 太容易了），而是考察原地算法 (In-place Algorithm) 的思维以及多指针 (Multi-pointers) 协作处理数组分区的能力。

下面我将其改编为符合NOI竞赛格式的题目描述。

题目：颜色分类 (Sort Colors)

题目描述

给定一个包含 $n$ 个元素的数组 nums，元素的值仅为 0、1 或 2，分别代表红色、白色和蓝色。

请你原地对数组进行排序，使得所有相同颜色的元素彼此相邻，并按照 0（红色）、1（白色）、2（蓝色）的顺序排列。

严格限制：

1. 禁止使用标准库提供的排序函数（如 C++ 中的 std::sort），你需要自己实现排序逻辑。
2. 你的解法应当尽可能优化空间复杂度，争取使用 $O(1)$ 的额外空间。

输入格式

第一行包含一个整数 $n$，表示数组的长度。 第二行包含 $n$ 个整数，表示数组 nums 的元素，整数之间用空格分隔。

输出格式

输出一行，包含 $n$ 个整数，表示排序后的数组，整数之间用空格分隔。

样例输入 1

6
2 0 2 1 1 0

样例输出 1

0 0 1 1 2 2

样例输入 2

3
2 0 1

样例输出 2

0 1 2

数据范围与提示

• $1 \le n \le 300$
• nums[i] 的值保证为 0, 1 或 2。
• 进阶挑战：你能想出一个仅使用常数空间 $O(1)$ 且只进行一次遍历 (One-pass) 的算法吗？

教练的解题思路提示 (NOIP C++14)

这道题有三种层次的解法，体现了从暴力到优雅的思维跃迁。

方法一：计数排序 (Counting Sort) - 两趟扫描

这是最直观的思路。

1. 第一趟扫描：统计 0、1、2 分别出现了多少次（比如分别出现了 $a, b, c$ 次）。
2. 第二趟扫描：根据统计结果，重写原数组。前 $a$ 个位置填 0，接下来 $b$ 个位置填 1，最后 $c$ 个位置填 2。

• 复杂度：时间 $O(N)$，空间 $O(1)$。但需要遍历两次数组。

方法二：三指针法 (Three Pointers) - 一趟扫描

这是本题的精髓，也就是 Dijkstra 的荷兰国旗算法。我们可以把数组看作三个区域的动态划分：

• 左侧 (Left)：全都是 0 的区域。
• 右侧 (Right)：全都是 2 的区域。
• 中间 (Current)：全是 1 的区域（或者待处理区域）。

我们需要维护三个指针：

1. p0：指向 0 区域的下一个存放位置（初始为 0）。
2. p2：指向 2 区域的前一个存放位置（初始为 $n-1$）。
3. curr：当前正在考察的元素指针（初始为 0）。

伪代码提示 (Pseudo-code)：

函数 sortColors(nums, n):
    初始化 p0 = 0
    初始化 curr = 0
    初始化 p2 = n - 1

    // 当当前指针还没遇到 2 的边界时，继续循环
    当 curr <= p2 时，执行循环：
        如果 nums[curr] == 0 则：
            // 遇到 0，应该放到左边
            交换(nums[curr], nums[p0])
            p0 = p0 + 1
            curr = curr + 1 
            // 思考：为什么这里 curr 可以放心右移？
            // 因为 p0 左边全是 0，p0 和 curr 之间全是 1 (处理过的)
            
        否则如果 nums[curr] == 2 则：
            // 遇到 2，应该放到右边
            交换(nums[curr], nums[p2])
            p2 = p2 - 1
            // 易错点警告：
            // 这里 curr 不能立即 +1。
            // 因为从 p2 换回来的那个数我们还没检查过（可能是 0 或 1 甚至 2）
            // 需要在下一轮循环继续检查 nums[curr]
            
        否则：
            // 遇到 1，它就应该在中间，不需要动
            curr = curr + 1
        结束如果
    结束循环

知识点覆盖 (Knowledge Points)

在备战 NOIP/NOI 时，通过此题你需要掌握：

1. 排序算法基础：理解非比较排序（如计数排序）在特定值域下的优势。
2. 双指针/多指针技巧 (Two/Three Pointers)：这是解决数组分区（Partition）问题的核心手段，也是快速排序（Quick Sort）中 partition 操作的基础。
3. 原地算法 (In-place Algorithm)：理解空间复杂度 $O(1)$ 的含义，即只使用常数个额外变量，不随数据规模 $N$ 增长。
4. 交换操作 (Swap)：如何在数组中通过交换达到移动元素的目的，而非插入删除（插入删除是 $O(N)$ 的）。

易错点总结

1. 循环终止条件：是 curr < p2 还是 curr <= p2？（答案是 <=，因为 p2 指向的位置也需要被检查）。
2. 指针移动时机：与 p2 交换后，curr 指针不应移动；而与 p0 交换后，curr 指针应该移动。这是逻辑中最容易写错的地方。
3. 边界处理：如果数组是空的，或者只有一个元素，代码是否健壮？