题解 | 字符串排序（排序的稳定性

sort与stable_sort的使用。

sort底层结合了快速排序、堆排序和插入排序，其中快排属于交换排序。

交换排序主要有快排和冒泡，快排是不稳定的，相同元素可能会交换位置，而冒泡稳定。

#include <bits/stdc++.h>
#include <utility>
#include <vector>
using namespace std;

bool cmpFirstOnly(const pair<char,char> & a,const pair<char,char> & b){
    return a.first<b.first;
}

int main() {
    string s;
    getline(cin,s);
    int n=s.size();
    vector<pair<char,char>> vec;//first aa second aA
    for(int i=0;i<n;i++){
        if(isalpha(s[i])){
            vec.push_back({tolower(s[i]),s[i]});
        }
    }
//方法一：
    //sort(vec.begin(),vec.end(),cmpFirstOnly);//无法通过 快排是不稳定排序
    //用例：gjo%%CGP-A+@-krz~dhxWb$qVev+!W^)~--U+ysdA^ZA~y^SxF!PUu&k
    //错误位置：UuU 应为UUu
    //sort改为stable就可以了！！！stable_sort：相等就保持不变！
	stable_sort(vec.begin(),vec.end(),cmpFirstOnly);//可以通过
/*
//方法二：//可以通过 冒泡是稳定排序
    int m=vec.size();
    for(int i=0;i<m;i++){
        for(int j=0;j+1<m-i;j++){
            if(vec[j].first>vec[j+1].first){
                pair c=vec[j];
                vec[j]=vec[j+1];
                vec[j+1]=c;
            }
        }
    }
*/
    int k=0;
    for(int i=0;i<n;i++){
        if(isalpha(s[i])){
            s[i]=vec[k++].second;
        }
        cout<<s[i];
    }
    return 0;
}