Шаг 261.
Библиотека STL.
Алгоритмы STL. Алгоритмы сортировки (окончание)

    На этом шаге мы закончим сравнение алгоритмов сортировки.

    Помимо перечисленных на предыдущем шаге существуют и другие алгоритмы сортировки элементов. Например, алгоритмы сортировки в куче вызывают функции, непосредственно работающие с кучей (то есть с бинарным деревом, используемым в реализации этих алгоритмов). Алгоритмы сортировки в куче заложены в основу эффективной реализации приоритетных очередей. Вызовы этих алгоритмов, сортирующие все элементы коллекции, выглядят так:

// Сортировка всех элементов
// - сложность n+n*log(n)
make_heap (coll.begin(), coll.end()); 
sort_heap (coll.begin(), coll.end());

    Алгоритмы nth_element() существуют на тот случай, если вам нужен только n-й упорядоченный элемент или подмножество из n старших или младших элементов (неупорядоченное). Алгоритм nth_element() разделяет элементы на два подмножества в соответствии с критерием сортировки. Впрочем, задача также может быть решена алгоритмами partition() и stable_partition(). Различия между этими алгоритмами заключаются в следующем.

    Любому алгоритму сортировки в необязательном аргументе всегда можно передавать критерий сортировки. По умолчанию критерием сортировки является объект функции less<>, а элементы сортируются по возрастанию значений.

    Как и в случае с модифицирующими алгоритмами, приемником алгоритмов сортировки не может быть ассоциативный контейнер, поскольку элементы ассоциативного контейнера считаются константными.

    Кроме того, алгоритмы сортировки не могут вызываться для списков, поскольку списки не поддерживают итераторы произвольного доступа. Впрочем, для сортировки элементов в списках определена функция sort() (смотри 204 шаг).

    На следующем шаге мы рассмотрим алгоритмы упорядоченных интервалов.




Предыдущий шаг Содержание Следующий шаг