题解 | 字符串排序

import sys


def merge(f, m, n, k):
    i = m
    j = k + 1
    x = 0
    fn = [" "] * (n - m + 1)
    while (i <= k) and (j <= n):
        if not (("a" <= f[i] <= "z") or ("A" <= f[i] <= "Z")):
            fn[i - m] = f[i]
            i += 1
            continue
        if not (("a" <= f[j] <= "z") or ("A" <= f[j] <= "Z")):
            fn[j - m] = f[j]
            j += 1
            continue
        while not (("a" <= f[x + m] <= "z") or ("A" <= f[x + m] <= "Z")):
            fn[x] = f[x + m]
            x += 1
        if f[i].lower() <= f[j].lower():
            fn[x] = f[i]
            i += 1
        else:
            fn[x] = f[j]
            j += 1
        x += 1
    while i <= k:
        if not (("a" <= f[i] <= "z") or ("A" <= f[i] <= "Z")):
            fn[i-m] = f[i]
            i += 1
            continue
        while not (("a" <= f[m + x] <= "z") or ("A" <= f[m + x] <= "Z")):
            fn[x] = f[m + x]
            x += 1
        fn[x] = f[i]
        i += 1
        x += 1
    while j <= n:
        if not (("a" <= f[j] <= "z") or ("A" <= f[j] <= "Z")):
            fn[j-m] = f[j]
            j += 1
            continue
        while not (("a" <= f[m + x] <= "z") or ("A" <= f[m + x] <= "Z")):
            fn[x] = f[m + x]
            x += 1
        fn[x] = f[j]
        j += 1
        x += 1
    for i in range(m, n + 1):
        f[i] = fn[i - m]


def sortfun(f, m, n):
    if m >= n:
        return
    k = int((m + n) / 2)
    sortfun(f, m, k)
    sortfun(f, k + 1, n)
    merge(f, m, n, k)


for line in sys.stdin:
    line = line[:-1]
    line = list(line)
    sortfun(line, 0, len(line) - 1)
    print("".join(line))