Быстрая сортировка, как и другие алгоритмы сортировки, фокусируется на упорядочении входных элементов в порядке, установленном данным оператором сравнения, но то, что отличает его от других алгоритмов сортировки, заключается не только в разделении и Покоритестратегию, но сама идея вращаться вокруг точки разворота весьма интригует.
Временная сложность и пространственная сложность этого алгоритма составляют O(nlogn) и O(n) соответственно, но пространственная сложность может быть улучшена до O(logn) с помощью простой хвостовой рекурсии.
Эта статья посвящена оптимизацииалгоритма быстрой сортировки, но чтобы узнать больше о быстрой сортировке, нажмите здесь.
Техника:
Чтобы оптимизировать быструю сортировку, чтобы использовать меньше памяти, метод довольно прост.
ИСПОЛЬЗОВАТЬ ХВОСТ РЕКУРСИИ !!
Обычно хвостовая рекурсия не предпочтительна, но в этом случае хвостовая рекурсия сочетается с идеей решения наименьшего раздела в первую очередь, что значительно улучшает пространственную сложность до O (logn) из O(n).
Оптимизированная функция быстрой сортировки
Приведенный выше код быстрой сортировки принимает следующие три аргумента:
i: данные: входная последовательность Int.
ii: start: начальный индекс данной входной последовательности.
iii: end: конечный индекс данной входной последовательности.
Быстрая сортировка обычно реализуется с использованием рекурсии, поэтому основное базовое условие остается неизменным, а именно:
Если начальный индекс больше или равен последнему индексу, то рекурсия завершится и вызов функции будет удален из стека.
Но вводится цикл while, который неоднократно вызывает функцию разделения и рекурсивно вызывает функцию быстрой сортировки, которая имеет наименьший раздел, пока все разделы не будут отсортированы.
Поскольку наименьший раздел всегда сортируется первым, дополнительная память ограничена O(logn).
Java-код
Нажмите, чтобы перейти к исходному коду
