首页 > 试题广场 >

字符串排序

[编程题]字符串排序

热度指数：308138 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的由可见字符和空格组成的字符串，按照下方的规则进行排序：
$\hspace{23pt}\bullet\,$ 按照字母表中的顺序排序（不区分大小写）；
$\hspace{23pt}\bullet\,$ 同一字母的大小写同时存在时，按照输入顺序排列；
$\hspace{23pt}\bullet\,$ 非字母字符保持原来的位置不参与排序；
$\hspace{15pt}$ 直接输出排序后的字符串。

$\hspace{15pt}$ 字符串由 ASCII 码在 $32$ 到 $126$ 范围内的字符组成。您可以参阅下表获得其详细信息。

../图片/可见字符集Ascii.png

输入描述:

在一行上输入一个长度为  ，由上表中的字符组成的字符串  。

输出描述:

输出一个字符串，代表按照规则排序后的字符串。

示例1

输入

BabA

输出

aABb

示例2

输入

Hello NowCoder!

输出

CdeeH llNooorw!

算法知识视频讲解

霄霄霄总止痛酊

屎山

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max_size 1000
#define caps 0
#define low 1
#define sbl 2

int16_t flow_judge(char c)
{
    if (c >= 'A' && c <= 'Z') return caps;
    else if (c >= 'a' && c <= 'z') return low;
    else return sbl;
}

int main() 
{
    char *deque = (char*)malloc((max_size + 1) * sizeof(char));
    int16_t reard = 0,frontd = 0;

    char *stack = (char*)malloc(max_size * sizeof(char));
    int16_t top = 0;

    char *symbol = (char*)malloc((max_size + 1) * sizeof(char));
    int16_t *symboli = (int16_t*)malloc((max_size + 1) * sizeof(int16_t));
    int16_t rears = 0,fronts = 0;

    char max_ele,min_ele,top_ele,c;
    int16_t flow = 0,index = 0;
    scanf("%c",&c);
    while(c >= ' ' && c <= '~')
    {
        if((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))break;
        else
        {
            printf("%c",c);
            scanf("%c",&c);
        }
    }
    if (c >= 'A' && c <= 'Z') 
    {
        max_ele = c;
        min_ele = c;
    }
    else 
    {
        max_ele = c - ' ';
        min_ele = c - ' ';
    }
    deque[reard++] = c;

    scanf("%c",&c);
    flow = flow_judge(c);

    while (c != '\n') 
    {
        if (flow == sbl) {
            symbol[rears] = c;
            symboli[rears++] = ((reard - frontd + (max_size + 1)) % (max_size + 1)) + top + rears;
        }
        else if ( (flow == caps && c <= min_ele) || (flow == low && (c - ' ') <= min_ele) ) {
            if( (flow == caps && c == min_ele) || (flow == low && (c - ' ') == min_ele) ) {
                int16_t x = frontd;
                frontd = (frontd - 1 + (max_size + 1)) % (max_size + 1);
                deque[frontd] = c;
                while ( (flow_judge(deque[x]) == caps && deque[x] == min_ele) || (flow_judge(deque[x]) == low && (deque[x] - ' ') == min_ele) ) {
                    char tmp3 = deque[x];
                    int16_t y = (x - 1 + (max_size + 1)) % (max_size + 1);
                    deque[x] = deque[y];
                    deque[y] = tmp3;
                    x = (x + 1) % (max_size + 1);
                }
            } 
            else {
                frontd = (frontd - 1 + (max_size + 1)) % (max_size + 1);
                deque[frontd] = c;
                if(flow == caps)min_ele = c;
                else min_ele = c - ' ';
            }
        }
        else {
            while ((flow == caps && c < max_ele) || (flow == low && (c - ' ') < max_ele)) {
                reard = (reard - 1 + (max_size + 1)) % (max_size + 1);
                stack[top++] = deque[reard];
                top_ele = flow_judge(stack[top-1]) == caps ? stack[top-1] : stack[top-1] - ' ';
                int16_t tmp2 = (reard - 1 + (max_size + 1)) % (max_size + 1); 
                max_ele = flow_judge(deque[tmp2]) == caps ? deque[tmp2] : deque[tmp2] - ' ';
            }
            if (top != 0) {
                while ((flow == caps && c >= top_ele) || (flow == low && (c - ' ') >= top_ele)) {
                    deque[reard] = stack[--top];
                    reard = (reard + 1) % (max_size + 1);
                    if (top == 0) {
                        top_ele = 0;
                        break;
                    }
                    top_ele = flow_judge(stack[top-1]) == caps ? stack[top-1] : stack[top-1] - ' ';
                }
            }
            if(flow == caps) max_ele = c;
            else max_ele = c - ' ';
            deque[reard] = c;
            reard = (reard + 1) % (max_size + 1);
        }
        scanf("%c",&c);
        flow = flow_judge(c);
    }

    int sum = ((reard - frontd + (max_size + 1)) % (max_size + 1)) + top + rears;
    while( ((reard - frontd + (max_size + 1)) % (max_size + 1)) > 0 ) {
        if( (sum - (((reard - frontd + (max_size + 1)) % (max_size + 1)) + top + rears - fronts) == symboli[fronts]) && (rears - fronts > 0)) {
            printf("%c",symbol[fronts++]);
        } else {
            printf("%c",deque[frontd]);
            frontd = (frontd + 1) % (max_size + 1);
        }
    }
    free(deque);

    while (top > 0) {
        if((sum - (top + rears - fronts) == symboli[fronts]) && (rears - fronts > 0)) {
            printf("%c",symbol[fronts++]);
        } else {
            printf("%c",stack[--top]);
        }
    }
    free(stack);

    while(rears - fronts > 0) {
        printf("%c",symbol[fronts++]);
    }
    free(symbol);
    free(symboli);

    return 0;
}

发表于 2025-11-14 04:58:57 回复(0)

牛客163202627号

#include<stdio.h>

#include<string.h>

int main()

{

char a[1001],b[1000],e;

int i,j,l=0,k=0;

fgets(a, sizeof(a), stdin);

for (i = 0; i < 26; i++)

{

for (j = 0; j < strlen(a); j++)

{

if (a[j] == 'A' + i || a[j] == 'a' + i)

{

b[l] = a[j];

l++;

}

for (i = 0,j = 0; i < strlen(a); i++)

{

if (a[i] < 'A' || (a[i] > 'Z' && a[i] < 'a') || a[i]>'z')

printf("%c", a[i]);

else

{

printf("%c", b[j]);

j++;

}

发表于 2025-07-11 14:13:30 回复(0)

牛客975604703号

#include <stdio.h>

#include <ctype.h>

#include <string.h>

void sort_string(char* str, size_t len) {

char letters[1000]; // 存储所有字母字符

int positions[1000]; // 存储所有字母字符的原始位置

int letter_count = 0;

// 步骤1: 提取字母字符及其原始位置

for (int i = 0; i < len; i++) {

if (isalpha(str[i])) {

letters[letter_count] = str[i];

positions[letter_count] = i;

letter_count++;

}

// 步骤2: 冒泡排序（不区分大小写，稳定排序）

for (int i = 0; i < letter_count - 1; i++) {

for (int j = 0; j < letter_count - i - 1; j++) {

// 比较相邻字符的小写形式

char a = tolower(letters[j]);

char b = tolower(letters[j + 1]);

if (a > b || (a == b && positions[j] > positions[j + 1])) {

// 交换字符

char temp_char = letters[j];

letters[j] = letters[j + 1];

letters[j + 1] = temp_char;

}

// 步骤3: 将排序后的字符按原始位置放回

for (int i = 0; i < letter_count; i++) {

str[positions[i]] = letters[i];

}

int main() {

char str[1000] = {0};

scanf("%[^\n]",str);

size_t len = strlen(str);

sort_string(str, len);

printf("%s\n", str);

return 0;

}

发表于 2025-02-28 21:08:17 回复(0)

牛客653305411号

#include <stdio.h>
#include <string.h>

int main() {
    char str[1000];
    gets(str);

    int length = strlen(str);
    char temp[length];
    /* 1、先将所有的字母a-z, A-Z排序*/
    int k = 0;
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < length; j++) {
            if ( str[j] == ('a' + i) || str[j] == ('A' + i)) {
                temp[k++] = str[j]; // 排好序的字符串就存放在temp中
            }
        }
    }

    /* 2、将temp按照顺序写回到str中，遇到非字母就跳过 */
    k = 0;
    for (int i = 0; i < length; i++) {
        if (((str[i] >= 'a') && (str[i] <= 'z')) || ((str[i] >= 'A') &&
                (str[i] <= 'Z'))) {
            str[i] = temp[k++];
        }
    }

    printf("%s", str);

    return 0;
}

发表于 2024-09-09 23:12:03 回复(0)

守定

#include <stdio.h>
#include <string.h>
int main() {
    char arr[1001];
    char ch[1001];
    int n=0;
    gets(arr);
    int len=strlen(arr);
    for (int i=0;i<=len-1;i++){
        for(int j=0;j<=len-1;j++){
            if(arr[j]-'a'==i || arr[j]-'A'==i){
                ch[n]=arr[j];
                
                n++;
            }
        }
    }
    n=0;
    for(int i=0;i<=len-1;i++){
        if((arr[i]>='a'&&arr[i]<='z') || (arr[i]>='A'&&arr[i]<='Z')){
            arr[i]=ch[n];
            n++;
            printf("%c",arr[i]);

        }
        else {
        printf("%c",arr[i]);
        }
    }
    return 0;
}

发表于 2024-09-01 23:28:57 回复(0)

牛客407997512号

#include <stdio.h>
#include <string.h>

int letter(char x) {
    if (x >= 'a' && x <= 'z') {
        x = x - ('a' - 'A');
        return x;
    } else if (x >= 'A' && x <= 'Z') return x;
    else return -1;
}
int main() {
    char s[1005];
    int pos[1005];
    gets(s);
    int a, b;
    char temp;
    int x;
    for (int i = 0; i < strlen(s); i++) {
        pos[i] = i;
    }
    for (int i = 0; i < strlen(s) - 1; i++) {
        for (int j = i + 1; j < strlen(s); j++) {
            a = letter(s[i]);
            b = letter(s[j]);
            if (a != -1 && b != -1) {
                if (a > b) {
                    temp = s[i] ;
                    s[i] = s[j];
                    s[j] = temp;
                    x = pos[i];
                    pos[i] = pos[j];
                    pos[j] = x;
                } else if (a == b) {
                    if (pos[i] > pos[j]) {
                        temp = s[i] ;
                        s[i] = s[j];
                        s[j] = temp;
                        x = pos[i];
                        pos[i] = pos[j];
                        pos[j] = x;
                    }
                }
            }
        }
    }
    printf("%s", s);
}

发表于 2024-05-15 15:07:41 回复(0)

牛客70985078号

看到某个写法受到启发写了个简洁的，思路就是按照a到z的顺序输出，在输出到符号的位置输出符号。实际输出与预期输出是一样的可为什么过不了呢？

#include <stdio.h>
#include <string.h>
int main() {
    char str[1001] = { 0 }; int output = 0; /*output表示已经输出的字符数量*/
    gets(str);
    int len = strlen(str);
    for (int i = 0; i < 26; i++)
    {
        char word = 'A' + i;
        for (int j = 0; j < len; j++)
        {
            if (str[output]<'A' || str[output]>'z' || (str[output]>'Z'&&str[output] < 'a')) /*即为非字母*/
            {
                printf("%c",str[output]);
                output++;
            }
            if (str[j] == word || str[j] == word + 32)
            {
                printf("%c", str[j]);
                output++;
            }
        }
    }
    return 0;
}

编辑于 2024-03-24 18:05:49 回复(0)

不自量力c

#include <stdio.h>
#include <string.h>

int main() {
    char str[1000];
    int str_count[1000];
    memset(str_count,0,sizeof(str_count));
    scanf("%[^\n]\n",str);
    char *x,*y=str;
    for(char i='A';i<='Z';i++)
    {
        for(int j=0;j<strlen(str);j++)
        {
            if(str_count[j])
            continue;
            else if(str[j]>='a'&&str[j]<='z')
            {
                if(str[j]=i-'A'+'a')
                {
                    printf("%c",str[j]);
                    str_count[j]++;
                }
            }
            else if(str[j]>='A'&&str[j]<='Z')
            {
                if(str[j]=i)
                {
                    printf("%c",str[j]);
                    str_count[j]++;
                }
            }
            else {
                printf("%c",str[j]);
                str_count[j]++;
            }
        };
    }
    
    return 0;
}

为什么会这样啊？？？？

编辑于 2024-02-25 19:08:36 回复(1)

牛客760397612号

#include <stdio.h>
int main(void)
{
char str[100], stand[100] ;
while(scanf("%s", str)==1){
int a, b,c=strlen(str),k=0;
for (b = 'A'; b <= 'Z'; b++)
{
for (a = 0; a < c; a++)
{

if (str[a] == b || str[a] - 32 == b)
{
stand[k] = str[a];
k++;
}
}
}

k = 0;
for (a = 0; a < c; a++)
{
if (str[a] >= 'A' && str[a] <= 'Z' || str[a] >= 'a' && str[a] <= 'z')
printf("%c", stand[k++]);
else printf("%c", str[a]);
}
printf("\n");
}
return 0;
}

发表于 2024-01-28 23:03:50 回复(0)

牛客356249919号

//思路：读取字符串中的所有字母，由于字母不分大小写，所以只要遇到字母，就加到alp字符组中
//输出时遍历str，遇到字母就输出alp中的字符，遇到非字母则输出str中的内容

#include <stdio.h>
#include <string.h>

int main(){
    char str[1001] = {'\0'},alp[1001] = {'\0'};
    int n = 0;
    gets(str);
    for(int i = 0 ; i < 26 ; i++ ){ //从'a'/'A'开始遍历
        for(int j = 0 ; j < strlen(str) ; j++){
            if(str[j] - 'a' == i || str[j] - 'A' == i ) //例如：str[j]中遇到b/B，则会把str[j]放在alp[n]中，然后n++
                alp[n++] = str[j];
        }
    }
    //printf("%s\n",alp);   //输出alp中的所有字母
    n = 0;
    for(int i = 0 ; i < strlen(str) ; i++ ){
        if( (str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z') ){
            printf("%c",alp[n++]);
        }
        else
            printf("%c",str[i]);
    }
    return 0;
}

编辑于 2023-12-23 19:43:34 回复(0)

牛客770548236号

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
struct word
{
    char c;
    int index;//输入序号
};


int compare(const void *a, const void *b) 
{
    struct word *wordA = (struct word *)a;
    struct word *wordB = (struct word *)b;
    
    //比较字母大小，不考虑大小写，全部按照大写字母比较
    int diff = toupper(wordA->c) - toupper(wordB->c);
    if (diff != 0) 
    {
        return diff;
    }
    
    //如果字母相同，比较输入序号
    return wordA->index - wordB->index;
}

void sort(char str[],int len)
{
    struct word arr[1000]={0};//结构体数组，存放字母和输入序号
    int i=0;
    int j=0;
    for(i=0;i<len;i++) 
    {
        if(isalpha(str[i]))//是字母就存到排序数组中
        {
            arr[j].c = str[i];
            arr[j].index =i;
            j++;
        }
    }

    //compaer(arr,j);//排序
    qsort(arr, j, sizeof(struct word), compare);//使用qsort函数

    for(i =0,j=0;i<len;i++)//排序后替换到原来的数组中
    {
        if(isalpha(str[i]))
        {
            str[i]=arr[j].c;
            j++;
        }
    }
}

int main() 
{
    //输入
    char str[1001]={0};
    fgets(str,sizeof(str),stdin);
    int len= strlen(str)-1;
    //排序
    sort(str,len);
    //输出
    printf("%s",str);
    return 0;
}
//a-z
//1>2
//非英文不动

//这是排序过程的实现函数，也可以制定好规则后使用qsort函数。
//结构体数组按照字母大小排序
// void compaer(struct word arr[],int n)
// {
//     int i =0;
//     int j =0;
//     char tmp=0;
//     int tmp_index=0;
//     //冒泡排序
//     for(i=0;i<n;i++)
//     {
//         for(j=i;j<n;j++)
//         {
//             //比较字母大小，不考虑大小写，全部按照大写字母比较
//             if(toupper(arr[i].c)-toupper(arr[j].c)>0)
//             {
//                 //交换字母
//                 tmp =arr[i].c;
//                 arr[i].c =arr[j].c;
//                 arr[j].c =tmp;
//                 //交换序号
//                 tmp_index =arr[i].index;
//                 arr[i].index =arr[j].index;
//                 arr[j].index =tmp_index;
//             }
//             //如果字母相同，比较输入序号
//             else if(toupper(arr[i].c)-toupper(arr[j].c) ==0)
//             {
//                 if(arr[i].index>arr[j].index)
//                 {
//                 //交换字母
//                     tmp =arr[i].c;
//                     arr[i].c =arr[j].c;
//                     arr[j].c =tmp;
//                     //交换序号
//                     tmp_index =arr[i].index;
//                     arr[i].index =arr[j].index;
//                     arr[j].index =tmp_index;
//                 }
//             }
//         }
//     }
// }

发表于 2023-12-12 13:12:01 回复(0)

彭洋a

#include <stdio.h>

#include <string.h>

#include <ctype.h>

int main() {

char str[1001];

while (gets(str) != NULL) {

int len = strlen(str);

for(int i = 0;i<len-1 ;i++)

{

for(int j = 0;j<len-i-1;j++)

{

//判断是不是字母

if(isalpha(str[j]))

{

//是就冒泡排序

int k = j+1;

while(!isalpha(str[k])&&k<len-i-1)

{

k++;

}

if(toupper(str[j])-toupper(str[k])>0&& isalpha(str[k]))

{

char tmp = str[j];

str[j] = str[k];

str[k] = tmp;

}

else {

continue;

}

for(int i = 0;i<len;i++)

{

printf("%c",str[i]);

}

return 0;

}

发表于 2023-10-09 15:50:16 回复(0)

帅气的大魔王喜欢摸鱼

#include <stdio.h>
#include <ctype.h>  // 包含 isalpha() 函数的头文件
#include <stdlib.h> // 包含 qsort() 函数的头文件

// 比较两个字符并忽略大小写的函数
int compare(const void* a, const void* b) {
    // 将参数转换为 char 指针并解引用，将两个字符都转换为小写，然后相减得到差值
    return tolower(*(char*)a) - tolower(*(char*)b);
}

int main() {
    char str[1000], alp[1000]; // 输入字符串、排序字符串
    int id, len; // 输入字符串索引、排序字符串长度

    scanf("%s", str); // 从标准输入读取字符串到输入字符串中
    for (id = 0, len = 0; str[id]; id++) // 遍历输入字符串
        if (isalpha(str[id])) // 检查当前字符是否是字母
            alp[len++] = str[id];// 添加到排序字符串并更新长度
    qsort(alp, len, sizeof(char), compare); // 按字母顺序排序
    for (id = 0, len = 0; str[id]; id++) // 再次遍历输入字符串
        if (isalpha(str[id])) // 检查当前字符是否是字母
            str[id] = alp[len++]; // 用排序字符串的字符替换它
    printf("%s", str); // 将修改后的字符串打印到标准输出
}

发表于 2023-03-22 18:25:29 回复(0)

Cataliar

字母数量规模较小，直接空间换时间，用26个队列存储字母，总共遍历两边即可。

#include <stdio.h>
#include <ctype.h>
#include <string.h>

int main() {
    char queue[26][1000] = {0};
    int tail[26] = {0};
    char buf[1001] = {0};
    scanf("%[^\n]", buf);
    for (int i = strlen(buf)-1; i >= 0; --i) {
        if (!isalpha(buf[i])) {
            continue;
        }
        int idx = tolower(buf[i]) - 'a';
        queue[idx][tail[idx]++] = buf[i];
    }
    int idx = 0;
    for (int i = 0; i < 26; ++i) {
        while (tail[i] > 0) {
            if (!isalpha(buf[idx])) {
                printf("%c", buf[idx++]);
            } else {
                printf("%c", queue[i][tail[i]-1]);
                --tail[i];
                ++idx;
            }
        }
    }
    while (idx < strlen(buf)) {
        printf("%c", buf[idx++]);
    }
    return 0;
}

发表于 2022-08-16 11:59:10 回复(0)

练习时长的代码练习生

获取输入时注意换行符

#include <stdio.h>
#include <string.h>

int main(){
    char a[1000];
    while(scanf("%s",a)!=EOF){
        int len=strlen(a);int k,j;char b[1000]={0};int n=0;
        for(j='a',k='A';j<='z',k<='Z';j++,k++){
            for(int m=0;m<len;m++){
                if(a[m]==k || a[m]==j){
                    b[n++]=a[m];
                }
            }
        }
        n=0;
        for(int m=0;m<len;m++){
            if(!((a[m]>='a' && a[m]<='z') || (a[m]>='A' && a[m]<='Z'))){
                printf("%c",a[m]);
            }
            else{
                printf("%c",b[n++]);
            }
        }
    }
}

发表于 2022-06-07 10:38:02 回复(0)