package main
import (
"fmt"
"sort"
)
// Student 学生结构体
type Student struct {
Name string // 学生姓名
Score int // 学生成绩
Index int // 输入顺序，用于稳定排序
}
// StudentList 学生列表管理
type StudentList struct {
Students []Student // 学生列表
SortOrder int // 排序方式：0-降序，1-升序
}
// Add 添加学生
func (sl *StudentList) Add(name string, score int, index int) {
student := Student{
Name: name,
Score: score,
Index: index,
}
sl.Students = append(sl.Students, student)
}
// Sort 执行稳定排序
func (sl *StudentList) Sort() {
sort.SliceStable(sl.Students, func(i, j int) bool {
// 如果成绩相同，按输入顺序排序（保持稳定性）
if sl.Students[i].Score == sl.Students[j].Score {
return sl.Students[i].Index < sl.Students[j].Index
}
// 根据排序方式决定升序或降序
if sl.SortOrder == 0 {
// 降序：成绩大的在前
return sl.Students[i].Score > sl.Students[j].Score
} else {
// 升序：成绩小的在前
return sl.Students[i].Score < sl.Students[j].Score
}
})
}
// Display 输出排序结果
func (sl *StudentList) Display() {
for _, student := range sl.Students {
fmt.Printf("%s %d\n", student.Name, student.Score)
}
}
func main() {
var n, op int
// 读取学生数量和排序方式
fmt.Scan(&n)
fmt.Scan(&op)
// 创建学生列表
studentList := StudentList{
Students: make([]Student, 0, n),
SortOrder: op,
}
// 读取学生信息
for i := 0; i < n; i++ {
var name string
var score int
fmt.Scan(&name, &score)
// 添加学生，记录输入顺序
studentList.Add(name, score, i)
}
// 执行稳定排序
studentList.Sort()
// 输出排序结果
studentList.Display()
}
解题思路
算法分析
这道题的核心是稳定排序和学生信息管理。主要涉及：
- 数据结构设计：学生信息的存储和排序
- 稳定排序算法：保持相同成绩学生的原始顺序
- 排序条件控制：根据op参数决定升序或降序
- 多关键字排序：成绩为主键，输入顺序为辅助键
数据结构设计
classDiagram
class Student {
+string Name
+int Score
+int Index
+String() string
}
class StudentList {
+[]Student students
+int sortOrder
+Add(name, score, index)
+Sort()
+Display()
}
Student --> StudentList : contains
稳定排序原理
graph TD
A[学生成绩列表] --> B[按成绩排序]
B --> C{成绩相同?}
C -->|是| D[保持原始顺序]
C -->|否| E[按成绩排序]
D --> F[稳定排序结果]
E --> F
G[排序策略] --> H[主键: 成绩]
G --> I[辅助键: 输入顺序]
H --> J[升序/降序]
I --> K[始终升序]
J --> L[最终排序结果]
K --> L
排序逻辑详解
flowchart TD
A[输入学生信息] --> B[创建学生结构体]
B --> C[记录输入顺序]
C --> D[添加到学生列表]
D --> E{读取完所有学生?}
E -->|否| A
E -->|是| F[执行稳定排序]
F --> G{排序方式op}
G -->|0| H[按成绩降序]
G -->|1| I[按成绩升序]
H --> J[自定义比较函数]
I --> J
J --> K[稳定排序算法]
K --> L[输出排序结果]
比较函数设计
graph TD
A[比较函数] --> B{成绩是否相等?}
B -->|是| C[按输入顺序排序]
B -->|否| D{排序方式}
D -->|升序| E[成绩小的在前]
D -->|降序| F[成绩大的在前]
C --> G[保持稳定性]
E --> H[排序结果]
F --> H
G --> H
算法流程图
flowchart TD
A[读取学生数量n] --> B[读取排序方式op]
B --> C[初始化学生列表]
C --> D[循环读取学生信息]
D --> E[解析姓名和成绩]
E --> F[创建学生对象]
F --> G[记录输入顺序]
G --> H[添加到列表]
H --> I{是否读取完毕?}
I -->|否| D
I -->|是| J[执行稳定排序]
J --> K{排序方式判断}
K -->|op=0| L[降序排序]
K -->|op=1| M[升序排序]
L --> N[自定义比较函数]
M --> N
N --> O[sort.SliceStable执行]
O --> P[输出排序结果]
代码实现思路
- 学生结构体：包含姓名、成绩、输入顺序提供清晰的数据封装支持字符串输出格式
- 稳定排序实现：使用Go的sort.SliceStable函数自定义比较函数处理排序逻辑确保相同成绩的学生保持原始顺序
- 排序策略：主键：成绩（按op参数升序或降序）辅助键：输入顺序（始终升序，保证稳定性）多关键字排序确保结果正确
时间复杂度分析
- 时间复杂度：O(n log n)，其中n是学生数量
- 空间复杂度：O(n)，存储学生信息
关键优化点
- 稳定排序：使用sort.SliceStable保证稳定性
- 输入顺序记录：为每个学生记录输入顺序
- 比较函数优化：先比较成绩，再比较输入顺序
- 内存管理：使用切片高效管理学生列表
边界情况处理
- 成绩相同：按输入顺序排列
- 姓名相同：按成绩和输入顺序排列
- 单个学生：直接输出
- 极端成绩：0分和100分的正确处理
测试用例分析
graph TD
A[示例1: 3学生降序] --> B[fang 90, yang 50, ning 70]
B --> C[排序后: fang 90, ning 70, yang 50]
D[稳定性测试] --> E[相同成绩学生]
E --> F[保持输入顺序]
G[边界测试] --> H[单个学生]
G --> I[成绩相同]
G --> J[姓名相同]
C --> K[验证排序正确]
F --> K
H --> K
I --> K
J --> K
算法特点
- 稳定排序：保证相同成绩学生的相对位置
- 灵活排序：支持升序和降序两种模式
- 高效实现：使用标准库的稳定排序算法
- 易于扩展：可以轻松添加更多排序关键字
实际应用场景
- 学生成绩管理：学校成绩排名系统
- 考试排序：各类考试成绩排序
- 竞赛排名：保持并列名次的相对顺序
- 数据分析：需要稳定排序的数据处理
稳定排序的重要性
graph TD
A[稳定排序特点] --> B[保持相对顺序]
A --> C[多关键字排序]
A --> D[公平性保证]
B --> E[相同成绩学生]
C --> F[成绩优先输入顺序次之]
D --> G[先到先得原则]
E --> H[实际应用价值]
F --> H
G --> H
这个问题的关键在于正确理解稳定排序的含义和设计合理的比较函数，确保在成绩相同的情况下保持学生的原始输入顺序。
京公网安备 11010502036488号