某个大型的网络游戏网站,现有几亿用户,为了实时获取前十名游戏_

一念清浊

第一反应是桶排序可惜没有

发表于 2019-10-23 10:29:41 回复(0)

Tahara

STL实现就是先压入10个元素。储存最小元素的值。如果新的元素的值大于最小值，就先弹出后压入。手动实现也就是用小根堆来实现。复杂度大概是o(n)。每一次更新需要消耗常数时间。

编辑于 2016-09-22 16:16:21 回复(0)

想做樱木的圆寸少年

感觉前面的评论的朋友都没有说出问题的本质。

我觉得这道题选择堆排序的根本原因在于需求只说了获取前十名玩家的信息。

除了堆排序之外，其他的排序都不能在单次logN的条件下完成对最大值/最小值的查找。

而堆排序，每次排序的结果就是找到当前堆中的最大/最小值。

因此完成需求的时间复杂度为O(logN)。

当我们需要找到常数级的最大/最小值时，往往堆排序是我们应该最先考虑的

快速排序只有在对整个空间排序完成后才能找出前10名，因而时间复杂度是O(logN).

因此选D

编辑于 2016-03-08 09:43:45 回复(8)

牛客706988号

D,参考如下比较表。堆排序时间复杂度和空间复杂度都是最优的。

个人感觉堆排序唯一的缺点就是算法较为复杂，代码量稍大。

排序法	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n²)	O(n²)	稳定	O(1)
快速排序	O(n²)	O(n*log₂n)	不稳定	O(log₂n)~O(n)
选择排序	O(n²)	O(n²)	稳定	O(1)
二叉树排序	O(n²)	O(n*log₂n)	不一顶	O(n)
插入排序	O(n²)	O(n²)	稳定	O(1)
堆排序	O(n*log₂n)	O(n*log₂n)	不稳定	O(1)
希尔排序	O	O	不稳定	O(1)

发表于 2015-12-03 17:40:48 回复(2)

炫

各种排序的稳定性，时间复杂度和空间复杂度总结：

发表于 2015-12-08 14:08:40 回复(0)

huixieqingchun

要注意理解题意。获取前十名的成绩，用堆排序每次取得最大值。

发表于 2016-06-03 21:59:01 回复(0)

IM_Rocket

我觉得评论中没有人说明使用堆排序到底具体怎么处理；下面我猜想一下，只是猜想。

这是个topk问题，如果使用堆排序的话我觉得应该是这样做的，先从海量数据中选取前k个数据建立小根堆，后面的数据不断的和根顶元素作比较，如果比根顶元素大则替换根顶元素，并重新调整为小根堆，如果比根顶元素小，则继续读取后面的数字。最后按照中序遍历的方式输出堆的内容就是海量数据的前k个数值。这种方式的好处在于空间复杂度为K 时间复杂度为O（nKlogK）

发表于 2017-03-25 10:00:04 回复(0)