Можна використовувати порядкову статистику.
Рекурсивно ділимо подмассів на дві частини. Беремо з подмассіва деякий опорний елемент (pivot), і ділимо подмассів на те, що більше опорного елемента, і менше. Якщо тих, які більше виявилося більше ніж потрібно, рекурсивно обробляємо праву частину, якщо менше - ліву, якщо скільки потрібно - відповідь знайдений.
Алгоритм ділення (partition) той же самий, що в швидкої сортування (quicksort) використовується, різниця в тому, що ділиться тільки одна гілка.
Краще і середній час - O (n), найгірше - O (n ^ 2),
Методи лікування ті ж, що і у quicksort - правильний вибір pivot. Можна вибирати випадково.
Дивіться також: k-я порядкова статистика, медіана.
Сам алгоритм називається quickselect.
відповідь дан 10 Листопада '16 в 9:54
У мене вийшло таке рішення:
Якщо вам потрібно отримати n максимальних чисел, то ми створюємо чергу. Потім проходимо по колекції, якщо розмір черги менші заданого числа, то просто додаємо туди поточний елемент. Інакше, порівнюємо з мінімальним елементом в черзі. Якщо поточний елемент більше, то видаляємо мінімальний і додаємо новий.
відповідь дан 10 Листопада '16 о 9:10
розібрався, ось, може кому і допоможе))
відповідь дан 24 Листопада '16 о 12:42
що повинен був робити прапор sorted? у нього завжди значення true, а й воно ніде не перевіряється - Grundy 24 Листопада '16 о 12:45
Краще використовуйте стандартну сортування, ніж свої милиці :) - gil9red 24 Листопада '16 о 12:58