Как получить первые 10 отсортированных элементов списка без сортировки всего списка

Question

Проблема в том, что у меня есть список из 1 миллиона номеров, но я хочу только 10 первых в отсортированном списке, но я не хочу сортировать весь список? Это возможно?

Answer 1

То, что вы хотите, это приоритетная очередь. Вставьте каждый номер в приоритетную очередь. Если размер очереди превышает 10, удалите наименьшее (или наибольшее) значение. Значения, которые остаются в очереди в конце, являются 10 самыми большими (или самыми маленькими). ​​

Если очередь реализована с использованием кучи, то это может быть очень эффективным алгоритмом.

Answer 2

Да.Вы просто просматриваете список один раз и сохраняете десять самых маленьких чисел.Алгоритм будет 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.