тому в итоге может быть получе

Автор admin Вторник, 26 мая 2009 11:32

тому в итоге может быть получен интервал вида {a(2),a(l),b(l),b(2),c(2),c(l)}. С другой стороны, при устойчивой сортировке вы получите {a(l),a(2),b(l),b(2),c(l),c(2)}. Алгоритм STL sort() использует разновидность алгоритма быстрой сортировки и поэтому является неустойчивым, однако в библиотеку также входит устойчивый алгоритм stable_sort()1. В алгоритме stable_sort() применяется сортировка со слиянием, которая действительно сохраняет исходный порядок следования элементов, но в среднем работает несколько медленнее алгоритма быстрой сортировки. 286 Глава б • Обобщенные алгоритмы Чтобы продемонстрировать устойчивую и неустойчивую сортировку алгоритмов, изменяющих порядок элементов последовательности, мы должны как-то отслеживать исходный порядок элементов. Приведенная ниже разновидность объекта string запоминает исходную относительную позицию данного объекта при помощи статической карты, связывающей строки с числовыми индексами. В каждом объекте NString присутствует поле thisOccurrence, обозначающее номер вхождения данного объекта. //: C06:NString.h // “Нумерованная строка”, отслеживающая номер вхождения