具有大量元素的数组只排序最大的n个元素

Question

我有一个包含大量元素的数组——超过2,000,000个。我需要获得排名最高(或最低)的300个元素。因此，每当我到达数组中第一个最高(或最低)300个元素时，就返回它们。目前数组。Sort用于整个数组，然后返回排名最高(或最低)的元素。

。: {1,2,3,4,5,6,7,8,9}我想获得最高的3个元素;我需要:{9,8,7}

这个有什么建议吗?

编辑

迄今为止找到的最佳资源，包含不同解决方案的研究/比较:

http://www.michaelpollmeier.com/selecting-top-k-items-from-a-list-efficiently-in-java-groovy/

文章的源代码:

https://github.com/mpollmeier/Selection-Algorithms

Answer 1

可以使用部分heapsort。构造一个有1st 300个元素的minheap

然后在进一步遍历数组时，检查当前元素是否大于堆的根元素。如果大于，则删除根元素并添加新元素。

在你完成整个数组之后，你的minHeap将拥有最大的300个元素。

逐个提取根元素。元素将按升序弹出。

注意:无论N的值是多少，堆总是包含k(300)个元素，所以在这种情况下堆操作应该是O(logk)。

因此该算法的复杂度阶为O(Nlogk)，其中N为数组的大小。

空间复杂度- O(k)

编辑:如果需要最小的300个元素，那么可以使用maxheap而不是minheap来遵循类似的算法。

Answer 2

这对你有用吗?下面的例子对数组中的前4个元素进行排序:

    double[] arr = new double[]{1.0,4.0,2.0,8.0,3.0,6.0,7.0,5.0};
    int nth = 4; //e.g. - sort the top 4 numbers
    Arrays.sort(arr,arr.length-nth-1,arr.length);
    System.out.println(Arrays.toString(arr));

输出:

[1.0, 4.0, 2.0, 3.0, 5.0, 6.0, 7.0, 8.0]

Answer 3

Use (T[]， int, int, java.util.Comparator)，这将在指定的范围内对给定数组(T[])进行排序，仅从第一个int arg到第二个int arg的元素。比较器是可选的。