字符串排序问题

冷不防 2022-05-16 08:25 329阅读 0赞

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

规则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轮，算法的时间复杂度比较高。编译和调试结果：

![70][]

[70]: /images/20220516/b70ed2d723be490db5c72a81db4b6d9f.png