题解 | 字符串排序

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

int ascll(char a){
    if(a>='a'&&a<='z')return a-'a';
    else return a-'A';
}

// string sort1(string s){
//     // 写一个插入排序？
//     for(int i=0;i<s.size()-1;i++){
//         // 进行n-1轮
//         for(int j=i+1;j<s.size();j++){
//             if(ascll(s[j])<ascll(s[i])){
//                 char temp=s[i];
//                 s[i]=s[j];
//                 s[j]=temp;
//             }
//         }
//     }
//     return s;
// }

string sort1(string s){
    int n = s.size();
    for(int i = 0; i < n - 1; i++){
        // 每一轮把当前最大的字母往后“冒”
        for(int j = 0; j < n - 1 - i; j++){
            // 只有当前面的字母 ASCII 差值严格大于后面时才交换
            // 相等时（比如 BabA 中的 B 和 b）不交换，这样就保证了稳定性
            if(ascll(s[j]) > ascll(s[j+1])){
                char temp = s[j];
                s[j] = s[j+1];
                s[j+1] = temp;
            }
        }
    }
    return s;
}

int main(){
    string s;
    while(getline(cin,s)){
        // 思路 存下来不变的位置，把其中的所有字母全部提取出来，排好序再填回去
        vector<int> stop,go; // 记录不动的下标
        string abc=""; // 记录纯字母字符串
        for(int i=0;i<s.size();i++){
            if(!((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')))stop.push_back(i);
            else {
                abc+=s[i];
                go.push_back(i);
            }
        }
        // 怎么排序？写一个排序，稳定的，根据其和a或者A的ASCLL码差排序；
        abc = sort1(abc); //排序好了 装进去
        for(int i=0;i<go.size();i++){
            s[go[i]]=abc[i];
        }
        cout<<s<<endl;
    }
    return 0;
}

排序算法的问题，如何写一个稳定的排序算法？