题解 | #字符串排序#

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

void merge(string& letter, int lo, int mid, int hi){
    string temp = letter;
    auto less = [](char a, char b)-> bool{
        return tolower(a) <= tolower(b);
    };

    int i = lo,j = mid + 1;
    for(int x = lo; x <= hi; x++){
        if(i == mid + 1){
            letter[x] = temp[j++];
        } else if(j == hi + 1){
            letter[x] = temp[i++];
        } else if(less(temp[i], temp[j])){
            letter[x] = temp[i++];
        } else {
            letter[x] = temp[j++];
        }
    }
}

void sort_string(string& letter, int lo, int hi){
    if(lo >= hi) return;
    int mid = (lo + hi) >> 1;
    sort_string(letter, lo, mid);
    sort_string(letter, mid + 1, hi);
    merge(letter, lo, mid, hi);
}

int main() {
    string str;
    while (getline(cin, str)) { // 注意 while 处理多个 case
        string letter;
        for(char c: str){
            if(isalpha(c)){
                letter += c;
            }
        }
        sort_string(letter, 0, letter.size() - 1);
        int i = 0, j = 0;
        string ans;
        while(j < str.size()){
            if(isalpha(str[j]) && i < letter.size()){
                ans += letter[i++];
            } else {
                ans += str[j];
            }
            j++;
        }
        cout << ans;
    }
}
// 64 位输出请用 printf("%lld")


// Bey
// By?e
// Be?y

稳定归并