荷兰国旗

2019-02-17 | 阅读：次

荷兰国旗

题目描述

拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。

该问题本身是关于三色球排序和分类的，由荷兰科学家Dijkstra提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag Problem）。

下面是问题的正规描述：现有n个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，使得从左至右，依次是一些红球、一些白球、一些蓝球。

分析与解法

初看此题，我们貌似除了暴力解决并无好的办法，但联想到我们所熟知的快速排序算法呢？

我们知道，快速排序依托于一个partition分治过程，在每一趟排序的过程中，选取的主元都会把整个数组排列成一大一小的部分，那我们是否可以借鉴partition过程设定三个指针完成重新排列，使得所有球排列成三个不同颜色的球呢？

解法一

通过前面的分析得知，这个问题类似快排中partition过程，只是需要用到三个指针：一个前指针begin，一个中指针current，一个后指针end，current指针遍历整个数组序列，当

current指针所指元素为0时，与begin指针所指的元素交换，而后current++，begin++ ；
current指针所指元素为1时，不做任何交换（即球不动），而后current++ ；
current指针所指元素为2时，与end指针所指的元素交换，而后，current指针不动，end– 。

为什么上述第3点中，current指针所指元素为2时，与end指针所指元素交换之后，current指针不能动呢？因为第三步中current指针所指元素与end指针所指元素交换之前，如果end指针之前指的元素是0，那么与current指针所指元素交换之后，current指针此刻所指的元素是0，此时，current指针能动么？不能动，因为如上述第1点所述，如果current指针所指的元素是0，还得与begin指针所指的元素交换。

ok，说这么多，你可能不甚明了，直接引用下gnuhpc的图，就一目了然了：

参考代码如下：

//引用自gnuhpc  
while( current<=end )        
{             
  if( array[current] ==0 )             
   {                 
      swap(array[current],array[begin]);                  
      current++;                  
      begin++;            
   }             
   else if( array[current] == 1 )            
   {                 
      current++;            
   }   
            
   else //When array[current] =2   
   {               
      swap(array[current],array[end]);                
      end--;            
   }      
}  

python实践

#!/usr/bin/env python
# _*_ coding:utf-8 _*_
# 荷兰国旗
# date: 2019/02/17

"""
input: 国旗颜色的乱序排列,输入一个数组 0:代表红球，1：白球， 2：篮球
output: 颜色排序为红黄蓝，依次排序
"""

# 方法一：蛮力法，类似冒泡排序， 当成是一个排序问题来做，只不过其中的数只有0,1,2
def dutch_flag1(flags):
    for i in range(0, len(flags)):
        for j in range(i+1, len(flags)):
            if flags[i] > flags[j]:
                temp = flags[i]
                flags[i] = flags[j]
                flags[j] = temp
    print(flags)
    return flags

# 方法二：使用一种分治的思想，设置三个指针begin, current, end
# 思路：全部以current作为衡量标杆
def dutch_flag2(flags):
    begin = 0
    current = 1
    end = len(flags) - 1
    while current < end:
        if flags[current] == 0:
            temp = flags[current]
            flags[current] = flags[begin]
            flags[begin] = temp
            current += 1
            begin += 1
        if flags[current] == 1:
            current += 1
        if flags[current] == 2:
            temp = flags[current]
            flags[current] = flags[end]
            flags[end] = temp
            end -= 1
    print(flags)
    return flags

if __name__ == '__main__':
    flags = [1, 2, 0, 0, 0, 2, 1, 1, 0, 2, 2, 1, 0]
    dutch_flag2(flags)

运行结果

E:\YanJiuSheng-download\2a\python-3.6.7-embed-amd64\python.exe 
H:/python-workspace/algorithm/algorithm/荷兰国旗/Dutch_flag.py
[0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]

Process finished with exit code 0