O(N)的做法

冒泡排序属于O(n^2)的做法，考虑用hash将复杂度降为O(n)
#include <iostream>
#include <algorithm>
#include <string>
#include </string></algorithm></iostream>

using namespace std;

bool isAlpha(char a) {
//是否为字母
if (a < 65 || a > 90 && a < 97 || a > 122) return false;
return true;
}

/*
用排序做的问题在于，AFfaf,若交换a与F, 则改变了原来的 f 顺序，因此要考虑用数据结构记录同一字符出现的顺序
采用hash， O(n)的做法如下：
*/
void dealStr(string &s) {
if (s.empty()) return;
//记录所有出现字母的位置
vector<int> location;
//记录每个字符出现的顺序
unordered_map<char, string> mp;
for (int i = 0; i < s.length(); ++i) {
if (isAlpha(s[i])) {
location.push_back(i);
char key = s[i] >= 97 ? (s[i] - 32) : s[i];
if (mp.find(key) == mp.end()) {
mp[key] += s[i];
}
else {
mp[key] += s[i];
}
}
}
//得到所有字符顺序
string res_tmp;
for (char i = 'A'; i <= 'Z'; ++i) {
if (mp.find(i) != mp.end()) res_tmp += mp[i];
}
int idx = 0;
for (int i = 0; i < location.size(); ++i) {
s[location[i]] = res_tmp[idx];
idx++;
}
cout << s << endl;
}</int>

int main()
{
string s;
while (getline(cin, s)) {
dealStr(s);
}
return 0;
}