我提出了这个算法，似乎是O(n):

假设k=3我们想找出数组中第三大的元素。我将创建三个变量，并将数组中的每一项与这三个变量中的最小值进行比较。如果数组item大于最小值，则用item的值替换最小值变量。我们继续做同样的事情，直到数组结束。三个变量中的最小值是数组中第三大的项。

define variables a=0, b=0, c=0
iterate through the array items
    find minimum a,b,c
    if item > min then replace the min variable with item value
    continue until end of array
the minimum of a,b,c is our answer

为了找到第K大的项，我们需要K个变量。

例如:(k = 3)

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

有人可以审查这个，让我知道我错过了什么?

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

转到这个链接的结尾:...........

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

在那个('第k大元素数组')上快速谷歌返回这个:http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

"Make one pass through tracking the three largest values so far." 

(它是专门为3d最大)

这个答案是:

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)

我提出了这个算法，似乎是O(n):

假设k=3我们想找出数组中第三大的元素。我将创建三个变量，并将数组中的每一项与这三个变量中的最小值进行比较。如果数组item大于最小值，则用item的值替换最小值变量。我们继续做同样的事情，直到数组结束。三个变量中的最小值是数组中第三大的项。

define variables a=0, b=0, c=0
iterate through the array items
    find minimum a,b,c
    if item > min then replace the min variable with item value
    continue until end of array
the minimum of a,b,c is our answer

为了找到第K大的项，我们需要K个变量。

例如:(k = 3)

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

有人可以审查这个，让我知道我错过了什么?

还有Wirth的选择算法，它的实现比QuickSelect简单。Wirth的选择算法比QuickSelect慢，但经过一些改进，它变得更快。

更详细地说。使用Vladimir Zabrodsky的MODIFIND优化和3中位数的枢轴选择，并注意算法划分部分的最后步骤，我提出了以下算法(想象一下，命名为“LefSelect”):

#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
    int l=0, m = n-1, i=l, j=m;
    float x;

    while (l<m) {
        if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
        if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
        if( a[j] < a[k] ) F_SWAP(a[k],a[j]);

        x=a[k];
        while (j>k & i<k) {
            do i++; while (a[i]<x);
            do j--; while (a[j]>x);

            F_SWAP(a[i],a[j]);
        }
        i++; j--;

        if (j<k) {
            while (a[i]<x) i++;
            l=i; j=m;
        }
        if (k<i) {
            while (x<a[j]) j--;
            m=j; i=l;
        }
    }
    return a[k];
}

在我这里做的基准测试中，LefSelect比QuickSelect快20-30%。