题解 | #字符串排序# 插入排序

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

int main() {
    std::string str;
    getline(cin, str);
    int len = str.size();
    // 插入排序，稳定排序
    for (int i = 1; i < len; i++) {
        // 未排序区间的第一个元素作为基准元素
        char base = str[i];
        // 如果非英文字母，跳过
        if (!std::isalpha(base)) {
            continue;
        }
        // 已排序区间的右端点
        int j = i - 1;
        // 记录最后一次往前移动j时j的位置
        int lastJ = j + 1;
        // 遍历所有已排序区间
        while (j >= 0) {
            // 跳过不是字母的字符
            if (std::isalpha(str[j])) {
                // 大小写不敏感，统一转换为大写比较，如果比base大，往前挪动到字母字符的位置
                if (std::toupper(str[j]) > std::toupper(base)) {
                    str[lastJ] = str[j];
                    // 记录上一个字母字符的位置
                    lastJ = j;
                }
            }
            j--;
        }
        // 将base赋值到最后一个被挪动的j的位置
        str[lastJ] = base;
    }
    cout << str << endl;
}
// 64 位输出请用 printf("%lld")