这种方法怎么样

保持一个长度为k的缓冲区和一个tmp_max，得到tmp_max为O(k)并执行n次因此类似于O(kn)

是这样还是我漏掉了什么?

虽然它没有击败快速选择的平均情况和中值统计方法的最坏情况，但它非常容易理解和实现。

它类似于快速排序策略，在快速排序策略中，我们选择一个任意的枢轴，并将较小的元素放在它的左边，将较大的元素放在右边

    public static int kthElInUnsortedList(List<int> list, int k)
    {
        if (list.Count == 1)
            return list[0];

        List<int> left = new List<int>();
        List<int> right = new List<int>();

        int pivotIndex = list.Count / 2;
        int pivot = list[pivotIndex]; //arbitrary

        for (int i = 0; i < list.Count && i != pivotIndex; i++)
        {
            int currentEl = list[i];
            if (currentEl < pivot)
                left.Add(currentEl);
            else
                right.Add(currentEl);
        }

        if (k == left.Count + 1)
            return pivot;

        if (left.Count < k)
            return kthElInUnsortedList(right, k - left.Count - 1);
        else
            return kthElInUnsortedList(left, k);
    }

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

我想提出一个答案

如果我们取前k个元素并将它们排序成一个k个值的链表

对于每一个其他的值，即使在最坏的情况下如果我们对剩下的n-k个值进行插入排序即使在最坏的情况下，比较的数量也将是k*(n-k)对于前k个要排序的值让它是k*(k-1)所以结果是(nk-k)也就是o(n)

干杯

在那个('第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)

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

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