LeetCode颜色排序算法：迭代变量i的增减逻辑疑惑

这个问题的核心是搞懂三指针分区的思路——我们用三个指针把数组划分成三个确定区域和一个待处理区域：[0, low-1]全是0，[low, i-1]全是1，[high+1, n-1]全是2，[i, high]则是还没处理的部分。接下来逐个拆解不同情况的指针移动逻辑：

当A[i] == 0时，为什么i和low都要递增？ #

• low的作用是标记下一个应该放置0的位置，它左边的所有元素已经被确认是0了。当我们把A[i]的0交换到A[low]后，这个位置的0就归位了，所以low需要右移，找下一个放0的空位。
• 至于i为什么可以跟着递增？因为我们是从左往右遍历的，low到i之间的元素都是已经处理过的1（如果有0的话早就被交换到左边了）。交换后，A[i]拿到的是原来A[low]的元素——要么是1（当low < i时），要么就是它自己（当low == i时）。不管哪种情况，这个元素都是我们已经确认过不需要再处理的，所以i可以放心右移，检查下一个元素。

当A[i] == 1时，为什么i直接递增？ #

1本来就是我们要放在中间区域的目标元素，不需要任何交换操作，直接把i右移，处理下一个待检查的元素就行，逻辑非常直观。

当A[i] == 2时，为什么只递减high，i不动？ #

• high的作用是标记下一个应该放置2的位置，它右边的所有元素已经被确认是2了。把A[i]的2交换到A[high]后，这个位置的2就归位了，所以high需要左移，找下一个放2的空位。
• 那为什么i不能跟着递增？因为交换后，A[i]拿到的是原来A[high]的元素——这个元素可能是0、1或者2，我们完全没检查过它！比如，假设原来的A[high]是0，那我们需要把这个0交换到左边的0区域，所以必须留在当前i的位置，在下一次循环里处理它。如果这时候盲目把i递增，就会漏掉这个需要处理的元素。

举个实际例子验证 #

拿输入[2,0,2,1,1,0]走一遍流程：

1. 初始状态：low=0，high=5，i=0
2. A[i]=2：交换A[0]和A[5]，数组变成[0,0,2,1,1,2]，high=4，i保持0不变（因为交换过来的是0，需要处理）
3. A[i]=0：交换A[0]和A[0]（自己），i=1，low=1
4. A[i]=0：交换A[1]和A[1]，i=2，low=2
5. A[i]=2：交换A[2]和A[4]，数组变成[0,0,1,1,2,2]，high=3，i保持2不变（交换过来的是1，下一次检查）
6. A[i]=1：i=3
7. A[i]=1：i=4，此时i>high，循环结束，数组已经有序。

这样就能清晰看到，交换2时如果移动i，就会错过处理交换过来的元素，而交换0时移动i是完全安全的。

内容的提问来源于stack exchange，提问作者P.K.