I don't see another solution than sorting. However, if you have the freedom of organizing things in your own data structures and control the input array, you could do maybe this to save time:
- create an ordered list (or other ordered structure) in the size of 10 % of your original array. Provide methods to add elements into this ordered list. The other answer suggests B trees, which might also be used for this approach.
- when adding elements to the original array, also add the element to your ordered list
- the ordered list will always contain the top 10 percent.
The improvement over the approach of Aston is probably very small for large data sets, since the algorithm only increases my logarithmic scale. however, if your dataset is small there might be a real benefit of using only a 10 % size ordered data structure.
NOTE: If elements get removed from the original array, my approach might be less good than just using Aston suggestion from the start on, since a removal of an element might trigger a complete run over the list to fill the orderd structure again completely.