我正在寻找从输入数组返回前k元素的有效方法。
一种方法是对数组进行排序并从数组末尾返回k元素。
这里还建议使用其他方法，其中一种使用快速选择算法，但据我了解，快速选择仅返回未排序数组中的第 k 个元素。返回后，k左侧和右侧的元素仍未排序。
所以它应该是这样的：
while k>0{
quickselect(int[] arr, k);
k--;
}
快速选择是O(n)，我们这样做了k次，因此整体时间复杂度O(n*k) 。
但帖子中的数据表明，这比O(n log n)要好。
从 100 万个样本中选择前 200 名意味着前一种情况200 million，但在后一种情况下20 million。显然，这要好得多。
我了解如何使用快速选择来选择前 200 个元素是否正确？
不，你不需要O(nk)时间 - 它可以在O(n)（平均情况下）完成。
快速选择的最终结果将是数组中从末尾的第 k 个位置的第 k 个元素，左侧是较小的元素，右侧是较大的元素。
因此，从该元素到右侧的所有元素都将是 k 个最大的元素 - 在 O(k) 中提取这些元素（使用简单的 for 循环）是微不足道的，最终总运行时间为 O(n) .
或者，由于您在运行快速选择后知道第 k 个元素，因此您可以再次遍历数组并提取所有大于或等于该元素的元素（这可以一次性完成 - 也是O(n)）。
如果要按排序顺序返回它们，则需要额外的O(k log k)（对它们进行排序）。
如果 n 不是太大，那么
快速选择是很好的，但是如果你有非常大的 n（太大而无法放入内存）或未知的 n（假设你看到一个无限的样本流，并且您希望能够在任何时候报告迄今为止看到的 200 个最大的样本），那么另一种方法是保留一个 k 元素最小堆，每次你看到一个新元素时， 将其与最小堆的顶部（到目前为止 200 个最大元素中最小的一个）进行比较，如果它更大，则弹出堆的旧顶部并将新元素推送到堆上。