Выполняет ли std:: sort внедрение Quicksort?

Ответ 1

Существует два алгоритма, которые традиционно используются.

std::sort, скорее всего, будет использовать QuickSort или, по крайней мере, вариант над QuickSort, называемый IntroSort, который "вырождается" на HeapSort, когда рекурсия идет слишком глубоко.

Из стандарта:

Сложность: O (N log (N)) сравнения.

std::stable_sort, скорее всего, будет использовать MergeSort из-за требования стабильности. Однако обратите внимание, что MergeSort требует дополнительного пространства, чтобы быть эффективным.

Из стандарта:

Сложность: выполняется не более N log ² (N) сравнений; если доступно достаточно дополнительной памяти, это N log (N).

Мне еще предстоит увидеть std::sort реализацию TimSort, который является многообещающим и был принят на Python (созданный для него на самом деле), Java и Android (на сегодняшний день).

Ответ 2

Это зависит от реализации библиотеки. Реализации слияния наиболее распространены, так как это худший случай O (N * logN), в то время как quicksort может деградировать до O (N ^ 2).

Это подтверждает это.

Кроме того, насколько мне известно, на входе используется какая-то эвристика, чтобы решить, какой алгоритм лучше всего использовать внутри, поэтому различные вызовы std::sort() могут использовать разные алгоритмы.

Ответ 3

Из Википедии -

Конкретный алгоритм сортировки не является обязательным и может варьироваться в разных реализациях. Сортировка Wiki Link

Ответ 4

Он использует quicksort или introsort.

http://www.sgi.com/tech/stl/sort.html

Ответ 5

Я так думаю. std:: list имеет метод сортировки, или вы можете вызвать сортировку, из которой берется 2 итератора, начинаются и заканчиваются.

Ответ 6

из-за высокой худшей сложности quicksort (N ^ 2) и относительно сложно реализовать в списке ссылок. Я думаю, что это не будет сделано с помощью quicksort