这是一道作业问题，因此我希望避免完整的答案，如果可能的话，更喜欢提示。
给定一个随机整数数组A[1...x]，程序应该返回前y个以增量顺序排列的数组元素，其中1<=y<=sqrt(x)。所以，基本上，给定一个数组[5,9,2,8]和y=2，程序应该返回[2,5]。
“首先排序，返回前y项”的答案已经行不通了，因为我们最好的做法是使用归并或快速排序的n*logn时间。因此，答案必须利用我们最多只返回sqrt(x)项的事实，目前唯一的其他答案是在数组中进行for循环搜索，找到最小元素，从数组中删除最小值，在一个新数组B中存储它，然后在长度为x-1的现在较小的修改版本的A上重复这个过程，这给我们运行时间如下:
x + (x-1) + (x-2) + ... + (x-y)
这个方法可以在最坏情况下迭代不超过y或sqrt(x)次，其中x是数组中的项目数。因此，我们有sqrt(x)*x，在比O(n*logn)更好但仍不够O(n)的时间复杂度范围内。
提示：假设您有一个O(n)时间复杂度的算法来选择第y个元素...
sqr(sqrt(n)) == n - ruslik其中1≤y≤sqrt(x)
注意这个要求给你什么。如果y ≤ √x，则y log y ≤ (√x log x) / 2 ∈ O(x½ log x) ⊂ O(x)。
先排序再过滤可能不适用，但过滤后再排序是可以接受的。
对于y，使用快速排序的思想，选择一个随机数并将其分成两部分。
Part1（较小）和part2（较大）。
如果Part1的长度<y，则在Part2中进行分区，其中y' = y - len(Part1)
如果Part1的长度>y，则在Part1中进行分区，其中y' = y
如果Part1的长度==y，则对Part1进行排序。
对于分区，平均时间应该几乎为O(n)（我现在无法批准，但它非常快）（我将尝试找到一些关于这部分的材料）。
对于y的排序需要ylog(y)<sqrt(x)log(sqrt(x)) -> 1/2 * sqrt(x) * log(x) < 1/2 * sqrt(x) * sqrt(x) => 1/2 x。
您只是想要一个提示，对吗？
仔细阅读random_hacker的评论，以防错过他所提供的重大提示。有一种算法可以对数组进行排序，做出微小微小的改变即可得到您的算法。
一般来说，如果y没有限制为sqrt（x），则您将得到一种算法，该算法在O（x + y * log x）中运行，如果y = O（x / log x），这是O（x）的情况，当y <= sqrt（x）时，当然也是如此。
quickselect，平均时间复杂度为O(n)，最坏情况下为O(n^2)。如果需要O(N)级别的难度，您需要根据自己的条件调整中位数算法（例如，选择50%的项目，找到中位数，然后对列表进行分区）。 - Dima Tisneky << x（在渐进的x中很典型），则将列表通过最小堆进行漏斗处理，结果将为O(x * log y)，这仍然是技术上的O(n log n)。但它非常实用，例如内存要求比其他方法小。 - Dima Tisnek