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