题解 | #字符串排序#

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

bool isletter(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

bool issame(const char a, const char b) {
    
    char a1 = (a>='a'&&a<='z') ? a : a+32;
    char b1 = (b>='a'&&b<='z') ? b : b+32;
    return a1 == b1;
}

bool comp(const char a, const char b) {
    if (issame(a,b))
        return false;
    char a1 = (a>='a'&&a<='z') ? a : a+32;
    char b1 = (b>='a'&&b<='z') ? b : b+32;
    return a1 < b1;
}

void maopao(vector<char>& letters) {
    int len = letters.size();
    for (int i = 1; i < len; i++) {
        for (int j = i; j >= 1; j--) {
            if (comp(letters[j], letters[j-1]))
                swap(letters[j], letters[j-1]);
            else
                break;
        }
    }
}

int main() {
    string s;
    while (getline(cin, s)) {
        vector<char> letters;
        vector<int> poses;
        int len = s.size();
        for (int i = 0; i < len; i++) {
            if (isletter(s[i])) {
                letters.push_back(s[i]);
                poses.push_back(i);
            }
        }
        
        // 冒泡排序
        maopao(letters);
        
        for (int i = 0; i < (int)letters.size(); i++) {
            int pos = poses[i];
            char c = letters[i];
            s[pos] = c;
        }
        cout << s << endl;
    }
}
// 64 位输出请用 printf("%lld")

思路：

1. 用letters和poses保存所有大小写字母与其下标，对letters进行题目规则排序后，再依次插入原字符串，保证非字母字符的位置不变
2. 对letters按规则排序，由于要保证A与a的相对位置不变，因此不能用快速排序，只能用插入排序或冒泡排序
3. 按规则写一个冒泡排序