c++标准库几乎完全有这个函数调用nth_element，尽管它确实会修改数据。它有线性运行时间，O(N)，它也做部分排序。

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a

这叫做求k阶统计量。有一个非常简单的随机算法(叫做quickselect)，平均时间为O(n)，最坏情况时间为O(n²)，还有一个相当复杂的非随机算法(叫做introselect)，最坏情况时间为O(n)。维基百科上有一些信息，但不是很好。

你需要的一切都在这些幻灯片里。只需提取O(n)最坏情况算法(introselect)的基本算法:

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

在Cormen等人的《算法介绍》一书中也有非常详细的描述。

遍历列表。如果当前值大于存储的最大值，则将其存储为最大值，并将1-4向下碰撞，5从列表中删除。如果不是，将它与第2条进行比较，然后做同样的事情。重复，检查所有5个存储值。应该是O(n)

首先，我们可以从未排序的数组中构建一个BST，它需要O(n)时间，从BST中我们可以找到O(log(n))中第k个最小的元素，它的总计数为O(n)。

创建优先级队列。 将所有元素插入堆中。 调用poll() k次。 getKthLargestElements(int[] arr) ｛ PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (y-x)); //将所有元素插入堆中 For (int ele: arr) pq.offer(避署); //调用poll() k次 int i = 0; 而(i&lt; k) ｛ Int result = pq.poll(); ｝ 返回结果; ｝

    function nthMax(arr, nth = 1, maxNumber = Infinity) {
      let large = -Infinity;
      for(e of arr) {
        if(e > large && e < maxNumber ) {
          large = e;
        } else if (maxNumber == large) {
          nth++;
        }
      }
      return nth==0 ? maxNumber: nthMax(arr, nth-1, large);
    }

    let array = [11,12,12,34,23,34];

    let secondlargest = nthMax(array, 1);

    console.log("Number:", secondlargest);