跳至主要內容

颜色分类：荷兰国旗三路划分与快速排序分区

老张2026/4/30大约 6 分钟

颜色分类：荷兰国旗三路划分与快速排序分区

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 17 分钟 | 难度：⭐⭐⭐

开篇故事

荷兰国旗问题是由计算机科学家 Edsger Dijkstra 提出的。他用荷兰国旗（红白蓝三色）来命名这个问题，所以又叫"荷兰国旗问题"。

这道题本质上是快速排序里 partition（划分）步骤的三路版本。标准快排的 partition 是两路划分（小于 pivot 和大于等于 pivot），而三路划分把等于 pivot 的元素也单独分出来，这样快排在处理大量重复元素时性能会更好。

我第一次写这道题，用了两次计数排序，数一遍 0 有多少个、1 有多少个、2 有多少个，然后重写数组。这是正确的，但面试官说："能不能只扫一遍，原地完成？"这才逼出了三路划分的解法。

一、题目解析

题目（LeetCode 75）： 给定数组 nums，其中元素只有 0、1、2。对数组进行原地排序（不使用库函数），要求只使用常数额外空间，且只扫描一遍。

示例：

  • 输入：[2,0,2,1,1,0]，输出：[0,0,1,1,2,2]

二、解法一：计数排序（O(2n)，两次扫描）

public class Solution1 {
    public void sortColors(int[] nums) {
        int cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for (int n : nums) {
            if (n == 0) cnt0++;
            else if (n == 1) cnt1++;
            else cnt2++;
        }
        int i = 0;
        while (cnt0-- > 0) nums[i++] = 0;
        while (cnt1-- > 0) nums[i++] = 1;
        while (cnt2-- > 0) nums[i++] = 2;
    }
}

复杂度分析

  • 时间复杂度：O(n)。两次扫描。
  • 空间复杂度：O(1)。

虽然整体是 O(n)，但扫描了两遍，不满足"只扫一遍"的进阶要求。

三、解法二：两指针两路划分（O(n)，接近一遍）

先把 0 放前面（一次扫描），再把 2 放后面（另一次扫描）：

public class Solution2 {
    public void sortColors(int[] nums) {
        // 第一遍：把 0 放到最前面
        int insertPos = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                swap(nums, i, insertPos++);
            }
        }
        // 第二遍：把 2 放到最后面
        insertPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == 2) {
                swap(nums, i, insertPos--);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
    }
}

四、解法三最优：荷兰国旗三路划分（一遍扫描）

核心思路

维护三个指针：

  • low：[0, low) 都是 0
  • mid：[low, mid) 都是 1，mid 是当前待处理的元素
  • high：(high, n-1] 都是 2

初始：low = 0, mid = 0, high = n - 1，此时 [mid, high] 是待处理的区域。

循环处理 nums[mid]：

  • nums[mid] == 0：将 nums[mid] 与 nums[low] 交换，low++，mid++。交换后 nums[mid] 变成了确定的 1（因为 [low, mid) 都是 1），所以 mid 也可以前进。
  • nums[mid] == 1：直接 mid++，1 已经在正确位置。
  • nums[mid] == 2：将 nums[mid] 与 nums[high] 交换，high--。注意此时 mid 不前进，因为交换过来的 nums[mid] 是未知的，需要在下一轮重新处理。

循环不变量

  • nums[0..low-1] 全是 0
  • nums[low..mid-1] 全是 1
  • nums[high+1..n-1] 全是 2
  • nums[mid..high] 是未处理的元素

循环结束条件：mid > high，即未处理区间为空。

Mermaid 图：三路划分状态机

完整代码

public class Solution3 {
    public void sortColors(int[] nums) {
        int low = 0;         // [0, low) 全是 0
        int mid = 0;         // [low, mid) 全是 1，mid 是当前处理位置
        int high = nums.length - 1;  // (high, n-1] 全是 2

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, mid, low);
                low++;
                mid++;  // [low, mid) 扩展了一个 1（原来 nums[low] 是 1）
            } else if (nums[mid] == 1) {
                mid++;  // 1 已经在中间区域，直接前进
            } else {  // nums[mid] == 2
                swap(nums, mid, high);
                high--;
                // 注意：mid 不前进，因为交换过来的 nums[high] 还未处理
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();

        int[] nums1 = {2, 0, 2, 1, 1, 0};
        sol.sortColors(nums1);
        System.out.println(Arrays.toString(nums1)); // [0, 0, 1, 1, 2, 2]

        int[] nums2 = {2, 0, 1};
        sol.sortColors(nums2);
        System.out.println(Arrays.toString(nums2)); // [0, 1, 2]

        int[] nums3 = {0};
        sol.sortColors(nums3);
        System.out.println(Arrays.toString(nums3)); // [0]

        int[] nums4 = {1};
        sol.sortColors(nums4);
        System.out.println(Arrays.toString(nums4)); // [1]

        // 全 0
        int[] nums5 = {0, 0, 0};
        sol.sortColors(nums5);
        System.out.println(Arrays.toString(nums5)); // [0, 0, 0]
    }
}

复杂度分析

  • 时间复杂度：O(n)。mid 和 high 各自只移动 n 次（mid 单调增，high 单调减），总移动次数 <= 2n。
  • 空间复杂度：O(1)。原地操作。

五、举一反三

题号题目关联点
215数组中第 K 个最大元素快排 partition（两路），三路 partition 处理重复
280摆动排序原地重排，类似分区思想
324摆动排序 II三路分区变种
912排序数组手写快排，partition 是核心

三路快排（处理大量重复元素时性能更好）：

void quickSort3Way(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = arr[lo];
    int lt = lo, gt = hi, i = lo + 1;
    while (i <= gt) {
        if (arr[i] < pivot) swap(arr, i++, lt++);
        else if (arr[i] > pivot) swap(arr, i, gt--);
        else i++;
    }
    // [lo, lt-1] < pivot, [lt, gt] == pivot, [gt+1, hi] > pivot
    quickSort3Way(arr, lo, lt - 1);
    quickSort3Way(arr, gt + 1, hi);
}

六、踩坑实录

坑一：处理 2 时 mid 也前进

这是最常见的错误。当 nums[mid] == 2 时，我们把 nums[mid] 与 nums[high] 交换，然后 high--。此时 nums[mid] 变成了原来的 nums[high]，它的值未知（可能是 0、1 或 2），需要在下一轮继续处理，所以 mid 不能前进。如果写成 swap(nums, mid, high); high--; mid++;，就会把一个未处理的元素直接放进"已处理"区域，导致错误。

坑二：初始状态理解错误

初始时 low = 0, mid = 0，意味着"0区间"和"1区间"都是空的，这是正确的初始状态。不要把 low 和 mid 初始化为不同的值，那样会破坏循环不变量。

坑三：循环结束条件

循环条件是 mid <= high（不是 mid < high）。当 mid == high 时，nums[mid] 还有一个元素需要处理，用 < 会漏掉最后一个元素。

坑四：与处理 0 时的对称性混淆

处理 0 时（swap(mid, low) 后 mid++）：因为 [low, mid) 全是 1，所以 nums[low] 在交换前就是 1，swap 后 nums[mid] = 1，mid++ 后 nums[mid-1] = 1，1 区间正确扩展。

处理 2 时（swap(mid, high) 后 high-- 但 mid 不动）：因为 (high, n-1] 全是 2，但 [mid, high] 是未处理区间，nums[high] 的值未知，swap 后 nums[mid] 也未知，需要再处理。

这种不对称性是三路划分最容易出错的地方。

七、总结

荷兰国旗三路划分是双指针技术在原地分区问题上的经典应用。它维护三个指针（low, mid, high），定义清晰的循环不变量，每步处理 mid 指向的元素，把数组分成三个有序区间。

关键要点：

  1. 处理 0：向前交换，low++ 且 mid++（交换来的是 1，可以直接跳过）
  2. 处理 1：mid++ 即可
  3. 处理 2：向后交换，high--，mid 不动（交换来的值未知，需要重新处理）

这个算法是三路快排 partition 的核心，理解了它，就理解了为什么三路快排在大量重复元素时比普通快排快。

编辑此页
最近更新:
贡献者: xiaozhangge