字符串排序（牛客）

题目描述：

编写一个程序，将输入字符串中的字符按如下规则排序。
规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
如，输入： Type 输出： epTy
规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入： BabA 输出： aABb
规则 3 ：非英文字母的其它字符保持原来的位置。
如，输入： By?e 输出： Be?y 
注意有多组测试数据，即输入有多行，每一行单独处理（换行符隔开的表示不同行）

输入：输入字符串

A Famous Saying: Much Ado About Nothing (2012/8).

输出：输出字符串

A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

做题思路：

建立一个结构体数组，单个结构体包含：字符原型，字符转换值，字符在原字符串中的位置

struct Letter{
    char source; //提取出来时的字符原型，排序后重新写入str
    char trans; //统一转换为小写字母，进行一级排序
    int index; //在输入字符串中的位置，用于同级字母的二级排序 
};

遍历字符串

遇到小写字母，例如a时，source是a，trans是a，index就是a在字符串中的位置

遇到大写字母，例如A时，source是A，trans是a，index就是A在字符串中的位置

遇到其他字符，不加入结构体数组

对结构体数组进行二级排序（见sort排序），trans不同时，按照字典排序。当trans相同时，按照index进行排序

排序完成后，将source写回输入字符串对应的index处即可

AC代码：

// 使用二级结构体排序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
struct Letter{
    char source; //提取出来时的字符原型，排序后重新写入str
    char trans; //统一转换为小写字母，进行一级排序
    int index; //在输入字符串中的位置，用于同级字母的二级排序 
};
int isLetter(char c);
bool cmp(Letter a,Letter b);
int main()
{
    char str[1000]; //注意本题100的空间不够，会提示通过20%，发生段错误
    while(gets(str)){
    	vector<Letter> letter;
	    for(int i=0; i<strlen(str); i++){  //将字符串中的字母提取出来,并添加到vector
	    	Letter l;
	        if( isLetter(str[i])==1 ){
	            l.source = str[i];
	            l.trans = str[i];
	            l.index = i; 
	            letter.push_back(l);
	        }
	        if( isLetter(str[i])==2 ){
	            l.source = str[i];
	            l.trans = str[i]+32;
	            l.index = i;
	            letter.push_back(l);
	        }
	    }
	    sort(letter.begin(),letter.end(),cmp);
	    for(int i=0; i<strlen(str); i++){  //将排序后的字母重新写回str 
	    	if(isLetter(str[i])){
	    		str[i] = letter[0].source;
	    		letter.erase(letter.begin());
			}
		}
	    printf("%s\n",str);
	}
    return 0;
}
int isLetter(char c)//小写字母返回1，大写字母返回2，否则返回0
{
    if( c>='a'&&c<='z'){
        return 1;
    }
    if( c>='A'&&c<='Z' ){
        return 2;
    }
    return 0;
}
bool cmp(Letter a,Letter b) //用于sort二级排序 
{
	if( a.trans!=b.trans ){ //不同级字母，对转换后的小写字母按照字典排序 
		return a.trans<b.trans; 
	}else{ //同级字母，按照index进行排序 
		return a.index<b.index;
	}
}