如何使用快速排序查找K个最小值

问题很简单，如果我排序所有值并选择第一个K值。但是它浪费了太多时间，因为在整个数组排序之前可能已经对最小的K值进行了排序。我认为解决这个问题的方法是在代码中添加一个标志，但我无法弄清楚如何让标志判断最小的k值是否已经排序。如何使用快速排序查找K个最小值

来源

2012-12-05 Roger Zhu

您可以使用random selection algorithm以O（n）时间解决此问题。最后，只需返回从0到k的子数组。

来源

2012-12-05 05:32:12 bhuang3

是否意味着排序整个数组是必须的？ –

不，在随机选择算法中，它并没有对整个数组进行排序，最后只是在数组[K]左侧的K个最小值。所以你只需要返回从0到K的子数组。它只是使用快速排序的分区思路，但是具有非常出色的预期运行时间。 – bhuang3

我已经阅读了wiki，我知道解决这个问题的想法。 Thx寻求帮助 –

我认为这个问题可以通过找到第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);

然后，[0 ...指数]在阵列中的前k个最小的值。如果您想对它们进行排序，您可以进一步对[0 ...索引]进行排序。

来源

2012-12-05 05:31:18

如何使用快速排序查找K个最小值

回答

相关问题