题解 | 字符串排序

思路就是把字母挑出来排序再覆盖回去，难点在不改变原本位置。首先纪念下我殉了的思路，用priority——queue排序，但没能解决保持位置不变的问题。

#include <cstdlib>
#include <functional>
#include <future>
#include <iostream>
#include<bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;
struct Compare{
    bool operator()(pair<char,bool>&a,pair<char,bool>&b){
        return a.first>b.first;
    }

};

int main() {
    string s;
    getline(cin,s);
    // 给数据打标签，大写转小写，位置打标记
    int n=s.size();
    vector<bool>isAZ(n,false);
    priority_queue<pair<char,bool>,vector<pair<char,bool>>,Compare>sortAZ;
    for(int i=0;i<s.size();i++){
        if(s[i]>='a'&&s[i]<='z'){
            isAZ[i]=true;
            s[i]-=32;
            sortAZ.push(pair<char,bool>{s[i],true});
            continue;
        }
        if(s[i]>='A'&&s[i]<='Z'){
            isAZ[i]=true;
            sortAZ.push(pair<char,bool>{s[i],false});
            continue;
        }
    }
    // 单独把字母提出了排序再输出回去
    for(int i=0;i<s.size();i++){
        if(isAZ[i]==true){
        if(sortAZ.top().second==true){
        char a=sortAZ.top().first+32;
        cout<<a;}
        else cout<<sortAZ.top().first;
        sortAZ.pop();
        }
        else cout<<s[i];
    }
    
}
// 64 位输出请用 printf("%lld")

正确解法是两端循环遍历，直接暴力，逐个字母寻找并写入数组。

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

int main() {
    string s;
    getline(cin,s);
    char vec[1000];
    int k=0;
    for(int i=0;i<26;i++){
        for(int j=0;j<s.size();j++){
            if(s[j]=='a'+i||s[j]=='A'+i){
                vec[k++]=s[j];
            }
        }
    }

    k=0;
    for(int i=0;i<s.size();i++){
        if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
        s[i]=vec[k++];

        cout<<s[i];
    }
}
// 64 位输出请用 printf("%lld")