题解 | #字符串排序#

字符串排序
算法知识视频讲解
中等 通过率：32.36% 时间限制：1秒 空间限制：32M
知识点
字符串
排序
题目
题解(40)
讨论(513)
排行
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
编写一个程序，将输入字符串中的字符按如下规则排序。

规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。

如，输入： Type 输出： epTy

规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。

如，输入： BabA 输出： aABb

规则 3 ：非英文字母的其它字符保持原来的位置。

如，输入： By?e 输出： Be?y

注意有多组测试数据，即输入有多行，每一行单独处理（换行符隔开的表示不同行）

输入描述：
输入字符串
输出描述：
输出字符串
示例1
输入：
A Famous Saying: Much Ado About Nothing (2012/8).
复制
输出：
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/*
* 字符串排序
* 思路：字母从a~z或A~Z一共26个字母，例如字母'b' - 'a' = 1;因此从0~25依次插入a~z或A~Z;
*      在字符串范围内，当strIn[i]>= 'a' && strIn[i] <= 'z' || strIn[i]>= 'A' && strIn[i] <= 'Z',
       将排序的字符串插入原来的strIn中，且非英文字母不变
* 步骤:
* 第一步：输入字符串strIn
* 第二步： 对a~z或A~Z的字符进行排序，且不区分大小,查找a或A为第一个位置
* 第三步：将非英文字符保持原来位置

*/
string StringSort(string strIn) 
{
    if (strIn.size() == 0) {
        return nullptr;
    }
    int strInLen = strIn.size();
    vector<int> vec;
    // 对a~z或A~Z的字符进行排序，且不区分大小
    for(int i = 0; i < 26; i++) { // a~z或A~Z为26个字符
        for(int j = 0; j < strInLen; j++) { 
            if((strIn[j] - 'a' == i) || (strIn[j] - 'A' == i)) {
                vec.push_back(strIn[j]);
            }
        }
    }

    // 将非英文字符保持原来位置
    for(int i = 0, k = 0; (i < strInLen) && (k < vec.size()); i++) {
        if((strIn[i] >= 'a' && strIn[i] <= 'z') || (strIn[i] >= 'A' && strIn[i] <= 'Z')) {
            strIn[i] = vec[k];
            k++;
        }
    }
    return strIn;
}

int main()
{
    string strIn;
    while (getline(cin, strIn)) {
        cout<<StringSort(strIn)<<endl;
    }
    return 0;
}