Home > Archives > Dutch National Flag问题 - One Pass算法解读

Dutch National Flag问题 - One Pass算法解读

Publish:

荷兰三色旗问题(以下简称DNF问题),是Dijkstra提出的一个经典问题,让我们先来看看它的描述:

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

解题思路

乍眼一看,这个问题就是一个简单的排序,我们写一个快排也很简单。

但问题在于数组中只有三种元素,按照排序算法来写肯定会有较大的性能损失。

于是我们可以很直观的想到一个Two Pass算法,即,第一次遍历统计数组得到0,1,2的数目,第二次遍历按序填充0,1,2。

那么有没有One Pass的算法呢?

答案是有的,不过理解起来有一定的难度。

One Pass算法介绍

让我们先看算法吧。

    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int i = 0;
        
        while (i <= right) {
            if (nums[i] == 0) {
                nums[i] = nums[left];
                nums[left] = 0;
                i++;
                left++;
            }
            else if (nums[i] == 2) {
                nums[i] = nums[right];
                nums[right] = 2;
                right--;
            }
            else {
                i++;
            }
        }
    }

我先大致讲解算法的思路,然后详述算法中tricky的点。

设置一个left和right指针,left的左边是已排好序的0,right右边是已排好序的2,由于遍历开始之前,没有排好序的0和2,所以left指向0,right指向n - 1。

以指针i开始遍历数组

如果遇到0,将nums[i]与nums[left]互换,left++, i++

如果遇到2,将nums[i]与nums[right]互换,right–

如果遇到1,将i++

这样在一次遍历以后,0被划分到了左边,2被划分到了右边,中间自然只有1了。

不细想的话似乎很明了,但要真正的透彻理解,还需要下一番功夫。

One Pass算法详解

首先对于上述的算法,让我们考虑一个问题。

为什么索引i与left的值互换时,i要自增,与right的值互换时却不能自增?

下面的讲解我就要解释这个问题。

首先在这个算法中,让我们把整个数组分成4个部分:

1 排好序的0
2 排好序的1
3 未排序的部分
4 排好序的2

如下图所示:

数组分区

在最开始的时候,只有未排好序的部分,即下图:

初始分区

一旦开始遍历

当遇到0时,将left指向的元素与i指向的元素互换

用不用再次比较互换之后i指向的元素呢?答案是不用。

因为互换之后

i不可能指向一个2,因为如果i指向一个2,它在遍历到i之前已经被换到right之后了,而right是不可能小于i的

如果i指向一个1,说明排好序的0之后的第一位刚好是一个1,我们所做的操作扩大了排好序的0的个数,

如果i指向一个0,一定意味着i之前的元素全部是0并且i和start此时相等,因为在遍历到i之前所有的0已经被加入到left之前已排好序的0中,如果此时left仍指向一个未排好序的0,那么这个0只能是i指向的元素

因此,在nums[i]与nums[left]交换后,i和left一样,都可以自增,因为索引i和left元素互换后可能出现的两种情况都不需要对索引i的元素重新进行操作,它已排好序。

当遇到1时,直接将i自增,从上图可以看出这样做时正确的,它缩小了未排序分区,扩大了排好序的1分区

当遇到2时,将i指向的元素与right指向的元素互换,将right自减。

这扩大了已排好序的2分区,但我们不能对i进行自增。

因为我们需要再次判断互换后的i是否仍指向2,如果仍指向2,继续将它与right互换。

如果不这样做的话,就会出现下面这种情况:

错误分区

由于right或者自减,i或者自增,所以他们最后总会相遇,算法结束。

总结

DNF问题是一个经典问题,它还是主要使用了快排的分区、交换的思想,注意体会它的思想,把握它的细节。

声明: 本文采用 BY-NC-SA 授权。转载请注明转自: Dutch National Flag问题 - One Pass算法解读 - 无火的余灰