首页 > 试题广场 >

字符串排序

[编程题]字符串排序
  • 热度指数：14091 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

编写一个程序，将输入字符串中的字符按如下规则排序(一个测试用例可能包含多组数据，请注意处理)。

规则 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).



输入描述:



输出描述:

示例1

输入

A Famous Saying: Much Ado About Nothing (2012/8).

输出

A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).
算法知识视频讲解
添加回答
C/C++
George____Z头像 George____Z 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(char a,char b) {
    char x,y;
    if(a>='A' && a<='Z') {
        x=a+32;
    } else {
        x=a;
    }
    if(b>='A' && b<='Z') {
        y=b+32;
    } else {
        y=b;
    }
    if(x>=y) {
        return false;
    } else {
        return true;
    }
}

vector<char> v;

int main() {
    char str[1001];
    while(gets(str)) {
        for(int i=0;i<strlen(str);i++) {
            if((str[i]>='A' && str[i]<='Z') || (str[i]>='a' && str[i]<='z')) {
                v.push_back(str[i]);
            }
        }
        stable_sort(v.begin(),v.end(),cmp);
        for(int i=0,j=0;i<strlen(str);i++) {
            if((str[i]>='A' && str[i]<='Z') || (str[i]>='a' && str[i]<='z')) {
                printf("%c",v[j++]);
            } else if(str[i]==' ') {
                printf(" ");
            } else {
                printf("%c",str[i]);
            }
        }
        printf("\n");
        v.clear();
    }
    return 0;
}

发表于 2018-03-13 15:58:29 回复(0)
LuxSun头像 LuxSun 

	import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String str=in.nextLine();
			String[] split = str.split(" ");
			int arrLen=split.length;
			int num[]=new int[arrLen];
			StringBuffer sb=new StringBuffer();
			for (int i = 0; i < arrLen; i++) {
				String ts=split[i];
				num[i]=ts.length();
				sb.append(ts);
			}
			
			
			
//			System.out.println(Arrays.toString(num)+sb);
			
			char temp = '\0';
			int len=sb.length();
			char[] cA = sb.toString().toCharArray();
			StringBuilder trs=new StringBuilder();
			int fuhaoLen=0;
			for (int i = 0; i < len; i++) {
				char c=cA[i];
				if(!(c>='A' && c<='Z' || c>='a' && c<='z')){
					fuhaoLen++;
				}
				else{
					trs.append(c);
				}
			}
			int index[]=new int[fuhaoLen];
			char cArr[]=new char[fuhaoLen];
			for (int i = 0,j=0; i < len; i++) {
				char c=cA[i];
				if(!(c>='A' && c<='Z' || c>='a' && c<='z')){
					index[j]=i;
					cArr[j++]=c;
				}
			}
			
			cA=trs.toString().toCharArray();
			int rsLen=len-fuhaoLen;
			for (int i = rsLen - 1; i > 0; --i)
			{
			    for (int j = 0; j < i; ++j)
			    {
			    	char c1=cA[j];
			    	char c2=cA[j + 1];
			    	if(c1>='A' && c1<='Z'){
			    		c1=(char) ((int)c1+32);
			    	}
			    	if(c2>='A' && c2<='Z'){
			    		c2=(char) ((int)c2+32);
			    	}
			        if (c2 < c1)
			        {
			            temp = cA[j];
			            cA[j] = cA[j + 1];
			            cA[j + 1] = temp;
			        }
			    }
			}
//			System.out.println(Arrays.toString(cA));
			
			StringBuilder rs=new StringBuilder();
			for (int i = 0; i < rsLen; i++) {
				rs.append(cA[i]);
			}
			
			for (int i = 0; i < fuhaoLen; i++) {
				rs.insert(index[i], cArr[i]);
			}
			
//			System.out.println(rs);
			
			String rsStr=rs.toString();
			StringBuilder result=new StringBuilder();
			for (int i = 0; i < arrLen; i++) {
				int tlen=num[i];
				if(i!=arrLen-1){
					result.append(rsStr.substring(0, tlen)+" ");
				}
				else{
					result.append(rsStr.substring(0, tlen));
				}
				rsStr=rsStr.substring(tlen);
			}
			
			System.out.println(result);
		}
	}
}
Ps：主要思路：分解功能，一步一步来：
1、去空格且把每组的len计算出来保存在数组里，后期拼接的时候用到；
2、去除除字母以外的char字符，保留它们的位置和内容到新的数组里，后期拼接的时候用到；
3、利用冒泡排序把char字符进行排序，如果碰到大写情况，+32；
4、把第2步的字符先拼接上，再把第1步的空格给补上。
完毕！
发表于 2016-10-13 13:22:17 回复(0)
C/C++
玉玉玉了头像 玉玉玉了
老规矩自定义sort 
#include <bits/stdc++.h>
using namespace std;
struct ch{
    char a;
    int i;
};
bool cmp(ch a,ch b)
{
    if(a.a==b.a||a.a-'A'+'a'==b.a||b.a-'A'+'a'== a.a )
        return a.i<b.i;
    else if(a.a>='A'&&a.a<='Z'&&b.a>='a'&&b.a<='z')
            return a.a-'A'+'a'<b.a;
    else if(b.a>='A'&&b.a<='Z'&&a.a>='a'&&a.a<='z')
        return a.a<b.a-'A'+'a';
    else
        return a.a<b.a;
        
}
int main()
{
    string str;
    while(getline(cin,str))
    {
        int len=str.length();
        ch c[10000];
        int flag[10000]={0},tmp=0;
        for(int i=0;i<len;++i)
        {
            if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z'))
            {
                c[tmp].a=str[i];
                c[tmp].i=i;
                tmp++;
            }
            else
                flag[i]=1;
        }
        sort(c,c+tmp,cmp);
        for(int i=0,k=0;i<len;++i)
        {
            if(flag[i]==0)
            {
                str[i]=c[k].a;
                ++k;
            }
        }
        cout<<str<<endl;
    }
}


发表于 2021-01-21 11:44:57 回复(0)
哈雷克斯之火葬魔咒头像 哈雷克斯之火葬魔咒 
#include<bits/stdc++.h>
using namespace std;
bool cmp(char a,char b) {
	char c=a,d=b;
	if(c>='a'&&c<='z') {
		c-=32;
	}
	if(d>='a'&&d<='z') {
		d-=32;
	}
	return c<d;
}
int main() {
	string s;
	vector<char> vt;
	while(getline(cin,s)) {
		vt.clear();
		for(int i=0; i<s.length(); i++) {
			if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')) {
				vt.push_back(s[i]);
			}
		}
		stable_sort(vt.begin(),vt.end(),cmp);
		for(int i=0,t=0; i<s.length(); i++) {
			if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')) {
				s[i]=vt[t++];
			}
		}
		cout<<s<<endl;
	}
}

发表于 2020-03-22 15:36:00 回复(0)
C/C++
fxzero头像 fxzero 
#include <stdio.h>
#include <string.h>

void bubblesort(char *p,int n)
{
    char temp,t1,t2;
    for(int i=n-1;i>0;i--)
    {
        
        for(int j=0;j<i;j++)
        {
            t1=((p[j]-'a'>=0)?(p[j]-'a'):(p[j]-'A'));
            t2=((p[j+1]-'a'>=0)?(p[j+1]-'a'):(p[j+1]-'A'));
            if(t1>t2)
            {
                temp=p[j+1];
                p[j+1]=p[j];
                p[j]=temp;
            }
        }
    }
}
int main ()
{
    char s[500];
    while (gets(s))
    {
        char t[500];
        int len=strlen(s),p=0;
        for(int i=0;i<len;i++)
        {
            if((s[i]>='a'&&s[i]<='z') || (s[i]>='A'&&s[i]<='Z'))t[p++]=s[i];
        }
        bubblesort(t,p);
        p=0;
        for(int i=0;i<len;i++)
        {
            if((s[i]>='a'&&s[i]<='z') || (s[i]>='A'&&s[i]<='Z'))printf("%c",t[p++]);
            else printf("%c",s[i]);
        }
        printf("\n");
    }
}

发表于 2020-02-10 18:52:24 回复(0)
C/C++
咖喱的cuy头像 咖喱的cuy

代码丑陋，好在逻辑简单

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

struct node{
    char c;
    int idx;
}words[500]; // 仅存储大小写字母

bool cmp(node a, node b){
    int value_a, value_b;
    if(a.c >= 'a' && a.c <= 'z')
        value_a = a.c - 'a';
    else
        value_a = a.c - 'A';
    if(b.c >= 'a' && b.c <= 'z')
        value_b = b.c - 'a';
    else
        value_b = b.c - 'A';

    if(value_a == value_b)
        return a.idx < b.idx;
    else
        return value_a < value_b;
}

int main(){
    string str;
    while(getline(cin, str)){
        string new_str;
        int len = 0;
        for(int i = 0; i < str.length(); i++){
            if((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')){
                words[len].c = str[i];
                words[len].idx = len;
                len++;
            }
        }
        sort(words, words + len, cmp);
        new_str = "";
        int k = 0;
        for(int i = 0; i < str.length(); i++){
            if((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
                new_str += words[k++].c;
            else
                new_str += str[i];
        }
        cout << new_str << endl;
    }
    return 0;
}
发表于 2019-03-15 20:46:42 回复(0)
C/C++
areyoukidding7头像 areyoukidding7 
//通过从A~Z遍历原字符串，来构造ans字符串

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

int main(){
    string str,ans;//str为输入字符串,ans为输出字符串
    int i,j,t,len,loc;
    char cap_letter,low_letter;
    while(getline(cin,str)){
        ans=str;//ans=str，完成所有非英文字母的赋值(非英文字母字符保持原位置)
        len=str.size();
        loc=0;//定位ans字符串修改的位置
        for(cap_letter='A',low_letter='a';cap_letter<='Z';++cap_letter,++low_letter){//A~Z依次扫描
            for(i=0;i<len;++i){
                if(str[i]==cap_letter||str[i]==low_letter){//原字符串是当前扫描的字母
                    while(!(ans[loc]>='A'&&ans[loc]<='Z')&&!(ans[loc]>='a'&&ans[loc]<='z')){++loc;}
                    //ans[loc]不是字母则后移一位，直到ans[loc]为字母
                    ans[loc]=str[i];//用此次扫描到的字母替换ans[loc]
                    ++loc;//后移一位
                }
            }
        }
        cout<<ans<<endl;
    }
    
    return 0;
}

发表于 2019-02-24 22:51:28 回复(0)
Dan_tj头像 Dan_tj 



	#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>





	using namespace std;





	bool cmp(char a, char b)
{
 if(a>='A'&&a<='Z')
 {
  a = a-'A'+'a';
 }
 if(b>='A'&&b<='Z')
 {
  b = b-'A'+'a';
 }
 return a<b;
}





	bool isalpha(char c)
{
 return ((c>='a'&&c<='z')||(c>='A'&&c<='Z'));
}





	int main()
{
 string input,alpha,res,other;
 vector<int> pos;
 while(cin>>input)
 {
  
  res.clear();
  pos.clear();
  alpha.clear();
  other.clear();
  for(int i=0;i<input.size();i++)
  {
   if(isalpha(input[i]))
   {
    alpha.push_back(input[i]);
   }
   else
   {
    pos.push_back(i);
    other.push_back(input[i]);
   }
  }
  stable_sort(alpha.begin(),alpha.end(),cmp);
  int pos_count=0,other_count=0,alpha_count=0;
  for(int i=0;i<input.size();i++)
  {
   if(pos_count<pos.size()&&i==pos[pos_count])
   {
    res.push_back(other[other_count++]);
    pos_count++;
   }
   else
   {
    res.push_back(alpha[alpha_count++]);
   }
  }
  cout<<res<<endl;
 }
}
全用stl就成了
首先自定义一个比较函数，因为大小写不区分，所以如果是大写字母就转化成小写再比较
其次sort是不稳定排序，可能aA排序之后变成Aa，所以用stable_sort
然后记录一下非字母的位置，按位置输出就行了
boom，自己什么都没写就写完了
发表于 2018-06-12 21:30:42 回复(0)
Java
WongLong头像 WongLong
插入排序

发表于 2018-01-19 19:16:04 回复(0)
263保洁小妹头像 263保洁小妹
不知道用例的字符串有多长，一开始设的200溢出了，第二次改成1000通过了
我是把字符串里的字母全都复制到另一个字符串里，然后对另一个只含字母字符串进行排序。输出时对原字符串逐个字符输出，若该字符不是字母则直接输出，若是字母则从另一个字符串里面拿一个字符输出，这样就可以了 
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 1000
using namespace std;

int IsLetter(char c)
{
    if('a'<=c&&c<='z') return 1;//小写字母返回1
    else if('A'<=c&&c<='Z') return 2;//大写字母返回2
    else return 0;//不是字母返回0
}

bool cmp(char a, char b)
{
    if(IsLetter(a)==2) a=a-'A'+'a';
    if(IsLetter(b)==2) b=b-'A'+'a';
    return a<b;
}

int main()
{
    char letter[N];
    char str[N];
    int len1;
    int pos;
    while(gets(str))
    {
        len1=0;
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
            if(IsLetter(str[i])!=0) letter[len1++]=str[i];
        }
        stable_sort(letter, letter+len1, cmp);
        pos=0;
        for(int i=0; i<len; i++)
        {
            if(IsLetter(str[i])==0) printf("%c", str[i]);
            else printf("%c", letter[pos++]);
        }
        printf("\n");
    }
    return 0;
}

发表于 2018-02-22 16:25:16 回复(6)
cancer大魔王头像 cancer大魔王

应该是比较简单易懂的喽~ 看懂了给个赞 哈哈哈

每个字符设置一个字符位ch，和一个标志位flag
初始化result的时候，如果不是字母，则填充字符位，并且flag=1
如果是字母，则不填充字符位(留到后面排序后填充)，并且flag=0

排序的时候2个for，分别遵循题目的要求：
外部for实现字母顺序排序 内部for实现输入顺序排序
在向result插入字符的时候，要看当前位的flag是否为0 如果不为0，就向后移动索引
直到为0才开始插入（这样就跳过了初始化的时候填充的特殊符号）。

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

class Node{
public:
    char ch;
    int flag;   
};

int main(){

    vector<Node> result(1024);
    string str;
    while(cin>>str){

        int len=str.length();
        for(int i=0;i<len;i++)
        {
            if((str[i]>='a' && str[i]<='z') ||(str[i]>='A' && str[i]<='Z'))
            {
                result[i].flag=0;
            }else
            {
                result[i].flag=1;
                result[i].ch=str[i];
            }
        }

        int index=0;
        //外部for实现字母顺序排序 内部for实现输入顺序排序
        for(int i='A';i<='Z';i++)
        {
            for(int j=0;j<len;j++)
            {
                if(str[j]==i || str[j]==i+32)
                {
                    //如果不是字母，则它的ch位已经被填充，索引向后移动即可
                    while(result[index].flag==1)
                        index++;

                    result[index].ch=str[j];
                    result[index].flag=1;
                }
            }
        }

        for(int i=0;i<len;i++)
            cout<<result[i].ch;
        cout<<endl;
    }

    //system("pause");

    return 0;
}
发表于 2017-08-29 10:34:34 回复(5)
Steven.wu头像 Steven.wu 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String s = input.nextLine();
            String r = sort(s);
            System.out.println(r);
        }
    }

    public static String sort(String s) {
        if (s.length() <= 0) {
            return null;
        }
        char[] c = s.toCharArray();
        StringBuffer sb = new StringBuffer();
        // 对字母进行排序的思想是：将每一字符与'a'-'z'或'A'-'Z'做比较，并添加到字符缓冲中，经过此步骤完成了
        // 不同字母按递增顺序排序，同一字母（不区分大小写）按原来顺序排列。
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < c.length; j++) {
                if (c[j] == 'a' + i || c[j] == 'A' + i) {
                    sb.append(c[j]);
                }
            }
        }
        StringBuffer res = new StringBuffer();
        int flag = 0;
        for (int i = 0; i < c.length; i++) {
            if (isChar(c[i])) {
                res.append(sb.charAt(flag));
                flag++;
            } else {
                res.append(c[i]);
            }
        }
        return res.toString();
    }

    // 判断某一字符是否为字母
    public static boolean isChar(char c) {
        if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
            return true;
        } else {
            return false;
        }
    }
}

发表于 2017-11-29 08:55:58 回复(0)
Pigeon_头像 Pigeon_ 
/*设置两个动态数组replaceIndex和allLetters。replaceIndex记录需要修改的索引，
即字符是英文字母的索引；allLetters按照题目的排序要求放置字母，采取方法是：
从a-z的循环顺序扫描句子，再以输入顺序取字母对比，相同(忽略大小写)就
放入allLetters。最后，按allLetters顺序将字母放入需要修改的索引。*/
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            char[] line = scanner.nextLine().toCharArray();
            List<Integer> replaceIndex = new ArrayList<>();
            List<Character> allLetters = new ArrayList<>();
            for (int i = 0; i < line.length; i++)
                if (Character.isLetter(line[i]))
                    replaceIndex.add(i);
            for (int i = 0; i < 26; i++) {
                char pattern = (char) ('a' + i);
                for (int j = 0; j < line.length; j++) {
                    if (Character.isLetter(line[j]) && Character.toLowerCase(line[j]) == pattern)
                        allLetters.add(line[j]);
                }
            }
            for (int i = 0; i < replaceIndex.size(); i++) {
                int index = replaceIndex.get(i);
                line[index] = allLetters.get(i);
            }
            for (char c : line)
                System.out.print(c);
            System.out.println();
        }
        scanner.close();
    }
}

编辑于 2018-02-14 14:25:37 回复(1)
C++
牛客67820661号头像 牛客67820661号
#include<iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
typedef struct{
    char a;
    char b;
}str;
bool cmp(str x,str y)
{
    if(x.a<y.a)
    return true;
    return false;
}
int main()
{
    string s1;
    while(getline(cin,s1))
    { 
        str A[s1.size()];
        char s2[s1.size()];int k=0;
        for(int i=0;i<s1.size();i++)
        {
            if((s1[i]>='a'&&s1[i]<='z')||(s1[i]>='A'&&s1[i]<='Z'))
            {
                s2[k++]=s1[i];
            }
        }
        for(int i=0;i<k;i++)
        {
            if(s2[i]>='A'&&s2[i]<='Z')
            {
                    A[i].a=char(int(s2[i])+32);
                    A[i].b=s2[i];
            }
            else
            {
                A[i].a=s2[i];
                A[i].b=s2[i];
            }
        }
        stable_sort(A,A+k,cmp);
        for(int i=0,j=0;i<s1.size();i++)
        {
            if((s1[i]>='a'&&s1[i]<='z')||(s1[i]>='A'&&s1[i]<='Z'))
            {
                s1[i]=A[j].b;j++;
            }
        }
        for(int i=0;i<s1.size();i++)
        cout<<s1[i];
        cout<<endl;
    }
    return 0;
}
发表于 2023-03-14 19:51:11 回复(0)
C++
Forgery头像 Forgery 
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
using namespace  std;
map<char,int> Priority;
bool isC(char c){
    if(c>='a'&&c<='z') return true;
    else if(c>='A'&&c<='Z') return true;
    else return false;
}
void initMap(){
    for(char c='a';c<='z';c++){
        Priority.insert({c,c-'a'});
    }
    for(char c='A';c<='Z';c++){
        Priority.insert({c,c-'A'});
    }
}
bool compare(char a,char b){
    return Priority[a]<Priority[b];
}
vector<pair<int,char>> charMap;
int main(){
    initMap();
    string str;
    string tmp;
    char c;
    while(getline(cin,str)){
        charMap.erase(charMap.begin(),charMap.end());
        for (int i = 0; i < str.size(); i++) {
            if (!isC(str[i])) {
                pair<int, char> p = {i, str[i]};
                charMap.push_back(p);
            }
        }
        vector<pair<int, char>>::iterator it;
        if(!charMap.empty())
        for (it = --charMap.end();; it--) {
            str.erase(it->first, 1);
            if (it == charMap.begin()) break;
        }
        stable_sort(str.begin(), str.end(), compare);
        for (it = charMap.begin(); it != charMap.end(); it++) {
            int idx = it->first;
            char c = it->second;
            string::iterator index = str.begin();
            index = index + idx;
            str.insert(index, c);
        }
        printf("%s\n", str.c_str());
        str="";

}}

编辑于 2024-03-24 17:25:33 回复(0)
调皮的磨洋工匠人在查重头像 调皮的磨洋工匠人在查重 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool cmp(int a, int b) {
    int aa, bb;
    if (a - 'a' >= 0) aa = a - 'a';
    else aa = a - 'A';
    if (b - 'a' >= 0) bb = b - 'a';
    else bb = b - 'A';
    return aa < bb;
}

int main() {
    string a;
    while (getline(cin, a)) { // 注意 while 处理多个 case
        vector<char> s;
        for (int i = 0; i < a.size(); i++) {
            if (isalpha(a[i])) {
                s.push_back(a[i]);
            }
        }
        int n = s.size();
        stable_sort(s.begin(), s.end(), cmp);
        for (int i = a.size() - 1; i >= 0; i--) {
            if (isalpha(a[i])) {
                a[i] = s.back();
                s.pop_back();
            }
        }
        cout << a << endl;
    }
}
// 64 位输出请用 printf("%lld")

编辑于 2024-03-19 16:22:41 回复(0)
牛客729154675号头像 牛客729154675号
我懵了，他是靠什么来区分一个测试用例中的不同数据的？不是换行符那是什么？凭什么测试用例里的第一行为一个数据，后三行为一个数据？
编辑于 2024-03-06 16:27:25 回复(0)
C++
无问西东gmy头像 无问西东gmy 
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {       //字符结点
    char data;      //字符内容（数据）
    int position;   //字符（在原字符串中的）下标（位置）
    Node(char d, int p): data(d), position(p) {}
    bool operator<(const Node& n) {     //重载小于号，用于sort函数
        return tolower(data) < tolower(n.data) ||
               (tolower(data) == tolower(n.data) && position < n.position);
    }
};

inline bool isLetter(char ch) {     //判断字符是否为英文字母
    return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z');
}

int main() {
    string str;
    while (getline(cin, str)) {
        vector<Node>letters;    //英文字母
        vector<Node>other;      //非英文字母的其它字符
        for (int i = 0; i < str.size(); i++) {
            if (isLetter(str[i])) {
                letters.emplace_back(str[i], i);
            } else {
                other.emplace_back(str[i], i);
            }
        }
        sort(letters.begin(), letters.end());
        str = "";
        for (const auto& e : letters) {
            str += e.data;
        }
        for (const auto& e : other) {
            str.insert(str.begin() + e.position, e.data);
        }
        cout << str << endl;
    }
    return 0;
}

编辑于 2024-03-01 09:23:00 回复(0)
甜美的傻狍子在迎接offer头像 甜美的傻狍子在迎接offer
思路就是插入排序的翻版，不过之前都是 a[j] 与 a[j - 1] 比较，现在是与 a[k] 比较，k为j之前的元素中的英文字母 

#include <bits/stdc++.h>
using namespace std;

#define EN_LETTER(c) ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
#define INDEX(ch) (ch >= 'a'? ch - 'a' : ch - 'A')

bool Less(char c1, char c2) {
	int index1 = INDEX(c1);
	int index2 = INDEX(c2);
	
	if (index1 == index2)
		return false;	// 相同字母那就不换了
	else
		return index1 < index2;
}

void swap(string& s, int j, int k) {
	char tmp = s[j];
	s[j] = s[k];
	s[k] = tmp;
}

void InsertSort(string& s) {
	for (int i = 1; i < s.length(); i++) {
		char c = s[i];
		// 非英文字母 无需移动
		if (!EN_LETTER(c)) continue;
		
		for (int j = i; j >= 1; ) {
			int k = j - 1;
			while (k > 0 && !EN_LETTER(s[k])) {
				k--;
			} 
			if (k < 0) break;
			if (Less(s[j], s[k])) {
				swap(s, j, k);
			}
			j = k;
		}
	}
}

int main() {
	// freopen("D:\\DeskTop\\in.txt", "r", stdin);
	
	string s;
	while (getline(cin, s) && s.length() != 0) {
		InsertSort(s);
		cout << s << endl;
	}
}


发表于 2023-05-04 10:25:28 回复(0)
C++
如似三冬头像 如似三冬 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
    string str;
    while (getline(cin, str)) { // 注意 while 处理多个 case
        string _str;
        for (char c : str)
        {
            if (isalpha(c))
                _str.push_back(c);
        }
        int n = _str.size();
        vector<int> idxs(n);
        for (int i = 0; i < n; ++i)
            idxs[i] = i;
        sort(idxs.begin(), idxs.end(), [&](const int& i, const int& j) {
            char a = _str[i], b = _str[j];
            if (isupper(a))
                a += 32;
            if (isupper(b))
                b += 32;
            if (a == b)
                return i < j;
            return a < b;
            });

        int i = 0;
        for (char c : str)
        {
            if (isalpha(c))
                cout << _str[idxs[i++]];
            else
                cout << c;
        }
        cout << endl;
    }
    return 0;
}

发表于 2023-03-21 22:52:02 回复(0)
提交观点

问题信息

字符串 排序
难度：
104条回答 25376浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号