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