如何获取列表的前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个最大(或最小).

如果队列是使用堆实现的,那么这可能是一种非常有效的算法.