Алгоритм сортировки на месте для k наименьших целых чисел в массиве из n различных целых чисел

Question

Существует ли алгоритм на месте, чтобы расположить k наименьших целых чисел в массиве из n различных целых чисел с 1 <= k <= n? </p>

Я полагаю, что сортировка подсчета может быть изменена для этого, но я не могу понять, как? Любая помощь будет оценена.

Answer 1

Вы хотите разделить массив так, чтобы k наименьших элементов были первыми k элементами (не обязательно отсортированный порядок)?Если это так, то вы ищете обобщенный алгоритм поиска медианы, который работает в O (n) (просто Google для алгоритма поиска медианы).

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

Answer 2

Как насчет выбора сортировки ? Он работает на месте в О (п ^ 2). Просто остановитесь после того, как вы нашли k самых маленьких элементов.

Answer 3

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

Answer 4

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