给定一个只包含 0、1、2 三种元素的数组，要求将其原地排序，使所有 0 排在最前面，1 排在中间，2 排在最后面，并且不允许使用额外的数组空间。这就是经典的荷兰国旗问题，也是各大公司面试中出现频率极高的一道算法题。本文将详细介绍如何用 C# 实现一次遍历、常数空间的三指针解法。
一、问题分析与解题思路
最直观的做法是先统计数组中 0、1、2 各自出现的次数，然后再按顺序回填。这种方法虽然时间复杂度也是 O(n)，但需要遍历数组两次，而且面试官往往会追问能否只遍历一次。另一个思路是直接调用 Array.Sort，但快速排序的平均空间复杂度为 O(log n)，并且无法体现对算法本身的掌握。
荷兰国旗问题的标准解法是三指针法。核心思想是维护三个指针：low、mid 和 high，将数组在逻辑上划分为四个区域：
- [0, low-1]：全部是 0 的区域
- [low, mid-1]：全部是 1 的区域
- [mid, high]：还未扫描的未知区域
- [high+1, 数组末尾]：全部是 2 的区域
初始时 low 和 mid 都指向下标 0，high 指向数组末尾。遍历过程中，mid 指针不断向后探测元素，根据元素的值做相应处理，未知区域逐渐缩小，直到 mid 超过 high，排序完成。
二、C# 完整实现代码
三指针法的处理逻辑分为三种情况：当 mid 位置的元素是 0 时，将它与 low 位置的元素交换，然后 low 和 mid 各前进一步；当元素是 1 时，它本来就该留在中间区域，直接让 mid 前进一步；当元素是 2 时，将它与 high 位置的元素交换，high 后退一步，但此时 mid 不前进，因为从 high 交换过来的元素还没有被检查过。
using System;
class DutchFlagSort
{
public static void SortColors(int[] nums)
{
if (nums == null || nums.Length < 2)
return;
int low = 0;
int mid = 0;
int high = nums.Length - 1;
while (mid <= high)
{
switch (nums[mid])
{
case 0:
// 将 0 交换到左侧区域
Swap(nums, low, mid);
low++;
mid++;
break;
case 1:
// 1 本来就属于中间区域，直接跳过
mid++;
break;
case 2:
// 将 2 交换到右侧区域，mid 不动，需重新检查换来的元素
Swap(nums, mid, high);
high--;
break;
}
}
}
private static void Swap(int[] nums, int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
static void Main()
{
int[] arr1 = { 2, 0, 2, 1, 1, 0 };
int[] arr2 = { 2, 0, 1 };
int[] arr3 = { 1, 1, 2, 2, 0, 0 };
SortColors(arr1);
SortColors(arr2);
SortColors(arr3);
Console.WriteLine(string.Join(",", arr1)); // 输出: 0,0,1,1,2,2
Console.WriteLine(string.Join(",", arr2)); // 输出: 0,1,2
Console.WriteLine(string.Join(",", arr3)); // 输出: 0,0,1,1,2,2
}
}运行上面的代码可以看到，三组测试数据全部输出正确结果。整个过程只对数组做了原地交换，没有创建任何新的数组或集合，空间开销只有三个 int 变量，完全满足题目对额外空间的要求。
三、关键细节与常见错误
1. 为什么遇到 2 时 mid 不能前进
这是本算法最容易出错的地方。当 nums[mid] 为 2 时，我们把它与 nums[high] 交换。但 nums[high] 原来的值可能是 0、1 或 2 中的任何一个，交换过来之后尚未被检查。如果此时贸然让 mid 前进，就可能漏掉一个需要处理的 0，导致排序结果错误。因此在 case 2 分支中只让 high 后退，mid 保持不动，下一轮循环会重新检查换过来的元素。
2. 为什么遇到 0 时 mid 可以前进
当 nums[mid] 为 0 时，它与 nums[low] 交换。由于 mid 始终大于等于 low，nums[low] 要么就是 mid 自己（两者重合时），要么来自已经扫描过的 1 区域，值一定是 1。所以换过来的元素必然是 1 或 0，不需要再检查，low 和 mid 同时前进一步是安全的。
3. 循环终止条件
循环条件必须是 mid <= high 而不是 mid < high。当 mid 等于 high 时，该位置的元素仍属于未知区域，还没有被分类，必须进入循环处理。写成小于号会导致最后一个元素被遗漏，例如数组 [1, 0, 2] 就会得到错误结果。
四、与计数排序方案的对比
除了三指针法，计数排序也是常见解法：先遍历一次统计 0、1、2 的个数，再遍历一次回填。两种方案各有优劣，下表是详细对比：
| 对比项 | 三指针法 | 计数排序 |
|---|---|---|
| 时间复杂度 | O(n)，一次遍历 | O(n)，两次遍历 |
| 空间复杂度 | O(1) | O(1)（仅三个计数器） |
| 交换次数 | 较少，最多 n 次 | 无需交换，直接覆盖 |
| 稳定性 | 不稳定 | 不稳定（元素值相同时无差别） |
| 扩展性 | 可扩展到三路快排分区 | 仅适用于取值范围极小的场景 |
计数排序的 C# 实现也非常简洁，代码如下，适合作为对照参考：
public static void SortByCounting(int[] nums)
{
int count0 = 0, count1 = 0, count2 = 0;
// 第一次遍历：统计各元素出现次数
foreach (int num in nums)
{
if (num == 0) count0++;
else if (num == 1) count1++;
else count2++;
}
// 第二次遍历：按顺序回填
int index = 0;
for (int i = 0; i < count0; i++) nums[index++] = 0;
for (int i = 0; i < count1; i++) nums[index++] = 1;
for (int i = 0; i < count2; i++) nums[index++] = 2;
}如果面试中被追问一次遍历的解法，三指针法是唯一标准答案；如果只是工程场景下对取值范围极小的整数排序，计数排序写起来更快、更不容易出错。值得一提的是，三指针法的分区思想正是快速排序三路划分的基础，掌握它对理解三路快排处理大量重复元素的场景也有直接帮助。