algorithm - 如何使用快速排序找到 K 个最小值

Question

如果我对所有值进行排序并选择第一个 K 值，问题就很简单。但是它浪费了太多时间，因为可能在整个数组排序之前已经排序了最小的 K 值。我认为解决这个问题的方法是在代码中添加一个标志，但我不知道如何放置标志来判断最小的k值是否已经排序。

Answer 1

您可以使用随机选择算法在 O(n) 时间内解决此问题。最后，只返回从 0 到 k 的子数组。

Answer 2

我认为可以通过找到第 k 个最小值来解决问题。假设快速排序中函数的签名partition是int partition(int* array, int start, int end)，这里是说明基本思想的伪代码：

int select(int[] a, int start, int end, int k)
{
    j = partition(a,start,end);

    if( k == j)
        return a[j];
    if( k < j )
        select(a,start,j-1,k);
    if( k > j )
        select(a,j+1,end,k-j);
}

index = select(a, 0, length_of_a, k);

那么 a[0...index] 是数组 a 中的前 k 个最小值。如果您希望对它们进行排序，您可以进一步对 a[0...index] 进行排序。