排序直到我们具有排序数组的最低一半

Question

我目前正在尝试获取数据数组最低一半的值.这个数组首先是未排序的.

由此:

{4,6,9,3,8,5}

对此:

{3,4,5,6,9,8} or {3,4,5}

一个简单的解决方案是对数组进行排序(使用快速排序),然后仅使用存储在排序数组的前半部分中的值.但是,由于快速排序和最有效的排序算法将对整个阵列进行排序,而我只需要前50%,这似乎浪费了资源.请注意,性能是此项目中的一个问题.

知道完全排序是O(n log n)并且在找到最低元素之后停止的排序是O(n),我可以轻松地构建一个复杂度为n/2*n的简单算法来查找最低的50%.但这真的比完全快速排序更好吗？

要清楚,如果我们只想要数组中最低一半的值,最好使用哪种方法？如果50%较小(如1%),那么对最低元素进行顺序搜索当然是最快的解决方案,但是它会比快速排序慢多少？

我使用C++编写代码并使用向量,但这个问题应该很普遍.

Answer 1

#include <algorithm>
std::partial_sort(start, middle, end);