荷兰国旗问题（Dutch National Flag Problem） 题目描述 给定一个包含红色、白色和蓝色元素的数组，代表荷兰国旗的三种颜色，你需要原地对它们进行排序，使得相同颜色的元素相邻，且按照红色、白色、蓝色的顺序排列。通常使用整数 0、1、2 分别表示红色、白色和蓝色。例如，输入数组 [ 2,0,2,1,1,0]，排序后应得到 [ 0,0,1,1,2,2 ]。 解题过程 问题分析 目标是将数组划分为三个区域，分别存放 0、1、2。 要求仅遍历数组一次，且使用常数空间（即原地排序）。 关键难点在于如何高效处理中间值（1）的归属，避免多次交换。 三指针法（Dutch National Flag Algorithm） 使用三个指针： low ：指向当前已排序的 0 的末尾的下一个位置（即 1 的起始位置）。 mid ：当前遍历的指针，用于检查元素值。 high ：指向当前已排序的 2 的起始位置的前一个位置（即 2 的起始位置）。 初始化： low = 0 ， mid = 0 ， high = n-1 （n 为数组长度）。 核心逻辑：通过移动 mid 指针并根据其指向的值交换元素，逐步扩大 0 和 2 的区间，同时压缩未处理区间。 具体步骤 步骤 1 ：若 nums[mid] == 0 ，交换 nums[low] 和 nums[mid] ，然后 low++ 和 mid++ 。 解释：0 应位于左端，交换后low右移确保0的区间扩大，mid右移继续检查下一个元素。 步骤 2 ：若 nums[mid] == 1 ，仅 mid++ 。 解释：1 应位于中间，无需交换，直接继续检查下一个元素。 步骤 3 ：若 nums[mid] == 2 ，交换 nums[mid] 和 nums[high] ，然后 high-- 。 解释：2 应位于右端，交换后high左移确保2的区间扩大，但mid不移动（因为交换后的新元素未被检查）。 终止条件 ：当 mid > high 时停止，此时所有元素已处理完毕。 示例演示 以数组 [ 2,0,2,1,1,0 ] 为例： 初始：low=0, mid=0, high=5 → [ 2,0,2,1,1,0 ] mid=0，值为2：交换2和0，high=4 → [ 0,0,2,1,1,2 ] mid=0，值为0：交换0和0，low=1, mid=1 → [ 0,0,2,1,1,2 ] mid=1，值为0：交换0和0，low=2, mid=2 → [ 0,0,2,1,1,2 ] mid=2，值为2：交换2和1，high=3 → [ 0,0,1,1,2,2 ] mid=2，值为1：mid=3 → [ 0,0,1,1,2,2 ] mid=3，值为1：mid=4 → 停止（mid=4 > high=3） 结果：[ 0,0,1,1,2,2 ] 算法特点 时间复杂度：O(n)，遍历一次数组。 空间复杂度：O(1)，仅使用三个指针。 稳定性：非稳定排序（交换可能改变相同元素的相对顺序）。