[编程题]字符串排序

我看好多玩家都借助了额外空间（数组）来排序，这种就不多介绍了。这里主要介绍一种仅在初始数组内部就完成排序的方法 。

根据题意，考虑到输入的顺序不能变，比如输入Aa就要输出Aa，如果输入aA则输出Aa，这说明 要求排序是稳定的。 考虑使用 冒泡排序 。

换汤不换药，，，普通的冒泡就是相邻元素之间交换的，循环的时候每次i++ j++这样，这个本质上不就是一直找下一个元素嘛！ 于是只要写个 next(i) / pre(i) ，用来求下标 i 的 下一个/上一个 英文字母的下标，然后用 next/pre 代替 i++ / i--，这样就和普通的冒泡排序没啥区别了，一般的冒泡是逻辑相邻加物理相邻，而这个冒泡则是逻辑相邻（就算是链表照样能够冒！）（注意临界条件）

直接上C语言：

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

char s[500];
int n;

// 获取下标 i 之后的下一个字母的下标
int next(int i)
{
    ++i;
    while (i < n && !isalpha(s[i])) ++i;
    return i;
}

// 获取下标 i 之前的上一个字母的下标
int pre(int i)
{
    --i;
    while (i >= 0 && !isalpha(s[i])) --i;
    return i;
}

void func()
{
    // 跳过非英文字母结尾，这部分不用考虑排序
    while (n - 1 >= 0 && !isalpha(s[n - 1])) --n;
    // last_second是倒数第二个英文字母的下标
    int last_second = pre(n - 1), has_sorted = 0;

    for (int i = 0; i <= last_second; i = next(i)) {
        for (int j = 0, j1; j <= last_second - has_sorted; j = j1) {
            j1 = next(j);
            if (tolower(s[j]) > tolower(s[j1])) {
                char tmp = s[j];
                s[j] = s[j1];
                s[j1] = tmp;
            }
        }
        ++has_sorted;
    }

    puts(s);
}

int main()
{
    while (fgets(s, sizeof(s), stdin)) {
        n = strlen(s);
        s[--n] = '\0';  // replace '\n' with '\0'
        func();
        memset(s, 0, sizeof(s));
    }

    return 0;
}