现有 n 名学生的成绩记录，每位学生的记录包含两门课程的成绩：课程 1（记为C1）和课程 2（记为C2）。排序规则如下：

• 首先，依据C1成绩升序排列；
• 若两名学生的C1成绩相同，则依据其总分（即C1+C2）升序排列。请从下列排序算法中，选择最适合实现上述需求的算法（ ）

A. 基数排序 B. 快速排序 C. 希尔排序 D. 选择排序

[tag_link]

正确答案：A

排序规则要求先按 C1 成绩升序，再按总分升序，这属于多键排序问题。基数排序是一种稳定的排序算法，特别适合多键排序，因为它可以对每个键位进行独立排序，且稳定性保证了当主键（C1）相同时，次键（总分）的顺序得以保持。具体实现时，可以先按总分（低优先级键）进行稳定排序，再按 C1（高优先级键）进行稳定排序，从而满足规则。其他算法中，快速排序、希尔排序和选择排序都不是稳定的，虽然可以通过自定义比较函数在一次排序中处理多键，但稳定性和效率不如基数排序。此外，学生成绩通常为整数，基数排序对整数排序效率较高。因此，基数排序是最适合的算法。