OlveraeUNSW
返回题目列表
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