从数组中找到n个最大的元素

Question

我有一个数组

A[4]={4,5,9,1}

我需要它可以给出前3个顶级元素，例如9,5,4

我知道如何找到最大元素，但如何找到第二和第三最大？

即如果

max=A[0]
for(i=1;i<4;i++)
{
  if (A[i]>max)
  {
    max=A[i];
    location=i+1;
  }
}

实际排序不适合我的应用程序，因为，

位置编号对我来说也很重要，即我必须知道前三个最大值出现在哪个位置，在这里是第0，第1和第2个位置...所以我在考虑一个逻辑

在获得最大值之后，如果我可以在该位置放置0并可以对该新数组应用相同的步骤，即{4,5,0,1}

但是我有点困惑如何将我的逻辑写入代码

Answer 1

您可以使用选择算法

还要提一下，复杂度为 O(n)，即选择为 O(n)，迭代为 O(n)，因此总复杂度也是 O(n)