![]() |
|
Программирование >> Операторы преобразования типа
о Первые формы sort() и stable sort() сортируют все элементы интервала [beg,end) оператором <. О Вторые формы sort() и stable sort() сортируют все элементы интервала, используя в качестве критерия сортировки бинарный предикат op(elemi,elem2). О Предикат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на с. 303. О Отличие sort() от stable sort() заключается в том, что stable sort() сохраняет относительный порядок следования равных элементов. О Алгоритмы не могут использоваться со списками, потому что списки не поддерживают итераторы произвольного доступа. Впрочем, для сортировки элементов в списках определена специальная функция sort() (см. с. 252). О Алгоритм sort() гарантирует хорошее среднее быстродействие (nxlog(h)). Тем не менее если в вашей ситуации особенно важно избежать худших случаев, используйте алгоритм partial sort() или stable sort(). Сравнительный анализ алгоритмов сортировки приводится на с. 328. О Сложность; □ Sort() - в среднем nxlog(n) (примерно numberOfElementsx\og{numberOf-Elements) сравнений); □ Stable sort() - nxlog(n) при наличии дополнительной памяти (питЬег-OfElementsx\og(nu7nberOfElements)), xlog(n)xlog(n) в противном случае (numberOfElements:<\Qg(numberOfElementsy сравнений). Пример использования алгоритма sort(): algo/sortl.cpp #1nclude algostuff,hpp using namespace std; int mainO ( deque<int> coll: INSERT ELEMENTS(col1.1.9); INSERT ELEMENTS(coll.l.9): PRINT ELEMENTS(coll. on entry: ): Сортировка элементов sort (coll.beginO. coll.endO): PRINTJLEMENTS(col 1. sorted: ): Сортировка в обратном порядке sort (coll.beginO, coll.endO. Интервал greater<int>0): Критерий сортировки PRINT ELEMENTS(coll. sorted >; ): Результат выполнения программы выглядит так: on entry: 123456789123456789 sorted: 11223344556677В899 sorted >: 998877665544332211 Пример сортировки, при которой в критерии используются функции класса элементов, приведен на с. 133. Следующая программа демонстрирует различия между алгоритмами sortQ и stabie sort(). В ней оба алгоритма сортируют строки по количеству символов, используя критерий lessLength(): algo/sort2,cpp #include algostuff.hpp using namespace std: bool lessLength (const strings si. const strings s2) { return sl.lengthO < s2,length(); int mainO ( vector<string> colli: vector<string> coll2; Заполнение обеих коллекций одинаковыми элементами col col col col col col col col col col col col col col col col col col l.push back ( Ixxx ); l.push back ( 2x ) l.push back ( 3x ) l.push back ( 4x ) l.push back ( 5xx ): l.push back ( бхххх ); l.push back ( 7xx ); l.push back C 8xxx ): l.push back ( 9xx ); l.push back ( lOxxx ); l,push back ( 11 ) l.push back ( 12 ) l.push back ( 13 ) 14xx 15 ) l.push back l.push back l.push back ( 16 ) l.push back ( 17 ) 2 - colli: PRINT ELEMENTS(colll. on entry:\n ); Сортировка no длине строк sort (coin.beginO. colli,endO. Интервал lessLength); Критерий stable sort (со112.beginO, coll2.end(). Интервал lessLength); Критерий PRINT ELEMENTS(colll. \nwith sort():\n ); PRINTJLEMENTSCcol 12. Nnwith stable sort();\n O; Результат выполнения программы выглядит так: on entry: Ixxx 2x 3x 4x 5xx бхххх 7xx 8xxx 9xx lOxxx 11 12 13 14xx 15 16 17 with sortC): 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx Ixxx lOxxx бхххх with stable sort(): 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx Ixxx 8xxx 14xx бхххх IDxxx Только алгоритм stable sort() сохраняет относительный порядок следования элементов (начальные числа определяют порядок следования элементов в исходном состоянии коллекции). Частичная сортировка Простая частичная сортировка void partial sort (RandomAccessIterator beg. RandomAccessIterator sortEnd. RandotnAccessIterator end) void partial sort (RandomAccessIterator beg, RandomAccessIterator sortEnd. RandomAccessIterator end. BinaryPredicate op) О Первая форма сортирует элементы интервала [beg,end) оператором < так, чтобы интервал [begsortEnd) содержал упорядоченные элементы. О Вторая форма сортирует элементы по критерию op(elemi,elem2) так, чтобы интервал [beg,sortEnd) содержал упорядоченные элементы. О Предикат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на с. 303. О В отличие от sort() алгоритм partial sort() сортирует не все элементы интервала, а прекращает сортировку после того, как подинтервал от начала до sortEnd будет заполнен упорядоченными элементами. Например, если после сортировки интервала вам понадобятся только первые три элемента, этот алгоритм работает более эффективно, поскольку он не тратит время на сортировку остальных элементов.
|
© 2006 - 2025 pmbk.ru. Генерация страницы: 0
При копировании материалов приветствуются ссылки. |