一竞赛有10000人参加,要求找出分数最高的10个人并排序输出,后面的成绩不需要进行排序,问如何最快排出,为什么?

中国人民银行的一道笔试题,我是想直接用冒泡排序就可以了,控制冒泡次数为10次,这样最大的10个数就下沉到了最低部,而且是有序的,不知道还有没有其他最优解,求赐教!

阅读 3.5k
2 个回答

堆排序,控制 heapify 次数为 10,复杂度可降至 O(LogN)。

扫描一趟结束

复杂度O(n)

算法思想

  • 一个长度为10的数组R存结果

  • 从原始数据读取一个数据n,如果nR的最小值大,则替除R的最小值,放入n,并排序

  • 如果nR的最小值小,直接舍弃

  • 一趟结束后,R即为结果

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题