简单地在输入上运行计数排序,O(n)在这种情况下,因为范围是有界的.这也是最有效的方式,因为输出所有学生的任何方式都需要Ω(n).
你可以通过循环输出学生的可能得分(例如,如果存在90个可能的分数,循环学生90次,在第一次输出得分为100的学生,......).
此任务可以通过桶排序完成.但首先你应该循环输入,找到每个分数相关的学生数,然后通过考虑学生数量为每个分数创建一个桶,然后填充桶,注意你应该为桶创建一个数组,你也应该有一个额外的参数,用于保存每个桶中的当前项目数.
第一种方法(直接使用计数排序)是带有O(1)额外空间的O(n),第二种方法是带有O(n)额外空间的O(n),但第二种方法更快,因为它是2*n,而第一种方法是90*n.
| 归档时间： |
|
| 查看次数： |
461 次 |
| 最近记录： |