partial_sort_copy.md

#部分排序（std::partial_sort）

定义于头文件<algorithm>中：

template< typename InputIt, typename RandomIt >
RandomIt partial_sort_copy( InputIt first, InputIt last, RandomIt d_first, RandomIt d_last );    (1)

template< typename InputIt, typename RandomIt, Compare comp>
RandomIt partial_sort_copy(InputIt first, InputIt last, RandomIt d_first, RandomIt d_last, Compare comp );       (2)

升序排列区间[first, last)里的元素，结果保存于区间[d_first, d_last)。

最多d_last - d_first个元素移至区间[d_first, d_first + n)，然后开始排序，其中n为带排序元素个数，n = min(last - first, d_last - d_first))。不保证是否保持相等元素的先后顺序。区间[middle, last)的元素的顺序未知。版本(1)用<排序，即默认为升序，版本(2)用自定义的函数cmp。

##参数

first, last —— 待排序的元素的区间

comp —— 比较函数，若第一个参数小于第二个则返回true。 比较函数必须使用下面的等效声明：

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

比较函数不一定非得声明为const &，但是这个函数对象应该不能修改传递过来的参数。

类型Type1和Type2必须是能够解除引用操作和隐式互转的RandomIt类型。

类型约束

• InputIt 必须满足输入迭代器（InputIterator）。
• RandomIt必须满足值可交换和随机访问迭代器的要求。
• 解除引用的RandomIt类型必须满足可移动和可移动构造。

##返回值 指向已排序元素区间的上界的迭代器。

##复杂度

O(N*log(min(D,N)),其中N = std::distance(first, last), D = std::distance(d_first, d_last)次cmp函数调用。

##例子

下面是对整型vector排序，然后把它们复制到一个比它小和比它大的vector中的例子。

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
 
int main()
{
    std::vector<int> v0{4, 2, 5, 1, 3};
    std::vector<int> v1{10, 11, 12};
    std::vector<int> v2{10, 11, 12, 13, 14, 15, 16};
    std::vector<int>::iterator it;
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
 
    std::cout << "Writing to the smaller vector in ascending order gives: ";
    for (int a : v1) {
        std::cout << a << " ";
    }
    std::cout << '\n';
    if(it == v1.end())
        std::cout << "The return value is the end iterator\n";
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(), 
                                std::greater<int>());
 
    std::cout << "Writing to the larger vector in descending order gives: ";
    for (int a : v2) {
        std::cout << a << " ";
    }
    std::cout << '\n' << "The return value is the iterator to " << *it << '\n';
}

输出为：

Writing to the smaller vector in ascending order gives: 1 2 3
The return value is the end iterator
Writing to the larger vector in descending order gives: 5 4 3 2 1 15 16
The return value is the iterator to 15

##另见

• partial_sort_copy 按一定顺序排出区间里的前N个元素（函数模板）
• sort 递增排序，且不一定会保持相等元素的先后次序（函数模板）
• stable_sort 对区间的元素进行排序，同时保持相等元素的先后顺序（函数模板）