题解 | #字符串排序# C++代码

题解 | 字符串排序 C++代码

	核心思路： 

字符处理与存储：遍历输入的字符串s，对于每个字符，如果它是字母，则将其转换为小写并存储在node数组a中。同时，记录该字母是否原本是大写，以及它的原始索引（这里的“原始索引”实际上是它在所有字母中的相对位置，而不是在整个字符串中的位置。 换句话说，是剔除掉非字母字符后的字符串中的位置）。 这样做的目的是为了在后续步骤中能够根据字母的实际内容（忽略大小写）进行排序，同时保留足够的信息以恢复原始的大小写状态。
排序：通过一个简单的冒泡排序算法对数组a进行排序。首先按字母的小写形式排序，如果两个字母相同，则按它们在输入字符串中的顺序（即原始索引）排序。
输出：再次遍历原始字符串s。对于每个字符，如果它是字母，则从a数组中按顺序取出一个字母（因为非字母字符的位置不会改变，a又有序），并根据该字母原本是否是大写将其转换回相应的大小写形式后输出。 如果字符不是字母，则直接输出该字符。
#include <bits/stdc++.h>
using namespace std;

struct node {
    char letter;
    bool big;
    int originalIndex; // 用于记录原始索引，以保持大小写字母的输入顺序
};

int main() {
    string s;
    getline(cin, s);
    node a[1005]; // 存储字母
    int cnt = 0;

    // 遍历字符串，处理每个字符
    for (int i = 0; i < s.length(); i++) {
        if (isalpha(s[i])) { // 如果是字母
            a[cnt].letter = tolower(s[i]); // 统一转为小写存储
            a[cnt].big = isupper(s[i]); // 标记是否原本是大写
            a[cnt].originalIndex = cnt; // 记录原始索引
            cnt++;
        }
    }

    // 排序，首先按字母排序，字母相同则按原始索引排序
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < cnt - i - 1; j++) {
            if (a[j].letter > a[j + 1].letter || 
               (a[j].letter == a[j + 1].letter && a[j].originalIndex > a[j + 1].originalIndex)) {
                swap(a[j], a[j + 1]);
            }
        }
    }

    int letterIndex = 0; // 用于跟踪字母数组的当前索引
    // 遍历原始字符串，按规则构造输出字符串
    for (int i = 0; i < s.length(); i++) {
        if (isalpha(s[i])) { // 如果当前字符是字母
            // 检查原本是否是大写，如果是，转换回大写
            cout << (char)(a[letterIndex].big ? toupper(a[letterIndex].letter) : a[letterIndex].letter);
            letterIndex++;
        } else { // 如果不是字母，直接输出
            cout << (char)s[i];
        }
    }

    return 0;
}

作者：khan01
链接：https://www.nowcoder.com/discuss/608773240340623360?sourceSSR=users
来源：牛客网