Kotlin高效排序：基于热门度列表及字母序排序学生列表的方法

需求回顾 #

对学生列表排序的规则：

• 优先遵循**热门度列表（已按积分降序排好）**的顺序，热门列表中出现的学生，排序位置和热门列表一致
• 热门列表未覆盖的学生，按姓名字母序排序

示例数据 #

data class Student(val id: Int, val name: String)
data class Ranking(val id: Int, val points: Int)

val students = listOf<Student>(
    Student(id = 3, name = "mike"),
    Student(id = 2, name = "mathew"),
    Student(id = 1, name = "john"),
    Student(id = 4, name = "alan")
)

val popularity = listOf<Ranking>(
    Ranking(id= 2, points = 30),
    Ranking(id= 3, points = 15)
)

高效实现方案 #

核心是把热门列表转成ID到排序优先级的映射表，让排序时能O(1)时间获取优先级，避免反复遍历热门列表查ID，大幅提升效率。

步骤1：构建热门优先级映射

用withIndex()拿到热门列表中每个ID的位置索引（索引越小，优先级越高），存入Map：

// 键：学生ID，值：该ID在热门列表中的优先级（索引），不在列表的学生默认用Int.MAX_VALUE（优先级最低）
val popularityPriorityMap = popularity.withIndex()
    .associate { (index, ranking) -> ranking.id to index }

步骤2：自定义排序规则

用compareBy()组合两个排序条件：

1. 优先按热门优先级排序（值越小越靠前）
2. 热门优先级相同（即不在热门列表）时，按姓名字母序排序（默认不区分大小写，需区分可去掉lowercase()）

val sortedStudents = students.sortedWith(compareBy(
    { student -> popularityPriorityMap.getOrDefault(student.id, Int.MAX_VALUE) },
    { student -> student.name.lowercase() }
))

结果验证 #

运行代码后输出与期望完全一致：

[
 Student(id=2,name="mathew"),
 Student(id=3,name="mike"),
 Student(id=4,name="alan"),
 Student(id=1,name="john")
]

效率说明 #

• 构建映射表时间复杂度O(n)（n为热门列表长度）
• 排序时间复杂度O(m log m)（m为学生列表长度），是基于比较的排序算法最优复杂度
• 优先级查找为O(1)，相比遍历热门列表查ID的O(n)方式，数据量大时效率提升显著

内容的提问来源于stack exchange，提问作者yuu