Сортировка первых n целых чисел в линейном времени и постоянном пространстве

Question

Я ищу алгоритм, не основанный на сравнении или сравнении, который может сортировать массив, содержащий любую перестановку первых n натуральных чисел, которая должна быть O (n) сложность времени и O (1) сложность пространства.*

Существует ли существующий алгоритм, который соответствует этим спецификациям?

Answer 1

Если у вас есть массив размера N со всеми целыми числами от 1 до N, вы можете использовать следующий алгоритм O (N) (Примечание: массивы 1 основаны на этом псевдокоде, чтобы не вносить ненужную сложность в объяснении алгоритма):

1. Начать с первого элемента массива.
   
2. Если индекс массива соответствует его значению, переходите к следующему.
   
3. Если нет, поменяйте его на значение индекса индекса, соответствующее его значению.
   
4. Повторяйте шаг 3 до тех пор, пока не понадобятся перестановки.
   
5. Если не в конце массива, перейдите к следующему элементу массива, в противном случае перейдите к шагу 7
   
6. Перейти к шагу 2.
   
7. Готово

Answer 2

Безразличная сортировка MSD

Answer 3

Если вы уверены, что все целые числа находятся в диапазоне от 1 до N, вы можете использовать сортирующая сортировка