https://leetcode.cn/problems/sort-colors/description

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

思路：用双指针法把数组分成三部分区域，第一部分是红色区域，其右边界是p0；最后一部分是蓝色区域，其左边界是p2；从头到尾遍历数组并进行判断元素属于什么区域，交换元素并更新指针p0或p2

C#实现

public class Solution {
    public void SortColors(int[] nums) {
        // 定义三个指针：
        // p0：指向下一个该放置 0 的位置（红色区右边界）
        // p2：指向下一个该放置 2 的位置（蓝色区左边界）
        // i ：当前扫描指针，从左到右遍历
        int p0 = 0;
        int p2 = nums.Length - 1;
        int i = 0;
        // 当 i 超过 p2 时说明所有元素都归位
        while(i <= p2) {
            if(nums[i] == 0) {
                // 当前是 0（红色）
                // 应该放到最前面的“红色区域”
                // 所以与 p0 位置交换
                Swap(nums, i, p0);
                // 交换完后：
                // 左边的红色区扩大一格
                p0++;
                // 当前位置 i 已经处理完，继续向右扫描
                i++;
            } else if(nums[i] == 2) {
                // 当前是 2（蓝色）
                // 应该放到最后面的“蓝色区域”
                // 所以与 p2 位置交换
                Swap(nums, i, p2);
                // 蓝色区左边界向左移动一格
                p2--;
                // ⚠ 注意：这里 i 不递增！
                // 因为从右边交换过来的数还没检查，
                // 它可能是 0 或 1，还需要继续判断
            } else {
                // 当前是 1（白色）
                // 白色放在中间，不需要换
                // 直接跳到下一个
                i++;
            }
        }
    }

    private void Swap(int[] nums, int i, int j) {
        if(i==j) return;
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}