题解 | #字符串排序# | 稳定冒泡排序思路

思路

观察规则1与规则2的约束，由于规则1要求排序，且规则2要求保持英文字符大小写相对位置不变，因此首先想到的是稳定排序算法，于是，本题解采用稳定冒泡排序，作为英文字符串排序的核心动作。整体思路如下：
1、读取输入字符串，提取其中的所有英文字符，并保存至新的字符串中；
2、新字符串中均为英文字符，但大小写不确定，因此采用改进的稳定冒泡排序，满足题目中规则1与规则2的约束；
3、将排序好的字符串，顺序输出到原输入字符串中的英文字符的位置，满足题目中规则3的约束。

算法缺陷

尽管进行了优化，但是冒泡排序的复杂度依旧较高。

详细代码及注释

#include <stdio.h>

void swap(char *, char *);
void bubbleSortSpecial(char *, int);

//1：将字符串中的所有英文（大小写）字符，复制到新的字符串中；
//2：对新字符串，进行稳定的冒泡排序，需要考虑到，不能够改变大小写字符的而相对位置；
//   第一的想到的，就是稳定排序算法；
//3：将排好序的字符串，重新赋值到原字符串的对应位置。
int main(){
    char str[1001] = {0};
    while(scanf("%[^\n]", str) != EOF){
        getchar();//清空输入缓冲区
        //将字符串中的英文字符进行提取
        char chStr[1001] = {0};
        int i = 0, j = 0;
        for(; str[i] != '\0'; i++){
            if((str[i] >= 'A' && str[i] <= 'Z') || (str[i] >= 'a' && str[i] <= 'z')){
                chStr[j++] = str[i];
            }
        }
        //针对chStr字符串，进行特殊的冒泡排序
        bubbleSortSpecial(chStr, j);
        //大小写字符串排序好后，顺序输出到原字符串中的字符位置，满足规则3
        for(i = 0, j = 0; str[i] != '\0'; i++){
            if((str[i] >= 'A' && str[i] <= 'Z') || (str[i] >= 'a' && str[i] <= 'z')){
                str[i] = chStr[j++];
            }
        }
        //输出字符串，字符串中的大小写英文字母，已经按照所有规则进行了排序
        printf("%s\n", str);
    }
    return 0;
}

void swap(char *a, char *b){
    char temp = *a;
    *a = *b;
    *b = temp;
    return;
}

void bubbleSortSpecial(char *str, int size){
    int flag, i, j;
    char A, B;//分别用来记录str[j]与str[j+1]对应的“小写字母”，用以作为排序的依据
    for(i = 0; i < size - 1; i++){
        flag = 0;
        for(j = 0; j <= size - 2 - i; j++){
            //由于在排序时，需要暂时忽略掉大小写，因此需要借助辅助变量，来进行字符“大小的比较”；
            //首先将str[i]与str[j + 1]替换为对应的小写字符（或者大写也行，统一即可）
            //注：A和B的使用，使得排序不区分大小写，也通过A>B条件判断，使排序稳定，
            //     也即使得规则1与规则2被满足。
            A = str[j] < 97 ? (str[j] + 32) : str[j];
            B = str[j + 1] < 97 ? (str[j + 1] + 32) : str[j + 1];
            if(A > B){
                swap(&str[j], &str[j + 1]);
                flag = 1;
            }
        }
        if(!flag){
            break;
        }
    }
    return;
}

欢迎交流讨论~~~