排序长度为n的无序阵列的T最小整数 [英] Sort the t smallest integers of an unsorted array of length n

问题描述

我试图找到最有效的方式，长度为n的无序阵列的T最小整数排序。

I am trying to find the most efficient way to sort the t smallest integers of an unsorted array of length n.

我想有O（n）的运行，但继续被卡住。

I am trying to have O(n) runtime but, keep getting stuck.

最好的，我能想到的只是排序整个数组，并采取第t。在其他情况下，我不停的按最小的是留下，如果我检查他们所有的话，它的排序整个数组的时间复杂度的机会。

The best I can think of is just sorting the entire array and taking the first t. In all other cases, I keep hitting the chance that the smallest is left behind, and if I check them all then, it has the same time complexity of sorting the entire array.

谁能给我一些想法？

推荐答案

运行像 quickselect 找到第t个元素，然后对数据进行分区，以提取吨最小元素。这可以在O（n）时间（一般情况下）来完成。

Run something like quickselect to find the t-th element and then partition the data to extract the t smallest elements. This can be done in O(n) time (average case).

Quickselect是：

Quickselect is:

这是算法上快速排序相似，这反复选取一个'枢轴'和根据该枢轴（离开枢轴在中间，与左边较小的元素，并在右边较大元件）将数据分区。然后将其递归到含有目标元素（它可以通过只计数元件的数目在任一侧容易地确定）的一侧。

An algorithm, similar on quicksort, which repeatedly picks a 'pivot' and partitions the data according to this pivot (leaving the pivot in the middle, with smaller elements on the left, and larger elements on the right). It then recurses to the side which contains the target element (which it can easily determined by just counting the number of elements on either side).

那么你仍然需要到T的元素，这是可以做到的，例如，快速排序或归并排序，使邻（T日志t）的运行时间。

Then you'll still need to sort the t elements, which can be done with, for example, quicksort or mergesort, giving a running time of O(t log t).

总运行时间为O（N + T日志T） - 你可能无法做到比这更好

The total running time will be O(n + t log t) - you probably can't do much better than that.

这篇关于排序长度为n的无序阵列的T最小整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！