Есть ли алгоритм сортировки массива чисел с плавающей точкой за один цикл?
Если вы имеете в виду один проход, то нет. Сортировка обычно требует либо O (N log N). Один проход подразумевает O (N).
Радикальная сортировка занимает O (N * k) со средней длиной ключа k. Хотя это линейное время, оно требует нескольких проходов. Он также обычно не подходит для сортировки поплавков.
Возьмите ноутбук с программой быстрой сортировки.Затем положите ноутбук на одноколесном велосипеде.Тада!Сортировка за один цикл.
проверка Подсчет сортировки выполняется за время O (N + M), где N - размер входного массива, а M - размер массива сортировки
Нет, нет алгоритма с O (n). Возможно, используется столько параллельных компьютеров, сколько элементов в вашем массиве, либо квантовые компьютеры, но если вы хотите, чтобы O (n) теперь использовалось на обычном компьютере, вы можете забыть об этом.
Есть несколько алгоритмов сортировки, которые в лучшем случае являются O (n).Смотрите здесь .
Алгоритм сортировки «за один цикл» - я полагаю, вы имеете в виду алгоритм с линейной сложностью.В дополнение к этим ответам вы также можете проверить Алгоритм сортировки ведра .Имеет среднюю производительность O (n + k).
номер
<aside> @ codinghorror: почему в моем сообщении должно быть> = 15 символов? </aside>
<aside>
</aside>