Алгоритм найти N ~ N + 100 самых больших элементов в массиве?

Question

Это относится к limit N,100 операторам SQL.

Сортировка всего массива - пустая трата времени, когда я просто хочу извлечь N~N+100 самые большие элементы.

Какой лучший алгоритм для такой ситуации?

Answer 1

Лучшее, на что вы можете надеяться в несортированном массиве, это O (n), так как все элементы должны быть проверены.При прохождении вы просто сохраняете текущие 100 лучших элементов в памяти, и если вы встретите элемент, который больше, чем самый низкий элемент в текущих 100, вы просто удалите его и добавите новый.Вы можете сохранить первые 100 элементов в памяти как отсортированную очередь.

Answer 2

Поиск дополнения STL std::partial_sort (C ++)

Answer 3

Полагаю, это будет зависеть от размера массива.

Для достаточно небольшого массива, как при сортировке выборки, просто переберите массив 100 раз, выберите максимальный элемент и удалите его.

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

Алгоритм быстрой сортировки может переключиться на алгоритм сортировки выбора, как только корзины станут достаточно маленькими.