Dutch National Flag Problem 荷兰国旗问题，该问题由荷兰计算机科学家Dijkstra所提出

问题描述

Dutch National Flag Problem 荷兰国旗问题描述了这样一个问题：荷兰国旗由红、白、蓝三种颜色组成。现在给定n个这三种颜色的小球，且乱序排列在一起。现期望对这些小球进行排序，使得所有相同颜色的球在一起，且颜色顺序依次为红、白、蓝。该问题对于排序算法的设计具有重要意义

事实上LeetCode的第75题——颜色分类。其本质上就是一个荷兰国旗问题

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序。使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色
必须在不使用库的sort函数的情况下解决这个问题

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]

提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

解决方案

计数排序

由于待排序元素只有三种：0、1、2。故我们可以使用计数排序来解决该问题。即先分别统计0、1、2出现的次数，然后重写整个数组即可

/**
 * 计数排序
 */
class Solution {
    public void sortColors(int[] nums) {
        int num0 = 0;
        int num1 = 0;
        int num2 = 0;
        for (int num : nums) {
            if( num==0 ) {
                num0++;
            } else if (num == 1) {
                num1++;
            } else if (num == 2) {
                num2++;
            }
        }

        for (int i=0; i< nums.length; i++) {
            if( num0>0 ) {
                nums[i] = 0;
                num0--;
            } else if( num1>0 ) {
                nums[i] = 1;
                num1--;
            } else if( num2>0 ) {
                nums[i] = 2;
                num2--;
            }
        }
    }
}

单指针

我们先将所有的0交换到数组的头部，然后再将所有的1再交换到这些的0后面。这样我们就完成了排序。具体地：

在第一轮遍历中，我们使用一个指针p用于表示数组该位置之前的元素全为0。显然初始状态指向的是数组0位置。当遍历过程中，每发现一个0时，即将当前元素与p指针所指向的元素进行交换。并同时将指针p向后移动一位，以指向下一个位置
当第一轮遍历结束后，p指针之前的元素显然全部是0。而p指针所指向的元素及其后面元素只可能是1和2。故此时我们只需从p指针开始继续遍历。将后面的1交换到p指针位置处，同时将指针p向后移动一位，以指向下一个位置

/**
 * 单指针
 */
class Solution {
    public void sortColors(int[] nums) {
        int p = 0;
        // 先把0交换到指针p所指示的位置处
        for(int i=0; i<nums.length; i++) {
            if( nums[i]==0 ) {
                swap(nums, i, p);
                p++;
            }
        }

        // 此时p之前的元素已经全部为0, 故只需从p开始继续遍历
        // 将1交换到指针p所指示的位置处
        for(int i=p; i<nums.length; i++) {
            if( nums[i]==1 ) {
                swap(nums, i, p);
                p++;
            }
        }
    }

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

双指针

同时移动0、1

通过单指针的思路，我们不难想到。我们是不是可以用两个指针同时移动0、1。这样只需一轮遍历即可。即用p0指针来交换0、用p1指针来交换1。这样p0指针之前的位置都是0，而p0指针到p1指针之前的位置都是1。显然这两个指针初始状态均为0。具体地

当我们遍历过程中遇到1时，显然非常简单。直接将当前元素与p1位置元素进行交换即可。同时将p1指针向后移动一位，以指向下一个位置
当我们遍历过程中遇到0时，如果p0、p1指针均指向相同位置时，我们只需将当前元素与p0位置元素进行交换即可。同时将p0、p1指针均向后移动一位，以指向下一个位置;但当如果p0在p1指针前面时，此时说明p0指针所指向的元素一定是1。故当我们将当前元素与p0位置元素进行交换后，会导致原p0指针指向的1被放置到了当前遍历的位置上。所以此时还需要再进行一次交换，即将当前遍历位置上最新元素再次与p1指针进行交换。随后同时将p0、p1指针均向后移动一位，以指向下一个位置。示意图如下所示

/**
 * 双指针: 同时移动0、1
 */
class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        for(int i=0; i<nums.length; i++) {
            // 如果当前元素为1, 直接将其交换到p1指针处
            if( nums[i]==1) {
                swap(nums, i, p1);
                p1++;
            } else if( nums[i]==0 ) {
                // 如果当前元素为0, 直接将其交换到p0指针处
                swap(nums, i, p0);  // (1) 处
                // 如果p0、p1指针指向不是同一个位置, 则说明p0位置原先指向的是1
                if( p0<p1 ) {
                    // 由于(1)处把1交换到i位置, 故需要再次将i位置的元素放置到p1指针处
                    swap(nums, i, p1);
                }
                p0++;
                p1++;
            }
        }
    }

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

同时移动0、2

事实上，我们还可以使用两个指针：p0、p2，以实现同时将0、2移动到数组的头部、尾部。即用p0指针来交换0、用p2指针来交换2。这样p0指针之前的位置都是0，而p2之后的位置都是2。显然这两个指针初始状态分别为0、nums.length-1。由于遍历过程是从左到右的，而p2指针是从右到左的。故遍历位置时一旦超过p2指针就可以终止了，具体地

当我们遍历过程中遇到0时，显然非常简单。直接将当前元素与p0位置元素进行交换即可。同时将p0指针向后移动一位，以指向下一个位置
当我们遍历过程中遇到2时，同样需要将当前元素与p2位置元素进行交换。同时将p2指针向前移动一位，以指向前一个位置。但问题来了，由于p2指针原先指向的元素未被遍历过。所以它可能是0、1、2中的任意一个。所以当该元素被交换当前遍历位置后，我们还需要继续处理该元素，而不能直接去遍历下一个位置的元素

/**
 * 双指针: 同时移动0、2
 */
class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p2= nums.length-1;

        for(int i=0; i<nums.length; i++) {
            // 如果当前元素为2, 直接将其交换到p2指针处
            while (i<=p2 && nums[i]==2) {
                swap(nums, i, p2);
                p2--;
            }

            // 如果当前元素为0, 直接将其交换到p0指针处
            if( nums[i]==0 ) {
                swap(nums, i, p0);
                p0++;
            }
        }
    }

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

xyZGHio

浅谈Dutch National Flag Problem荷兰国旗问题

问题描述

解决方案

计数排序

单指针

双指针

同时移动0、1

同时移动0、2