返回题目列表
COMP2521
排序 · 按键稳定排序
排序 · 按 key【稳定】升序
每条记录是「一个整数 key + 一个不含空格的标签」。请按 key 从小到大排序,并保证排序是稳定的:当两条记录 key 相等时,它们在输出里的先后必须和输入里一致。
这正是考试爱考的点(如按次要键二次排序)。请补全 stableSortByKey,记得把 keys[] 和 labels[] 一起搬动。
易错点:① 想稳定,比较时只能在严格大于才交换/后移(用>,不要>=);用>=会把 key 相等的记录对调,破坏稳定。② 选择排序、快排这类「远距离交换」的算法天生不稳定,这里请用插入排序或冒泡这种相邻比较的稳定算法。③ 搬动 key 时别忘了同步搬 label,否则两者会错位。
输入
- 第 1 行:整数
n。 - 接下来
n行:每行一个整数key和一个标签(用空格隔开,标签不含空格)。
输出
n行:稳定排序后的记录,每行key 标签。
示例:输入 4 / 3 a / 1 b / 3 c / 1 d → 输出 1 b / 1 d / 3 a / 3 c(key=1 的 b 仍在 d 前,key=3 的 a 仍在 c 前——顺序没被打乱)。
样例
stdin
4 3 a 1 b 3 c 1 d
期望输出
1 b 1 d 3 a 3 c
stdin
1 5 x
期望输出
5 x
c-dcc
14