给定一个字符串里面只有"R" "G" "B" 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。 要求：空间复杂度是O(1)，且只能遍历一次字符串。
题目：给定一个字符串里面只有"R" "G" "B" 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。 要求：空间复杂度是O(1)，且只能遍历一次字符串。
解析：本题的解法类似于快速排序partition算法，对于字符串str，利用两个下标start1,end1,start1初始时指向字符串的头部，end1初始时指向字符串的尾部，当str[start1]!='R'，str[end1]!='B'时候，不能简单像原来的partition那样直接作交换，而是要根据不同的情况做不同的处理，因为字符串中还包含第三类字符'G'。
C ++代码如下：
#include<iostream>#include<cstring>using namespace std;const int MAXLEN=100;//字符串的最大长度void Set_RGB(char *str);//位置调整函数，借助了快排的partition函数思想int main(){char str[MAXLEN+1];cin>>str;//输入只包含'R','G','B'的字符串Set_RGB(str);cout<<str<<endl;//输出调整过的字符串return 0;}void Set_RGB(char *str){if(str==NULL)return;int len=strlen(str);int start1,end1,start2,end2;char tmp;start1=start2=0;end1=end2=len-1;while(true){while(str[start1]=='R'&&start1<=end1){start1++;if(start1>start2)start2=start1;//保证start2始终等于或大于start1}while(str[end1]=='B'){end1--;if(end1<end2)end2=end1;//保证end2始终等于或小于end1}if(start1>end1)break;if(str[start1]=='B'&&str[end1]=='R')//直接交换{tmp=str[start1];str[start1]=str[end1];str[end1]=tmp;}else if(str[start1]=='G'&&str[end1]=='R') {//先交换tmp=str[start1];str[start1]=str[end1];str[end1]=tmp;while(end2>start2)//然后用end2向前扫描知道遇到第一个不是'G'的字符{if(str[end2]!='G')break;end2--;}if(start2<end2)//若start2<end2，则end2和end1位置的字符交换{tmp=str[end2];str[end2]=str[end1];str[end1]=tmp;}}else if(str[start1]=='B'&&str[end1]=='G'){//先交换tmp=str[start1];str[start1]=str[end1];str[end1]=tmp;while(start2<end2)//然后用start2向前扫描知道遇到第一个不是'G'的字符{if(str[start2]!='G')break;start2++;}if(start2<end2)//若start2<end2，则start2和start1位置的字符交换{tmp=str[start2];str[start2]=str[start1];str[start1]=tmp;}}else{while(start2<=end2)//分别用start2和end2从前，从后，向后，向前扫描第一个不是'G'的字符{if(str[start2]!='G'&&str[end2]!='G')break;if(str[start2]=='G')start2++;if(str[end2]=='G')end2--;}if(start2==end2&&str[start2]=='R')//若两下标相遇，并且是字符'R'，则和start1位置'G'的字符交换{tmp=str[start2];str[start2]=str[start1];str[start1]=tmp;}if(start2==end2&&str[end2]=='B')//若两下标相遇，并且是字符'B'，则和end1位置'G'的字符交换{tmp=str[end2];str[end2]=str[end1];str[end1]=tmp;}if(start2<end2)//若两下标相遇，分别交换start1与start2,end1与end2位置的字符{tmp=str[end2];str[end2]=str[end1];str[end1]=tmp;tmp=str[start2];str[start2]=str[start1];str[start1]=tmp;}}if(start2>=end2)//若start2与end2相遇，则扫描结束，保证扫描字符串一遍，因为扫描过程中start2始终在start1后面,end2始终在end1前面，break;}}