我最近在面试期间进行了编码测试。有人告诉我：
有一个一百万个的大型未排序数组
int。用户想要检索K最大的元素。你会实现什么算法？
在此期间，我强烈暗示我需要对数组进行排序。
因此，如果性能确实很重要，我建议使用内置sort()或自定义实现。然后我被告知，使用Collectionor数组来存储k最大的元素和 for 循环可以实现大约O(N)，事后看来，我认为这是O(N*k)因为每次迭代都需要与大小数组进行比较K以找到要替换的最小元素，而需要对数组进行排序将导致代码至少为O(N log N).
然后我回顾了 SO 上的这个链接，它建议K数字的优先级队列，每次找到较大的元素时删除最小的数字，这也会给出O(N log N). 编写一个程序，从 10 亿个数字的数组中找出 100 个最大的数字
for循环方法不好吗？我应该如何证明使用 for 循环或优先级队列/排序方法的优点/缺点？我认为，如果数组已经排序，则不需要再次迭代整个数组，即如果对排序数组调用其他检索方法，则它应该是恒定时间。运行实际代码时是否存在一些我在理论化伪代码时没有考虑到的性能因素？