如何获得列表中的前10个已排序项目，而不对整个列表进行排序

Question

问题是我有一个100万个数字的列表，但我只想要10个排序列表中的第一个，但我不想排序整个列表？那可能吗？

Answer 1

是的。您只需运行一次该列表，并存储十个最小的数字。该算法将是O（n）（实际上，O（n * 10）最差情况）

Foreach (list) 
- Check if current item is smaller than the biggest item in the sorted Array[10] 
- If so, put the current item at the right spot (sorted) in the array (insertionsort), bumping away the biggest item. 

Answer 2

你想要的是优先级队列。将每个号码插入优先队列。如果队列大小超过10，则删除最小（或最大）值。最后队列中剩余的值是10个最大（或最小）。

如果使用Heap实现队列，那么这可能是一个非常有效的算法。