题解 | #字符串排序#

等会就上考场了兄弟们。沉住气，放轻松。

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

class spair{
public:
	int num;
	char ch;
	spair(int n, char c):num(n), ch(c){}
};

bool cmp(char c1, char c2){
	if(c1 >= 'a' && c1 <= 'z'){
		c1 -= 32;
	}
	if(c2 >= 'a' && c2 <= 'z'){
		c2 -= 32;
	}
	return c1 < c2;
}

int main(){
	string s;
	while(getline(cin, s)){
		vector<spair> v;
		string s1;
		for(int i=0; i<s.size(); i++){
			if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z')){
				s1.push_back(s[i]);
			}else{
				v.push_back(spair(i, s[i]));
			}
		}
		//先对s1排序 注意不能用sort sort是不稳定的
		for(int i=0; i<s1.size()-1; i++){
			bool flag = false;
			for(int j=s1.size()-1; j>i; j--){
				if(cmp(s1[j], s1[j-1])){
					swap(s1[j], s1[j-1]);
					flag = true;
				}
			}
			if(!flag){
				break;
			}
		}
		int loc1 = 0;//现在输出到第几个
		int loc2 = 0;//v中下一个输出第几个
		int loc3 = 0;//s1中下一个输出第几个 
		while(loc1 < s.size()){
			if(loc2 < v.size()){
				if(loc1 == v[loc2].num){
					printf("%c", v[loc2].ch);
					loc2++;
					loc1++;
					continue;
				}
			}
			printf("%c", s1[loc3]);
			loc3++;
			loc1++;
		}
		printf("\n");
	}
	return 0;
}