牛客网4812题：手把手教你实现保留非字母位置的字符串排序

一、问题重述

我们需要实现一个字符串排序函数，要求：

1. 仅对字母字符进行排序（a-z, A-Z）

2. 排序时不区分大小写（即"A"和"a"视为相同）

3. 当同一字母的大小写同时存在时，保持它们在原字符串中的相对顺序

4. 非字母字符（如数字、标点、空格等）保持原位不变

二、算法设计思路

1. 数据收集阶段

首先，我们需要遍历原始字符串，收集所有字母字符及其在字符串中的位置信息。这里使用vector<pair<char, int>>结构存储，其中：

• char保存字母本身

• int保存该字母在原字符串中的索引位置

2. 自定义排序阶段

使用标准库的sort函数配合自定义比较器：

1. 将字母统一转换为小写进行比较

2. 如果小写形式相同，则比较它们在原字符串中的位置，保持输入顺序

3. 字符串重构阶段

再次遍历原始字符串：

• 遇到字母字符时，从已排序的字母列表中按顺序取出字符替换

• 遇到非字母字符时，保持原样不变

三、关键代码解析

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

// 自定义比较函数，用于字母排序
bool compare(const pair<char, int>& a, const pair<char, int>& b) {
    // 转换为小写后比较
    char lowerA = tolower(a.first);
    char lowerB = tolower(b.first);
    if (lowerA != lowerB) {
        return lowerA < lowerB;
    }
    // 相同字母保持输入顺序
    return a.second < b.second;
}

string sortString(string s) {
    vector<pair<char, int>> letters; // 存储字母及其原始位置
    
    // 第一步：收集所有字母并记录位置
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) {
            letters.emplace_back(s[i], i);
        }
    }
    
    // 第二步：对字母进行排序
    sort(letters.begin(), letters.end(), compare);
    
    // 第三步：重构字符串
    int letterIndex = 0;
    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) {
            s[i] = letters[letterIndex].first;
            letterIndex++;
        }
    }
    
    return s;
}

int main() {
    string input;
    getline(cin, input); // 读取整行输入
    
    string result = sortString(input);
    cout << result << endl;
    
    return 0;
}

四、常见错误与调试技巧

1. 忘记处理大小写：确保使用tolower或toupper统一字母形式

2. 顺序保持错误：比较函数中必须包含原始位置比较

3. 边界条件：测试空字符串、全非字母字符串、全大写/全小写字符串等情况

五、扩展思考

可以尝试改进算法：

1. 处理Unicode字符而不仅限于ASCII

2. 添加更多排序规则（如数字的特殊处理）

3. 优化空间复杂度，尝试原地排序

六、总结

通过本文，我们学习了一个实用的字符串处理技巧：如何在保留非字母字符位置的同时，对字母进行不区分大小写的排序。掌握这种分离处理的思想，可以解决许多类似的复杂字符串处理问题。