题目的主要信息：

• 将输入多组测试字符串中的字符按如下规则排序后输出：
  1. 英文字母从 A 到 Z 排列，不区分大小写
  2. 同一个英文字母的大小写同时存在时，按照输入顺序排列
  3. 非英文字母的其它字符保持原来的位置

方法一：冒泡排序

具体做法：

我们利用冒泡排序的思想，对字母之间交换顺序即可。最多有字符串长度$nn$轮交换，这是最外层循环，内层循环从从0开始，每次找到相邻的两个字母，比较大小，如果位置相反则交换，一直到最后，像冒泡排序一样，每次可以保证最后的那个元素顺序是正确的，依次往前确认最后的元素，直到第一个就排好了。

因为我们每次找的时候相邻的字母，跳过了其他字符，因此其他字符的位置不变。

比较字母的大小，我们采用字符分别减去大小写各自的A/a，这样比较它们在字母表中的索引，即可比较不区分大小写的大小。

#include<iostream>
#include<string>
using namespace std;

bool ischar(char c){ //判断是否是字符
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

int toint(char c){ //将大小写字母转为同样的数字起跑线
    return (c >= 'a' && c <= 'z') ? c - 'a' : c - 'A';
}
int main(){
    string s;
    while(getline(cin, s)){
        int next;
        for(int i = s.length() - 1; i > 0; i--){
            for(int j = 0; j < i; j++){
                if(ischar(s[j])){ //首先要是字母才可以交换位置
                    next = j + 1;
                    while(next <= i && !ischar(s[next]))
                        next++; //找到下一个字母
                    if(ischar(s[next]) && toint(s[j]) > toint(s[next])){
                        swap(s[j], s[next]); //交换
                    }
                }
            }
        }
        cout << s <<endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，冒泡排序两层循环
• 空间复杂度：$O(1)O(1)$，无额外空间，字符串s属于必要空间

方法二：桶排序思想

具体做法：

介于字母只有26个，是有限的，我们可以用桶排序的思想，因为字符串比较虽然不区分大小写，但是字符串中还是要区分大小写，因此会稍微复杂一点。

我们准备第一维大小是26的二维数组作为桶，遇到一个字母就将其push进相应的索引后面，同时我们用一个字符串长度相同的数组（初始化所有位为-1）记录出现字母的下标。其后，准备两个指针遍历桶，然后遍历字符串，当遇到记录的下标为-1，则意味着这个位置是其他字符，不用管，我们只处理下标不为-1的。对于记录不为-1的，我们根据遍历到的桶中的位置，修改字符串为该字符，直到桶中元素用完。

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    string s;
    while(getline(cin, s)){
        vector<vector<char> > table(26);
        vector<int> index(s.length(), -1);
        for(int i = 0; i < s.length(); i++){
            if(s[i] >= 'a' && s[i] <= 'z'){ //小写
                index[i] = s[i] - 'a'; //记录这是哪一个字母索引
                table[s[i] - 'a'].push_back(s[i]); //将字母加入桶中
            }
            if(s[i] >= 'A' && s[i] <= 'Z'){ // 大写
                index[i] = s[i] - 'A'; //记录这是哪一个字母索引
                table[s[i] - 'A'].push_back(s[i]);  //将字母加入桶中
            }
        }
        int x = 0, y = 0; //table数组的下标
        for(int i = 0; i < index.size(); i++){
            if(index[i] != -1){
                while(y == table[x].size()){ //跳过为0的桶
                    x++;
                    y = 0;
                }
                s[i] = table[x][y]; //每次加入一个桶中元素
                y++;
            }
        }
        cout << s <<endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，加字符加入到桶中是$O(n)O(n)$，修改字符串字母的位置内外最坏循环$2\ast n2*n$次
• 空间复杂度：$O(n)O(n)$，记录字符的桶及记录下标的数组长度为$nn$