考虑到与N号（N> 100）的阵列。为了我们怎样才能找到他们的最大的10％？ （如果n / 10不是一个整数，就可以舍它）

Given an array with 'N' numbers (N >100). How could we find the largest 10% of them in order ? (if n/10 is not an integer, we can round it)

我想出了3算法来尝试上述问题，但我不知道哪一个是最好的渐近运行时间方面。我其实可以做任何的修改，以减少渐近时间？此外，如果N变得非常大，它的算法可能仍然是有效的吗？

I came up with 3 algorithms to attempt the above problem, but I am not sure which one is the best in terms of asymptotic running time. Could I actually make any modification to reduce the asymptotic time? Also, if N gets really large, which algorithm might still be efficient one?

我列出我的想法，下面的算法和真的可以使用一些帮助找出最有效的算法这一点。

I'm listing my ideas for the algorithms below and could really use some help to figure out the most efficient algorithm for this.

ALGO-1

我使用的选择排序和停止它曾经数的10％，分选。

I used selection sort and stopped it once the 10% of numbers were sorted.

ALGO-2

我建了一个最大堆，并保持删除号码的最大10％

I built a max-heap and kept removing the largest 10% of numbers

ALGO-3

还没有实现这一个，但这个想法我已经是使用任何顺序统计算法找到包含数字的前10％的一个分区，然后使用合并排序排序。

Haven't implemented this one, but the idea I have is to use any order-statistic algorithm to find a partition containing the top 10% of numbers and then sort them using merge sort.

推荐答案

最快的解决办法是使用分区基于选择算法，它运行在 O（N）。它是基于快速排序的想法，只不过不是递归排序两个分区，你只去其中一个分区找到第k 最小元素。

The quickest solution is to use the partition-based selection algorithm, which runs in O(n). It's based of the quicksort idea, except instead of sorting both partitions recursively, you only go to one of the partitions to find the k-th smallest element.

查找最大的10％是通过搜索 K =（90％* N）个最小的数来完成的。

Finding the largest 10% is accomplished by searching for the k=(90%*N)-th smallest number.

如果你还记得如何分区的快速排序的工作原理，元素小于枢轴移动到左侧，其余元素所去的权利。比方说，你要选择的第k 最小元素。然后你看是否有至少 K 元素枢轴的左边。如果有，那么你知道你可以忽略正确的分区元素。否则，你可以忽略左分区中的所有元素，因为你知道该元素将是正确的分区。

If you recall how partitioning in quicksort works, elements less than the pivot is moved to the left, and the rest of the elements go to the right. Let's say you want to select the k-th smallest element. Then you see if there are at least k elements to the left of the pivot. If there are, then you know you can ignore the elements in the right partition. Otherwise, you can ignore all elements in the left partition, because you know that element will be in the right partition.

请注意，该选择算法只标识了那些排名前10％数字。如果你需要他们进行排序，那么你必须对这些数字进行排序（但只有那些数字，其余90％可以忽略不计）。

Note that the selection algorithm only identifies what those top 10% numbers are. If you need them to be sorted, then you have to sort those numbers (but only those numbers, the other 90% can be ignored).