题解 | #字符串排序#

获取字符串后，将英文字母提取到vector中，然后进行排序，排序使用的是归并排序（忽略大小写），然后将字符串输出，非字母位置输出原字符。

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

void sort_l(vector<char> & letters, int start, int end);
void merage(vector<char> & letters, int start, int end);

int main() {
    string s;
    getline(cin, s);
    vector<char> letters;
    for (char letter : s) {
        if (isalpha(letter)) {
            letters.push_back(letter);
        }
    }
    sort_l(letters, 0, letters.size() - 1);
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (isalpha(s.at(i))) {
            cout << letters.at(count++);
        } else {
            cout << s.at(i);
        }
    }
    return 0;
}

void sort_l(vector<char> & letters, int start, int end) {
    if (start == end) {
        return;
    }
    sort_l(letters, start, (start + end) / 2);
    sort_l(letters, (start + end) / 2 + 1, end);
    merage(letters, start, end);
}
void merage(vector<char> & letters, int start, int end) {
    vector<char> temp;
    int start1 = start;
    int start2 = (start + end) / 2 + 1;
    int count = 0;
    int start_t;
    while (start1 < (start + end) / 2 + 1 && start2 <= end) {
        if (toupper(letters.at(start1)) <= toupper(letters.at(start2))) {
            temp.push_back(letters.at(start1));
            start1++;
        } else {
            temp.push_back(letters.at(start2));
            start2++;
        }
        count++;
    }
    if (start1 == (start + end) / 2 + 1) {
        start_t = start2;
    } else {
        start_t = start1;
    }
    while (count < end - start + 1) {
        temp.push_back(letters.at(start_t++));
        count++;
    }
    count = 0;
    for (int i = start; i <= end; i++) {
        letters.at(i) = temp.at(count++);
    }
}
// 64 位输出请用 printf("%lld")