partial_sort-c和c++中文资料站

C&C++标准库

std::

partial_sort

函数模板 <algorithm>

default (1)

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

custom (2)

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

对范围内的元素进行部分排序

重新排列[first,last)范围内的元素，middle 之前的元素以整个范围内最小的元素开始按升序排序，其余元素不按特定顺序排序。

第一个版本使用operator<比较元素，第二个版本使用comp比较元素。

☲ 参数

first, last: 指向一个进行部分排序序列初始和最终位置的随机访问迭代器。使用的范围是[first,last)，它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
middle: 指向[first,last)范围内的元素的随机访问迭代器，该迭代器用作排序的元素的上界。
comp: 二元函数，它接受范围中的两个元素作为参数，并返回可转换为bool的值。返回的值表明作为第一个参数传递的元素是否按照其定义的严格弱顺序先于第二个参数。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。

随机访问迭代器(RandomAccessIterator)应该指向一个正确定义了swap的类型，并且该类型既可以移动构造，也可以移动赋值。

☉ 返回值

none

☣ 示例

// partial_sort example
#include <iostream>     // std::cout
#include <algorithm>    // std::partial_sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {9,8,7,6,5,4,3,2,1};
  std::vector<int> myvector (myints, myints+9);

  // using default comparison (operator <):
  std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

输出:
myvector contains: 1 2 3 4 5 9 8 7 6

✥ 复杂度

平均来说，在 first and last之间的距离小于线性: 执行大约N*log(M)比较元素(其中N是整个距离，M是 first and middle之间的距离)。它还执行多个元素交换(或移动)。

⇄ 数据竞争

范围[first,last)中的对象将被修改。

☂ 异常安全性

如果任何元素比较、元素交换(或移动)或迭代器上的操作抛出。，则抛出。
注意，无效的参数会导致未定义的行为。

🍄 另请参阅

sort	对范围内的元素进行排序(函数模板)
stable_sort	对范围内的元素进行等价元素不变的排序(函数模板)
search	搜索范围的子序列(函数模板)
reverse	反转元素(函数模板)