HJ26. 字符串排序
题目描述
编写程序，对输入的字符串按如下规则排序：
- 英文字母按 ASCII 大小排序，但不区分大小写，且相同字母（如 A 和 a）按输入顺序保持相对位置。
- 非字母字符保持原位不动。
输入格式
一行待排序的字符串（可含空格、数字、标点）。
输出格式
排序后的字符串。
示例
示例 1
输入：
A Famous Saying: Much Ado About Nothing (2012/8).
输出：
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).
示例 2
输入：
a1b2c3
输出：
a1b2c3
解题思路
第一步：理解问题本质
字符串中混有字母和非字母。字母需要排序（不区分大小写），非字母原地不动。排序后字母依次填入原来字母占的位置。
第二步：暴力解法
为每个字母位置尝试所有字母排列，检查是否满足排序规则。组合爆炸，不可行。
第三步：提取字母 + 稳定排序
两步走：
- 把所有字母提取出来，按小写形式排序 → 不区分大小写。
- 稳定排序保证相同字母（如 A 和 a）保持输入顺序。
- 遍历原字符串，遇到字母按顺序回填排序结果，遇到非字母原样保留。
第四步：最优解法
Python 的 sorted 是稳定排序，用 key=str.lower 即可同时实现"大小写不敏感"与"同字母稳定"：
letters = sorted([ch for ch in s if ch.isalpha()], key=str.lower)
res = []
idx = 0
for ch in s:
if ch.isalpha():
res.append(letters[idx]); idx += 1
else:
res.append(ch)
print(''.join(res))
完整代码实现
算法可视化 · 逐帧回放这道题的代码187 帧 · 录制输入
import sys
def sort_string(s: str) -> str:
letters = sorted([ch for ch in s if ch.isalpha()], key=str.lower)
res = []
idx = 0
for ch in s:
if ch.isalpha():
res.append(letters[idx])
idx += 1
else:
res.append(ch)
return ''.join(res)
def solve():
line = sys.stdin.readline().rstrip('\n')
print(sort_string(line))
if __name__ == "__main__":
solve()
示例推演
以 "aBc b A" 为例：
步骤 1：提取字母 ['a','B','c','b','A']
步骤 2：按小写稳定排序 → ['A','a','B','b','c']
步骤 3：遍历原串回填：
'a'（字母）→'A''B'（字母）→'a''c'（字母）→'B'' '（非字母）→' ''b'（字母）→'b'' '（非字母）→' ''A'（字母）→'c'
结果："AaB bc"。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 提取+稳定排序 | O(n log n) | O(n) | n 为字符串长度 |
易错点总结
1. 忽略稳定排序要求
如果直接用 sorted(key=str.lower) 且没有注意稳定性，相同字母的相对顺序可能被打乱。Python 的 sorted 默认稳定，用它对字符排序即可满足要求。
2. 使用 str.lower() 时误用 lower 为排序键
key=str.lower 是把每个字符转小写后比较，正确；不要写成 key=ch.lower（把字符列表当成可调用对象）导致报错。
3. 非字母字符位置错乱
回填时必须保持非字母在原位置，不能把排序后的字母覆盖到非字母位置。
扩展思考
- 若要求严格按 ASCII 排序（区分大小写），去掉
key=str.lower即可。 - 稳定排序在"先按一列排、再按另一列排"的场景非常有用（如成绩排序按总分再按姓名）。