题目的主要信息：

将输入字符串中的字符按如下规则排序：

英文字母从 A 到 Z 排列，不区分大小写。
同一个英文字母的大小写同时存在时，按照输入顺序排列。
非英文字母的其它字符保持原来的位置。

方法一：

首先我们对字符串中的英文字母进行排序，由于统一英文字母的大小写要按照输入顺序进行排序，所以我们从26个字母表出发，按照字母顺序，每次从str中选出字母保存到alpha中，这样不仅能按照字母表排序还保留了大小写的输入顺序。题目中还要求其他字符保持原来的位置，因此再遍历一遍str，若当前位置为英文字母，则将其替换为排序后的字母，若当前位置不为英文字母则不发生改变。 alt

具体做法：

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main(){
    string str;
    while(getline(cin, str)){//可能有多个输入
        vector<char> alpha;
        for(int i=0;i<26;i++){//对str中出现的英文字母按照字母表的顺序进行排序
            for(int j=0;j<str.size();j++){
                if(str[j]-'a'==i||str[j]-'A'==i){//若str[j]为第i个字母，则加到alpha中
                    alpha.push_back(str[j]);
                }
            }
        }
        for(int i=0,j=0;i<str.size()&&j<alpha.size();i++){//将str中的字母替换为排序后的字母，其他字符的位置不变
            if(isalpha(str[i])){//当前位置是字母位，需要替换
                str[i]=alpha[j++];//替换完后，指针j移动到下一个顺序的字母上
            }
        }
        cout<<str<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历一遍str。
空间复杂度： $O (n)$ ，最坏情况下所有字符都是字母，alpha的大小和str大小相同。

方法二：“稳定“的冒泡排序

首先用字符串ans保存str中的所有英文字母，再对ans进行冒泡排序，因为冒泡排序是稳定的，所以如果我们能统一大小写字母，那么冒泡排序结束后是不改变大小写位置的。我们用compare函数来比较两个字母的大小，从比较两个字母的ASCII码转为比较字母在26个字母表中的位置，这样同一字母的大小写的位置相同，在冒泡排序比较的时候会保留他们的相对位置。对字母排序后输出的方法和方法一相同。

具体做法：

#include<iostream>
#include<vector>
#include<string>

using namespace std;
bool compare(char a,char b){//保留大小写，用字母的相对位置进行比较
    if(a>='a'&&a<='z'){
        a=a-'a';
    }else{
        a=a-'A';
    }
    if(b>='a'&&b<='z'){
        b=b-'a';
    }else{
        b=b-'A';
    }
    return a>b;
}
string bubble_sort(string str){//冒泡排序
    for(int i=0;i<str.size();i++){
        for(int j=0;j<str.size()-i-1;j++){
            if(compare(str[j],str[j+1])){
                swap(str[j],str[j+1]);
            }
        }
    }
    return str;
}
int main(){
    string str;
    while(getline(cin, str)){//可能有多个输入
        string ans;
        for(int i=0;i<str.size();i++){
            if(isalpha(str[i])){
                ans+=str[i];
            }
        }
        ans=bubble_sort(ans);//对字母进行冒泡排序
        for(int i=0,j=0;i<str.size()&&j<ans.size();i++){//将str中的字母替换为排序后的字母，其他字符的位置不变
            if(isalpha(str[i])){//当前位置是字母位，需要替换
                str[i]=ans[j++];//替换完后，指针j移动到下一个顺序的字母上
            }
        }
        cout<<str<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，冒泡排序的时间复杂度为 $O (n^{2})$ 。
空间复杂度： $O (n)$ ，最坏情况下str全为字母，字符串ans的大小和str相同。

题解 | #字符串排序#

题目的主要信息：

方法一：

方法二：“稳定“的冒泡排序