Какой алгоритм сортировки является наилучшим с точки зрения сложности пространства - Быстрая сортировка или Вставная сортировка?

Question

Я знаю, что временная сложность быстрой сортировки меньше, чем сортировка вставкой.

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

Answer 1

Сортировка вставкой - это алгоритм сортировки на месте, то есть вспомогательных структур данных нет, алгоритм выполняет только перестановки во входном массиве. Таким образом, сложность пространства равна O (1). При вставке в пространстве сортировка лучше.

Answer 2

Быстрая сортировка и сортировка вставкой - это на месте и алгоритмы сортировки на основе сравнения.

Ни один из двух приведенных выше алгоритмов сортировки не требует от вас дополнительного местано сложность пространства Сортировка вставки равна O (1) , поскольку при замене используется несколько временных переменных.

Но сложность пространства Быстрая сортировка равно O (log (n)) , это потому, что после разбиения раздел с наименьшим количеством элементов (рекурсивно) сортируется первым, требуя не более O (log (n)) пространства. А другой раздел отсортирован с помощью tail-recursion , который не добавляет к стеку вызовов. Это позволяет сохранить глубину стека, ограниченную O (log (n)).