荷兰国旗问题两种遍历解法的核心逻辑疑问：顺序与循环选择

问题1：遍历顺序与处理顺序的强制要求 #

从左到右遍历：先处理2，再处理0 #

当从左到右遍历数组时，start指针左侧是已排好的0，end指针右侧是已排好的2。如果颠倒处理顺序，会出现元素遗漏：

• 若先处理0，把当前位置的0和start交换后，start位置原本的元素可能是2（start到当前i之间的元素还未处理2），这个2会被留在i位置。而i是递增遍历的，后续不会回头处理该位置，导致2最终留在0和1的区域，排序失败。
• 先处理2的话，把当前位置的2交换到end并左移end，交换过来的元素只能是0或1：如果是0，后续处理0的逻辑会把它移到start区域；如果是1，无需处理即可继续遍历，不会遗漏任何元素。

从右到左遍历：先处理0，再处理2 #

当从右到左遍历数组时，end右侧是已排好的2，start左侧是已排好的0。颠倒处理顺序同样会导致遗漏：

• 若先处理2，把当前位置的2交换到end并左移end，交换过来的元素可能是0，而i是递减遍历的，后续不会回头处理该位置的0，导致0留在2和1的区域，排序失败。
• 先处理0的话，把当前位置的0交换到start并右移start，交换过来的元素只能是1或2：如果是2，后续处理2的逻辑会把它移到end区域；如果是1，无需处理即可继续遍历，确保所有元素归位。

问题2：从右到左遍历处理0时必须用while而非if #

从右到左处理0时，交换nums[i]和nums[start]后，nums[i]的位置可能仍然是0——因为start位置原本的元素可能就是0（start左侧是已排好的0，但start自身还未被处理）。如果只用if，只交换一次就跳过，这个残留的0会被i的递减遍历错过，最终留在非0区域。

举个例子：数组[0,0,2,1,0]，从右到左遍历到i=4时，nums[i]=0，此时start=0。如果用if交换一次，start变为1，但nums[4]仍然是0（因为nums[0]原本就是0），i递减到3后，这个位置的0就再也不会被处理，最终数组无法完全排序。

用while循环可以持续交换，直到nums[i]不再是0，或者i <= start（此时i左侧已经都是0，无需继续交换），确保所有0都被移到正确区域。

附：两种遍历解法代码 #

从左到右遍历解法

class Solution {
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void sortColors(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        // 从左到右遍历
        for (int i = 0; i < nums.length; i++) {
            // 先处理"2"，再处理"0"，顺序不可颠倒
            while (i < end && nums[i] == 2) {
                swap(nums, end, i);
                end--;
            }
            if (nums[i] == 0) { // 或 `while (i > start && nums[i] == 0)`
                swap(nums, start, i);
                start++;
            }
        }
    }
}

从右到左遍历解法

class Solution {
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void sortColors(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        // 从右到左遍历
        for (int i = nums.length - 1; i >= 0; i--) {
            // 先处理"0"，再处理"2"，顺序不可颠倒
            while (i > start && nums[i] == 0) { // 不能使用 `if (nums[i] == 0)`
                swap(nums, start, i);
                start++;
            }
            while (i < end && nums[i] == 2) {
                swap(nums, end, i);
                end--;
            }
        }
    }
}

内容的提问来源于stack exchange，提问作者Xiangzhen Zhang