c++ - 递增迭代变量背后的直觉？

Question

我正在解决关于 LeetCode.com 的问题:

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, they use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. [The trivial counting sort cannot be used].

For the input: [2,0,2,1,1,0]; the output expected is: [0,0,1,1,2,2].

highly upvoted solutions 之一是这样的:

   public void sortColors(vector<int>& A) {
       if(A.empty() || A.size()<2) return;
       int low = 0; 
       int high = A.size()-1;
       for(int i = low; i<=high;) {
           if(A[i]==0) {
              // swap A[i] and A[low] and i,low both ++
              int temp = A[i];
              A[i] = A[low];
              A[low]=temp;
              i++;low++;
           }else if(A[i]==2) {
               //swap A[i] and A[high] and high--;
              int temp = A[i];
              A[i] = A[high];
              A[high]=temp;
              high--;
           }else {
               i++;
           }
       }
   }

我的问题是，为什么当 A[i]==0 和 A[i]==1 时 i 增加而不是当 A[i]==2 时？使用笔和纸，算法就可以给我答案；但你能提供一些直觉吗？

谢谢!

Answer 1

这逐步遍历数组并维护元素 0..i 已排序的约束，并且所有元素都是 0 或 1。 (那里的 2 被交换到数组的末尾。)

当 A[i]==0 时，您将 i 处的元素(我们刚才说的是 0)与low 处的元素，它是 0..i 范围内的第一个 1 元素(如果有)。因此，在交换之后，A[i]==1 是可以的(约束仍然有效)。我们现在可以安全地在阵列中前进了。如果 A[i]==1 最初也是如此，在这种情况下不执行交换。

当 A[i]==2 时，您实质上是将元素 i(我们刚才说的是 2)移动到数组的末尾。但是你也从数组的末尾移动了一些东西到元素 i 的位置，我们不知道那个元素是什么(因为我们之前没有处理过它，不像 A[i]==0 案例)。因此，我们不能安全地将 i 向前移动，因为 A[i] 处的新元素可能还没有在正确的位置。我们需要另一次迭代来处理新的 A[i]。