荷兰国旗问题：

现有红，白，蓝三个不同颜色的小球，乱序排列在一起，重新排列这些小球，使得红白蓝三色的同颜色的球在一起。

问题分析：

问题转换为：给定数组A[0,1,...,N-1]，元素只能取0，1，2三个值，设计算法使得数组重新排列成“000...111..222”的形式。

可以使用三个游标，begin=0，cur=0，end=N-1。

程序实现：

1 /*************************************** 2 FileName HollandFlag.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/4 5 ****************************************/ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           12 13 using namespace std;14 15 void HollandFlag(int* A,int size){16 int begin = 0;17 int end = size - 1;18 int cur = 0;19 while(cur <= end){20 if(A[cur] == 2){21 swap(A[cur],A[end]);22 end --;23 }24 else if(A[cur] == 1){25 cur ++;26 }27 else if(A[cur] == 0){28 swap(A[cur],A[begin]);//这里简化了步骤，提醒：cur与begin是否相同，分情况考虑29 begin ++;30 cur ++;31 }32 }33 }34 int main()35 {36 int a[] = { 0,1,2,0,0,2,1,2,1,2,2,1,1,0};37 int size = sizeof(a)/sizeof(int);38 for(int i=0;i
          
         
        
       
      
     

运行结果：

转载请注明出处：

C++博客园：godfrey_88