题目描述

编写一个程序，将输入字符串中的字符按如下规则排序。
规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
如，输入： Type 输出： epTy
规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入： BabA 输出： aABb
规则 3 ：非英文字母的其它字符保持原来的位置。
如，输入： By?e 输出： Be?y

方法1：

提出字母和非字母两类数据，将非字母部分的char和索引pos放入pair中，字母部分排序完后将非字母部分插入。
字母部分排序，由于字母相同大小写不听时顺序不变，所以需要是个稳定的排序，用了基础的冒泡，都换算成大写字母，比较大小，大的往下沉。

#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
bool cmp(char a,char b){
    if(a>='a'&&a<='z') a=a-('a'-'A');
    if(b>='a'&&b<='z') b=b-('a'-'A');
    return a>b;
}
int main(){
    string s;
    while(getline(cin,s)){
        vector<pair<char,int> > temp;
        string ans;
        for(int i=0;i<s.size();i++){
            if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
                ans+=s[i];
            else
                temp.push_back({s[i],i});//保存非字母和对应的索引
        }
        for(int i=0;i<ans.size()-1;i++){
            bool flag=false;
            for(int j=0;j<ans.size()-i-j;j++){//冒泡排序（稳定排序）
                if(cmp(ans[j],ans[j+1])) {
                    swap(ans[j],ans[j+1]);
                    flag=true;}//flag标志，没有交换说明已经有序，退出循环
            }
            if(!flag) break;
        }
        for(int i=0;i<temp.size();i++){
            ans.insert(ans.begin()+temp[i].second,temp[i].first);//插入非字母，保持索引位置
            //记一下insert用法str.insert(iterator,string)
        }
        cout<<ans<<endl;
    }

}

方法2：

在提交记录里看到的，从a到z循环，每次循环检查字符串中是否有对应的大写或者小写的字母，有的话push入vector
这样既使得结果是a-z顺序，且同字母时是按出现顺序存入的。
eg： a&bc02 可以认为是 (字母)&(字母)(字母)02
判断原字符串每个元素是否是字母，是就认为是坑，将排好序的字母依次放入(子母)的坑里，这样非字母就没有受影响
然后
图片说明

方法3：

我也不知道我为什么要写这个方法
算是在忽略非字母的情况下对字母部分冒泡排序，非字母信息不用另外保存
将字母部分和索引作为pair存进vector，对vector排序，进而通过索引对字符串排序，每次交换完记得更新索引

#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
bool cmp(char a,char b){
    if(a>='a'&&a<='z') a=a-('a'-'A');
    if(b>='a'&&b<='z') b=b-('a'-'A');
    return a>b;
}
int main(){
    string s;
    while(getline(cin,s)){
        vector<pair<char,int> > temp;
        for(int i=0;i<s.size();i++){
            if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
                temp.push_back({s[i],i});//保存字母和对应的索引
        }
        //冒泡排序（稳定排序）
        for(int i=0;i<temp.size()-1;i++){//只交换字母部分，对字母部分排序，空过其他字符
            bool flag=false;
            for(int j=0;j<temp.size()-1-i;j++){
                if(cmp(temp[j].first,temp[j+1].first)) {//这里是j!!!!
                    swap(s[temp[j].second],s[temp[j+1].second]);//交换s中的位置
                    swap(temp[j],temp[j+1]);//交换vector的位置，因为是按照vector排序的
                    swap(temp[j].second,temp[j+1].second);//s交换了，所以pair对应的索引交换
                    flag=true;}
            }
            if(!flag) break;
        }
        cout<<s<<endl;
    }

}