Руководство по стандартной библиотеке шаблонов STL

Сортировка (Sort)


template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare соmр);

     sort сортирует элементы в диапазоне [first, last). Делается приблизительно NIogN (где N равняется last - first) сравнений в среднем. Если режим наихудшего случая важен, должны использоваться stable_sort или partial_sort.

template <class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

     stable_sort сортирует элементы в диапазоне [first, last). Он устойчив, то есть относительный порядок равных элементов сохраняется. Делается максимум N(logN)2 (гдеN равняется last - first) сравнений; если доступна достаточная дополнительная память, тогда зто - NlogN.

template <class RandomAccessIterator> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

     partial_sort помещает первые middle - first сортированных элементов из диапазона [first, last) в диапазон [first, middle). Остальная часть элементов в диапазоне [middle, last) помещена в неопределённом порядке. Берётся приблизительно (last - first) * log(middle - first) сравнений.

template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template <class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

     partial_sort_copy помещает первые min(last - first, result_last - result_first) сортированных элементов в диапазон [result_first, result_first + min(last - first, result_last - result_first)). Возвращается или result_last, или result_first +(last - first), какой меньше. Берётся приблизительно (last - first) * log(min(last - first, result_last - result_first)) сравнений.



Содержание раздела