字符串排序问题

 

题目描述：编写一个程序，将输入字符串中的字符按如下规则排序。

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

如，输入：Type 输出：epTy

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

如，输入：BabA 输出：aABb

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

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

---

输入：A Famous Saying: Much Ado About Nothing(2012/8)     输出：A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

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

int main(){
    int len,count=0;
    string line;
    while(cin >> line){  //输入字符中可能空格，考虑多个输入
    len = line.size();
    
    for(int i = 0; i<len; i++){  //确定字符串中字符个数
        if((line[i]>='a'&&line[i]<='z')||(line[i]>='A'&&line[i]<='Z')){
            count++;
        }
    }
    string str(count,'0'); //初始化字储对象
    int k=0;
    for(int i = 0; i<len; i++){ //将提取出来的字母复制到存储对象中
        if((line[i]>='a'&&line[i]<='z')||(line[i]>='A'&&line[i]<='Z')){
            str[k]=line[i];
            k++;
        }
    }
        
    k=0;
    string temp(count,'0'); //初始化排序存储数组
    for(int i = 0; i<26; i++){  //对提取的字母进行排序，按照与首字母的差值逐个提取顺序位置上的字母进行比较
       for(int j = 0; j<count; j++){
           if(str[j]-'a'==i||str[j]-'A'==i){
                 temp[k] = str[j];
                 k++;
           }
        }
     }
    k=0;
    for(int i=0;i<len;++i){ //将排序后的字母重写到提取位置
        if((line[i]>='a'&&line[i]<='z')||(line[i]>='A'&&line[i]<='Z')){
            line[i]=temp[k];
            k++;
        }
    }
    cout << line;
  }
    cout << endl;
    return 0;
}

这道编程题的难点在于不区分大小写进行排序，此处以遍历字符与首字符的差值进行挑选，用“||”运算屏蔽大小写对于排序的影响，这样的排序方法也有缺陷，那就是每一轮都需要遍历所有字符，一共需要遍历26轮，算法的时间复杂度比较高。编译和调试结果：