std::partial_sort

来自cppreference.com
< cpp‎ | algorithm

 
 
算法库
执行策略 (C++17)
不修改的序列操作
(C++11)
(C++11)
(C++11)
(C++17)
修改的序列操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
partial_sort
二分查找操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

重排
数值操作
C 库
 
定义于头文件 <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.
原文:
Sorts some of the elements in the range [first, last) in ascending order. The first middle - first of these elements are placed in the range [first, middle). The order of equal elements is not guaranteed to be preserved. The order of the remaining elements in the range [middle, last) is unspecified. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

目录

[编辑] 参数

first, last -
范围内的元素进行排序
原文:
the range of elements to sort
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。
comp - 比较函数对象(即满足比较 (Compare) 要求的对象),若首个参数小于第二个,则返回 ​true

比较函数的签名应等价于如下者:

 bool cmp(const Type1 &a, const Type2 &b);

签名不需要拥有 const & ,但函数对象必须不修改传递给它的对象。
类型 Type1Type2 必须使得 RandomIt 类型的对象能在解引用后隐式转换到这两个类型。 ​

类型要求
-
RandomIt 必须满足 ValueSwappable RandomAccessIterator 的要求。
-
解引用 RandomIt 结果的类型必须满足 MoveAssignable MoveConstructible 的要求。

[编辑] 返回值

(无)
原文:
(none)
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

[编辑] 复杂度

O(N·log2(N))N = std::distance(first, last)应用cmp。如果需要额外的内存是可用的,那么复杂O(N·log(N))
原文:
O(N·log2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(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

[编辑] 另请参阅

对区间内的元素进行复制并部分排序
(函数模板) [编辑]
将区间内的元素排序,同时保持相等的元素之间的顺序
(函数模板) [编辑]
将区间按升序排序
(函数模板) [编辑]