Я узнал о быстрой сортировке и о том, как ее можно реализовать как в рекурсивном, так и в итеративном методе.
В Итеративном методе:
- Нажмите диапазон (0... n) в стек
- Разделите данный массив с помощью сводной
- Поместите верхний элемент.
- Нажимаем разделы (диапазон индексов) на стек, если диапазон имеет более одного элемента
- Выполняйте вышеуказанные 3 шага, пока пустой стек не будет
И рекурсивная версия является нормальной, определенной в wiki.
Я узнал, что рекурсивные алгоритмы всегда медленнее, чем их итеративный аналог.
Итак, какой метод является предпочтительным с точки зрения временной сложности (память не является проблемой)?
Какой из них достаточно быстр, чтобы использовать в конкурсе программирования?
Является ли С++ STL sort() рекурсивным подходом?