Какая сортировка алгоритма используется списком STL:: вид ()?
Ctrl-1, чтобы преобразовать, если в условное выражение и назад, раздели присвоение или присоединитесь к нему назад или сделайте другие такие маленькие манипуляции. Существует список их в справке.
3 ответа
Стандарт не требует определенного алгоритма, только то, что он должен быть стабильным и чтобы он завершал сортировку, используя приблизительно N lg N сравнений. Это позволяет, например, выполнять быструю сортировку слиянием или связным списком (вопреки распространенному мнению, быстрая сортировка не обязательно нестабильна, даже несмотря на то, что наиболее распространенная реализация для массивов) .
С этой оговоркой, краткий ответ заключается в том, что в большинстве современных стандартных библиотек std :: sort реализован как вводная сортировка (интроспективная сортировка), которая по сути является быстрой сортировкой, отслеживающей его глубина рекурсии, и переключится на Heapsort (обычно более медленную, но гарантированную сложность O (n log n)), если Quicksort использует слишком глубокую рекурсию. Однако Introsort был изобретен относительно недавно (конец 1990-х). В старых стандартных библиотеках вместо этого обычно использовалась быстрая сортировка.
stable_sort существует, потому что для сортировки контейнеров, подобных массиву, большинство самых быстрых алгоритмов сортировки нестабильны, поэтому стандарт включает оба std :: sort ( быстро, но не обязательно стабильно) и std :: stable_sort (стабильно, но часто несколько медленнее).
Оба они, однако, обычно предполагают итераторы с произвольным доступом и будут работать плохо (если вообще будут) с чем-то вроде связного списка. Чтобы получить достойную производительность для связанных списков, стандарт включает list :: sort . Однако для связанного списка такого компромисса нет - довольно легко реализовать сортировку слиянием, которая будет стабильной и (примерно) так же быстро, как и все остальное. Как таковой,
Это полностью определено реализацией. Единственное, что об этом говорится в стандарте, это то, что его сложность составляет O (n lg n), и что сортировка стабильна . То есть, гарантируется, что относительный порядок равных элементов не изменится после сортировки.
Функция-член сортировки std :: list обычно реализуется с использованием некоторой формы сортировки слиянием, потому что сортировка слиянием стабильна, а слияния действительно очень дешево, когда вы работаете со связанными списками.
Надеюсь, что это поможет :)
Хотя это зависит от реализации / поставщика, но в большинстве известных мне реализаций используется Introsort, сложность которого в лучшем и худшем случае составляет O (nlogn).