为数组中最小的 k 个元素调整快速选择

Question

我知道我可以在几乎线性的时间内使用 quickselect 获得第 K 阶统计量（即数组中第 k 个最小的数字），但是如果我需要数组的 k 个最小元素？

维基百科link有单元素查找的伪代码，但没有第k个最小元素s查找的伪代码。

应该如何修改 quickselect 以在线性时间内实现它（如果可能）？

Answer 1

实际上不需要修改quickselect。如果我有一个数组（在本例中称为 arrayToSearch）并且我想要 k 个最小的项目，我会这样做：

int i;
int k = 10;  // if you wanted the 10 smallest elements 
int smallestItems = new Array(k);
for (i = 0; i < k; i++)
{
    smallestItems[i] = quickselect(i, arrayToSearch);
}

编辑：我假设 k 是一个相对较小的数字，这将使有效的 Big-O O(n) 成为可能。如果不假设 k 很小，这将具有 O(k*n) 的速度，而不是线性时间。我的回答更容易理解，并且适用于大多数实际目的。 recursion.ninja 的答案在技术上可能更正确，因此更适合学术目的。

Answer 2

我相信在你使用 quickselest 找到第 k-th statictic 之后，你会自动发现结果数组的前 k 个元素是 k 最小的元素, 只是可能没有排序。

此外，quickselect 实际上对第 k 个统计数据进行分区：第 k 个统计数据之前的所有元素都较小（或等于），并且后面的所有元素都大于或等于。这很容易证明。

请注意，例如对于 C++ nth_element

The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less.

如果您不仅需要 k 最小的元素，而且需要 sorted k 最小的元素，您当然可以在 quickselect 之后对它们进行排序。

为数组中最小的 k 个元素调整快速选择

Adapting quickselect for smallest k elements in an array

language-agnostic

arrays

sorting

algorithm

data-structures