BJFU_数据结构习题_296砾石的交换排序

浅浅的花香味﹌ 2023-05-29 13:09 85阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 296砾石的交换排序 ###

**描述**  
设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。  
**输入**  
多组数据，每组数据两行。第一行为砾石的数量n，第二行有n个字母，代表每个砾石的颜色（字母之间用空格分隔，R代表红色，W代表白色，B代表蓝色）。当n等于0时，输入结束。  
**输出**  
每组数据输出一行。为重新排序后的砾石序列。每两个字母之间用空格隔开。  
**输入样例 1**  
5  
R W R B R  
3  
B W R  
0  
**输出样例 1**  
R R R W B  
R W B

#include<iostream>
    using namespace std;
    void Exchange(char &x,char &y)	//注意引用符号&，形参变化，改变实参
    {
        
        char t;
        t=x;
        x=y;
        y=t;
    }
    void Sort(char c[],int n)	 //对砾石调整RWB，依次遍历，时间复杂度为O(1)
    {
        
        int i=0,j=0,k=n-1;        	 //从左往右依次检查砾石c[j]
        while(j<=k)                	 //c[i]左边都是R，c[k]右边都是B。R,B放对位置，W也就对了
        {
            
            if(c[j]=='R')            //c[j]是R                
            {
        
                Exchange(c[j],c[i]); //并入左边R区域
                i++;                 //指针i后移
                if(j<i)	
                    j=i;
            }
            else if(c[j]=='B')       //c[j]是B
            {
        
                Exchange(c[j],c[k]); //并入右边B区域
                k--;                 //指针k前移
            }
            else 
                j++;                 //不需交换，指针后移
        }        
    }
    int main()
    {
        
        int n,i;
        while(cin>>n&&n!=0)
        {
        	
    	char c[100];
    	for(i=0;i<n;i++)
                cin>>c[i];      	 //输入砾石的编号
            Sort(c,n);            	 //调整排序
            for(i=0;i<n-1;i++)
                cout<<c[i]<<" ";
            cout<<c[n-1]<<endl;      //区分空格和回车
        }
        return 0;
    }

### 代码2 ###

#include<iostream>
    using namespace std;
    void Exchange(char &x,char &y)	//注意引用符号&，形参变化，改变实参
    {
        
        char t;
        t=x;
        x=y;
        y=t;
    }
    void Sort(char c[],int n)	 //对砾石调整RWB，依次遍历，时间复杂度为O(1) RRRRRR W R B R
    {
        
        int i=0,j=0,k=n-1;        	 //从左往右依次检查砾石c[j]
        while(j<=k)                	 //c[i]左边都是R，c[k]右边都是B。R,B放对位置，W也就对了
        {
            
            if(c[j]=='R')            //c[j]是R                
            {
        
            	while(c[i]=='R')
    			    i++;                 //指针i右移直到一个非R的位置 
    			if(j<i)				
                	j=i;
    			else
    			{
        
    				Exchange(c[j],c[i]); //并入左边R区域
                	i++;                 //指针i右移 
                	if(j<i)				
                	    j=i;
    			}
            }
            else if(c[j]=='B')       //c[j]是B
            {
        
            	while(c[k]=='B')
            		k--;                 //指针k 
                Exchange(c[j],c[k]); //并入右边B区域
                k--;                 //指针k 
            }
            else   				  	 //c[j]是W
                j++;                 //不需交换，指针后移
        }        
    }
    int main()
    {
        
        int n,i;
        while(cin>>n&&n!=0)
        {
        	
    		char c[100];
    		for(i=0;i<n;i++)
                cin>>c[i];      	 //输入砾石的编号
            Sort(c,n);            	 //调整排序
            for(i=0;i<n-1;i++)
                cout<<c[i]<<" ";
            cout<<c[n-1]<<endl;      //区分空格和回车
        }
        return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com