给定一个带有'N'个数字的数组(N> 100).我们怎样才能找到最大的10%？(如果n/10不是整数,我们可以将它舍入)
我提出了3种算法来尝试上述问题,但我不确定哪种算法在渐近运行时是最好的.我是否可以进行任何修改以减少渐近时间？此外,如果N变得非常大,哪种算法可能仍然有效？
我列出了我对以下算法的想法,并且可以真正使用一些帮助来找出最有效的算法.
ALGO-1
我使用选择排序并在10%的数字排序后停止它.
ALGO-2
我构建了一个最大堆并保持删除最大的10%的数字
ALGO-3
没有实现这个,但我的想法是使用任何order-statistic算法来查找包含前10%数字的分区,然后使用合并排序对它们进行排序.