快排-荷兰国旗

在使用partition-exchange排序算法时，如快速排序算法，我们会遇到一些问题，比如重复元素太多，降低了效率，在每次递归中，左边部分是空的(没有元素比关键元素小)，而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。这时我们可以多分一个区，即，小于区，等于区，大于区。（传统快排为小于区和大于区）

下面我们通过一个经典例题来练习这种思想。

荷兰国旗问题

”荷兰国旗难题“是计算机科学中的一个程序难题，它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。

　　现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

样例输入

  

   

    

     

    
    

     

      3
     
    
   

    

     

    
    

     

      BBRRWBWRRR
     
    
   

    

     

    
    

     

      RRRWWRWRB
     
    
   

    

     

    
    

     

      RBRW
     
    
  
 

样例输出

  

   

    

     

    
    

     

      RRRRRWWBBB
     
    
   

    

     

    
    

     

      RRRRRWWWB
     
    
   

    

     

    
    

     

      RRWB
     
    
  
 

思路：

现在我们的思路就是把未排序时前部和后部分别排在数组的前面和后面，那么中部自然就排好了。

设置两个标志位head指向数组开头，tail指向数组末尾，now从头开始遍历：

(1)如果遍历到的位置为1，那么它一定是属于前部，于是就和head交换值，然后head++，now++；

(2)如果遍历到的位置为2，说明属于中部，now++；

(3)如果遍历到的位置为3，说明属于后部，于是就和tail交换值，然而，如果此时交换后now指向的值属于前部，那么就执行(1)，tail--；

废话不多说，上代码。

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int maxn = 100 + 5;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int n;
     
    
   

    

     

    
    

     

      string str;
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
 cin>>n;
     
    
   

    

     

    
    

     
 while(n--){
     
    
   

    

     

    
    

     
 cin>>str;
     
    
   

    

     

    
    

     
 int len=str.size();
     
    
   

    

     

    
    

     
 int now=0,ans=0;
     
    
   

    

     

    
    

     
 int head=0,tail=len-1;
     
    
   

    

     

    
    

     
 while(now<=tail){
     
    
   

    

     

    
    

     
 if(str[now]=='R'){
     
    
   

    

     

    
    

     

       swap(str[head],str[now]);
     
    
   

    

     

    
    

     

       head++;
     
    
   

    

     

    
    

     

       now++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(str[now]=='W'){
     
    
   

    

     

    
    

     

       now++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else{
     
    
   

    

     

    
    

     

       swap(str[now],str[tail]);
     
    
   

    

     

    
    

     

       tail--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<str<<endl;
     
    
   

    

     

    
    

     

       }return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

其实只要解题的话统计三个数量就好了，但是分三区的思想一定要有。

快排分三区以后降低了递归规模，避免了最差情况，性能得到改进。

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/81772701