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

本文介绍了如何使用快速排序找到K个最小值的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

The problem is simple if I sort all the values and pick the fist K values. But it wastes too much time because maybe the smallest K values has been sorted before the whole array is sorted. I think the way to solve this problem is to add a flag in the code, but I can not figure out how to put the flag to judge whether the smallest k values has been sort.

推荐答案

您可以使用随机选择算法用O（n）时间解决这个问题。最后，只需将子数组从0返回到k。

You can use random selection algorithm to solve this problem with O(n) time. In the end, just return sub-array from 0 to k.