cpp/algorithm/partial sort — различия между версиями

Материал из cppreference.com

Текущая версия на 05:00, 23 марта 2016

Эта страница была переведена автоматически с английской версии вики используя Переводчик Google. Перевод может содержать ошибки и странные формулировки.

Наведите курсор на текст, чтобы увидеть оригинал. Щёлкните здесь, чтобы увидеть английскую версию этой страницы.

(Вы можете помочь в исправлении ошибок и улучшении перевода. Для инструкций перейдите по ссылке.)

Определено в заголовочном файле `<algorithm>`
template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last );	(1)
template< class RandomIt, class Compare > void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );	(2)

Сортирует часть элементов в диапазоне [first, last) в порядке возрастания. Первые middle - first отсортированные элементы находятся в диапазоне [first, middle). Не гарантируется сохранение порядка равных элементов. Порядок элементов в диапазоне [middle, last) не определен. Первый вариант использует operator< для сравнения элементов, вторая версия использует переданную функцию сравнения comp.

[править] Параметры

first, last	—	диапазон элементов для сортировки Оригинал: the range of elements to sort Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
comp	—	объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает true, если первый аргумент "меньше", чем второй. Определение сравнения должно быть эквивалентно: bool cmp(const Type1 &a, const Type2 &b); Использование noexcept (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по const&, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже const) `Type1` и `Type2` независимо от категории значений (таким образом, Type1& не допускается, равно как и Type1, если только для `Type1` перемещение не эквивалентно копированию (начиная с C++11)). Типы Type1 и Type2 должны быть таковы, что объект типа RandomIt может быть разыменован и затем неявно преобразован в оба из них.
Требования к типам
- `RandomIt` должен соответствовать требованиям `ValueSwappable` и `RandomAccessIterator`.
- The type of dereferenced `RandomIt` must meet the requirements of `MoveAssignable` and `MoveConstructible`.

[править] Возвращаемое значение

(Нет)

[править] Сложность

O(N\cdotlog 2 (N))

, где N = std::distance(first, last) применения cmp. Если дополнительная память недоступна, то сложность

O(N\cdotlog(N))

[править] Пример

Запустить этот код

#include <algorithm>
#include <functional>
#include <array>
#include <iostream>
 
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
 
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    for (int a : s) {
        std::cout << a << " ";
    }
}

Вывод:

0 1 2 7 8 6 5 9 4 3

[править] См. также

partial_sort_copy	копирует и частично сортирует диапазон элементов (шаблон функции) [править]
stable_sort	сортирует диапазон элементов, сохраняя порядок между равными элементами (шаблон функции) [править]
sort	сортирует диапазон в порядке возрастания (шаблон функции) [править]

Источник — «https://ru.cppreference.com/mwiki/index.php?title=cpp/algorithm/partial_sort&oldid=41892»

@@ Строка 1: / Строка 1: @@
-{{title|partial_sort}}
+{{
-Синтаксис:
+title|partial_sort}}
-<syntaxhighlight lang="cpp">
+, middle , )middle, )<
-    #include <algorithm>
-    void partial_sort( random_access_iterator start, random_access_iterator middle, random_access_iterator end );
-    void partial_sort( random_access_iterator start, random_access_iterator middle, random_access_iterator end, StrictWeakOrdering cmp );
-</syntaxhighlight>
-Функция partial_sort() сортирует по возрастанию первые N элементов диапазона [start,end). N определено количеством элементов между итераторами start и middle.
+элементов
+end
-По умолчанию для сравнения двух элементов используется оператор <. Если нужна высокая точность, можно задать упорядочивающую функцию сравнения, используемую вместо <.
-Смотрите также: [[cpp/algorithm/binary_search | binary_search]], [[cpp/algorithm/is_sorted | is_sorted]], [[cpp/algorithm/nth_element | nth_element]], [[cpp/algorithm/partial_sort_copy | partial_sort_copy]], [[cpp/algorithm/sort | sort]], [[cpp/algorithm/stable_sort | stable_sort]]
+также
+:
+[[cpp/algorithm/]]
+[[cpp/algorithm/]]
+[[cpp/algorithm/]]
+[[cpp/algorithm/]]
+[[cpp/algorithm/sort
+sort]]
+[[cpp/algorithm/]]

Поддержка компилятором
Автономные и размещённые реализации
Язык
Стандартная библиотека
Заголовки стандартной библиотеки
Требования к именованию
Макросы тестирования функциональности (C++20)
Поддержка языка
Библиотека концептов (C++20)
Библиотека метапрограммирования (C++11)
Библиотека диагностики
Библиотека общих утилит
Библиотека строк
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека численных данных
Библиотека ввода/вывода
Библиотека локализаций
Регулярные выражения (C++11)
Атомарные операции (C++11)
Библиотека поддержки конкуренции (C++11)
Библиотека файловой системы (C++17)
Технические спецификации
Указатель символов
Внешние библиотеки

cppreference.com

Пространства имён

Варианты

Просмотры

Действия