partial_sort.md

#部分排序（std::partial_sort）

定义于头文件<algorithm>中：

template< typename RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );    (1)

template< typename RandomIt, typename Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );       (2)

重新排列区间[first, last)里的元素，区间[first, middle)指向排序后的middle-first`个元素。

不保证是否保持相等元素的先后顺序。区间[middle, last)的元素的顺序未知。版本(1)用<排序，即默认为升序，版本(2)用自定义的函数cmp。

##参数

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

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

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

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

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

类型约束

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

##返回值 无返回值。

##复杂度

约为(last-first)log(middle-first)次cmp函数调用。

##例子

#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

##另见

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