HJ68. 成绩排序
题目描述
输入若干学生的姓名和成绩，按成绩排序：
- 排序方式 flag=0：按成绩从高到低（降序）
- 排序方式 flag=1：按成绩从低到高（升序）
成绩相同时，按照输入顺序排列（稳定排序）。
输入格式
- 第 1 行：学生人数 n
- 第 2 行：排序方式 flag（0 降序，1 升序）
- 第 n 行：每行
姓名 成绩
输出格式
排序后的 n 行，每行 姓名 成绩。
示例
示例 1
输入：
3
0
fang 90
yang 50
ning 70
输出：
fang 90
ning 70
yang 50
示例 2
输入：
3
1
fang 90
yang 50
ning 70
输出：
yang 50
ning 70
fang 90
解题思路
第一步：理解问题本质
按成绩对 (姓名, 成绩) 排序，且成绩相同时保持输入顺序。这正好是"稳定排序"的定义。Python 的 list.sort() 是稳定排序。
第二步：暴力解法
自己实现冒泡排序，只按成绩比较，相等时不交换位置 → 等价于稳定排序。O(n²)，正确但低效。
第三步：最优解法
直接用内建稳定排序，以成绩作为排序 key，按 flag 决定升降序：
students.sort(key=lambda x: x[1], reverse=(flag == 0))
reverse=(flag == 0)：flag=0 时降序，flag=1 时升序。Python 的 sort 稳定，成绩相同者自动保持输入顺序。
完整代码实现
算法可视化 · 逐帧回放这道题的代码5 帧 · 录制输入
import sys
def solve():
data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it))
flag = int(next(it))
students = []
for _ in range(n):
name = next(it).decode()
score = int(next(it))
students.append((name, score))
students.sort(key=lambda x: x[1], reverse=(flag == 0))
for name, score in students:
print(name, score)
if __name__ == "__main__":
solve()
示例推演
以示例 1（flag=0 降序）为例：
初始顺序：[(fang,90), (yang,50), (ning,70)]
按成绩降序排序：90 > 70 > 50
结果：
fang 90
ning 70
yang 50
若成绩相同，如 [(a,70), (b,70), (c,60)]，由于稳定排序，a 仍在 b 前面（保持输入顺序）。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 简单但慢 |
| 内建排序 | O(n log n) | O(n) | 最优 |
n 为学生人数
易错点总结
1. 忘记稳定排序
成绩相同时若不保持输入顺序会判错。Python 的 sort 是稳定的，直接用即可；若用 key 排序，相同 key 会自动保持原顺序。
2. flag 与升降序方向搞反
flag=0 是降序、flag=1 是升序，用 reverse=(flag == 0) 精确表达，避免 if/else 出错。
3. 成绩类型
成绩应转为整数 int，否则字符串排序会按字典序（"90" < "9"）出错。
扩展思考
- 稳定排序的意义：多关键字排序时，先排次要关键字再排主要关键字，可复用稳定排序逐列完成。
- 若 n 极大且需要额外比较条件，可改用
sorted配合自定义cmp（通过functools.cmp_to_key）。