这种方法怎么样

保持一个长度为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);
    }

还有一种算法，比快速选择算法性能更好。它叫做弗洛伊德-铆钉(FR)算法。

原文:https://doi.org/10.1145/360680.360694

下载版本:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf

维基百科文章https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

我尝试在c++中实现快速选择和FR算法。我还将它们与标准c++库实现std::nth_element(基本上是quickselect和heapselect的introselect混合)进行了比较。结果是快速选择和nth_element的平均运行，而FR算法的平均运行约。速度是它们的两倍。

我用于FR算法的示例代码:

template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
    if (n == 0)
        return *(std::min_element(data.begin(), data.end()));
    else if (n == data.size() - 1)
        return *(std::max_element(data.begin(), data.end()));
    else
        return _FRselect(data, 0, data.size() - 1, n);
}

template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
    size_t leftIdx = left;
    size_t rightIdx = right;

    while (rightIdx > leftIdx)
    {
        if (rightIdx - leftIdx > 600)
        {
            size_t range = rightIdx - leftIdx + 1;
            long long i = n - (long long)leftIdx + 1;
            long long z = log(range);
            long long s = 0.5 * exp(2 * z / 3);
            long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);

            size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
            size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);

            _FRselect(data, newLeft, newRight, n);
        }
        T t = data[n];
        size_t i = leftIdx;
        size_t j = rightIdx;
        // arrange pivot and right index
        std::swap(data[leftIdx], data[n]);
        if (data[rightIdx] > t)
            std::swap(data[rightIdx], data[leftIdx]);

        while (i < j)
        {
            std::swap(data[i], data[j]);
            ++i; --j;
            while (data[i] < t) ++i;
            while (data[j] > t) --j;
        }

        if (data[leftIdx] == t)
            std::swap(data[leftIdx], data[j]);
        else
        {
            ++j;
            std::swap(data[j], data[rightIdx]);
        }
        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= n)
            leftIdx = j + 1;
        if (n <= j)
            rightIdx = j - 1;
    }

    return data[leftIdx];
}

template <typename T>
int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}

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

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

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大元素数组')上快速谷歌返回这个: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)