A Programmer's Companion to Algorithm Analysis给出了一个O(n)的版本，尽管作者指出常数因子如此之高，您可能更喜欢简单的排序-列表-然后选择方法。

我已经回答了你的问题:)

这是一个Javascript实现。

如果您释放了不能修改数组的约束，则可以使用两个索引来标识“当前分区”(经典快速排序样式- http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/)来防止使用额外的内存。

function kthMax(a, k){
    var size = a.length;

    var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2) 

    //Create an array with all element lower than the pivot and an array with all element higher than the pivot
    var i, lowerArray = [], upperArray = [];
    for (i = 0; i  < size; i++){
        var current = a[i];

        if (current < pivot) {
            lowerArray.push(current);
        } else if (current > pivot) {
            upperArray.push(current);
        }
    }

    //Which one should I continue with?
    if(k <= upperArray.length) {
        //Upper
        return kthMax(upperArray, k);
    } else {
        var newK = k - (size - lowerArray.length);

        if (newK > 0) {
            ///Lower
            return kthMax(lowerArray, newK);
        } else {
            //None ... it's the current pivot!
            return pivot;
        }   
    }
}  

如果你想测试它的表现，你可以使用这个变量:

    function kthMax (a, k, logging) {
         var comparisonCount = 0; //Number of comparison that the algorithm uses
         var memoryCount = 0;     //Number of integers in memory that the algorithm uses
         var _log = logging;

         if(k < 0 || k >= a.length) {
            if (_log) console.log ("k is out of range"); 
            return false;
         }      

         function _kthmax(a, k){
             var size = a.length;
             var pivot = a[parseInt(Math.random()*size)];
             if(_log) console.log("Inputs:", a,  "size="+size, "k="+k, "pivot="+pivot);

             // This should never happen. Just a nice check in this exercise
             // if you are playing with the code to avoid never ending recursion            
             if(typeof pivot === "undefined") {
                 if (_log) console.log ("Ops..."); 
                 return false;
             }

             var i, lowerArray = [], upperArray = [];
             for (i = 0; i  < size; i++){
                 var current = a[i];
                 if (current < pivot) {
                     comparisonCount += 1;
                     memoryCount++;
                     lowerArray.push(current);
                 } else if (current > pivot) {
                     comparisonCount += 2;
                     memoryCount++;
                     upperArray.push(current);
                 }
             }
             if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);

             if(k <= upperArray.length) {
                 comparisonCount += 1;
                 return _kthmax(upperArray, k);
             } else if (k > size - lowerArray.length) {
                 comparisonCount += 2;
                 return _kthmax(lowerArray, k - (size - lowerArray.length));
             } else {
                 comparisonCount += 2;
                 return pivot;
             }
     /* 
      * BTW, this is the logic for kthMin if we want to implement that... ;-)
      * 

             if(k <= lowerArray.length) {
                 return kthMin(lowerArray, k);
             } else if (k > size - upperArray.length) {
                 return kthMin(upperArray, k - (size - upperArray.length));
             } else 
                 return pivot;
     */            
         }

         var result = _kthmax(a, k);
         return {result: result, iterations: comparisonCount, memory: memoryCount};
     }

剩下的代码只是创建一些游乐场:

    function getRandomArray (n){
        var ar = [];
        for (var i = 0, l = n; i < l; i++) {
            ar.push(Math.round(Math.random() * l))
        }

        return ar;
    }

    //Create a random array of 50 numbers
    var ar = getRandomArray (50);   

现在给你做几次测试。 因为Math.random()每次都会产生不同的结果:

    kthMax(ar, 2, true);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 34, true);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);

如果你测试它几次，你甚至可以看到经验的迭代次数，平均来说，O(n) ~=常数* n, k的值不会影响算法。

你可以用O(n + kn) = O(n)(对于常数k)表示时间，用O(k)表示空间，通过跟踪你见过的最大的k个元素。

对于数组中的每个元素，您可以扫描k个最大的元素列表，并将最小的元素替换为更大的新元素。

Warren的优先级堆解决方案更简洁。

对于k非常小的值(即k << n)，我们可以在~O(n)时间内完成。否则，如果k与n比较，我们得到O(nlogn)

还有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%。

我提出了这个算法，似乎是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

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