algorithm - 如何在不对整个列表进行排序的情况下获取列表的前 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.