在未排序的数组中查找最小/最大的K元素的最有效算法是什么？

Question

我有N个元素的未排序向量，想找到K个最小或最大的元素。预期K比K小N，但算法对于较大的K值（例如N的50-80％）也应有效。

按照重用Quicksort的思路进行思考将意味着完全使用第K个最小/最大元素作为分区的支点。但是找到第K个最小/最大值已经在计算OP的解决方案。

这是Quicksort的分区位：

template<typename T>
int partition(std::vector<T>& arr, int low, int high, T pivot) {
    int i = (low - 1); 

    for (int j = low; j <= high - 1; ++j) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

如果我知道该pivot值对应于第K个最小/最大值，则可以使用上面的分区来求解我的OP。

Answer 1

Partial_sort会将最少（最大）K个元素放在容器的前面，并对它们进行排序。像这样称呼它

std::partial_sort(arr.begin(), arr.begin() + K, arr.end());
std::partial_sort(arr.begin(), arr.begin() + K, arr.end(), std::greater<>());

它将运行大约N log K次

Answer 2

标准库std::nth_element算法可以实现O（n）复杂度所需的功能。接到电话：

std::nth_element(arr.begin(), arr.begin() + K, arr.end());

如果对整个范围进行排序，则第K个元素将是发生的元素。第K个元素之前的所有元素都小于或等于第K个元素。

默认情况下，该算法使用小于运算符。如果需要最大的K个元素，则可以使用其他比较函数，例如：

std::nth_element(arr.begin(), arr.begin() + K, arr.end(), std::greater<>{});