成绩排序

排序约 865 字大约 3 分钟

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 决定升降序：

# key 取成绩；flag=0 要降序所以 reverse=True。sort 稳定，同分者保持输入顺序
students.sort(key=lambda x: x[1], reverse=(flag == 0))

reverse=(flag == 0)：flag=0 时降序，flag=1 时升序。Python 的 sort 稳定，成绩相同者自动保持输入顺序。

完整代码实现

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    # 前两个 token 是人数与排序方式，之后每两个 token 构成一条记录
    n = int(next(it))
    flag = int(next(it))

    students = []
    for _ in range(n):
        # 姓名从 bytes 解码；成绩转整数，否则会按字符串字典序比较
        name = next(it).decode()
        score = int(next(it))
        students.append((name, score))

    # 只按成绩这一列排；sort 稳定，同分自动保持输入先后
    students.sort(key=lambda x: x[1], reverse=(flag == 0))

    for name, score in students:
        print(name, score)


if __name__ == "__main__":
    solve()