std::
sort
函数模板 <algorithm>| default (1) | template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); |
| custom (2) | template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
对范围内的元素进行排序
将[first,last)范围内的元素按升序排序。
第一个版本使用operator<比较元素，第二个版本使用comp比较元素。
等价元素不能保证保持它们原来的相对顺序(参见stable_sort)。
☲ 参数
- first, last
- 指向一个要排序的序列初始和最终位置的随机访问迭代器。使用的范围是[first,last)， 它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。 随机访问迭代器(RandomAccessIterator)应该指向一个正确定义了swap的类型， 并且该类型既可以移动构造，也可以移动赋值。
- comp
-
二元函数，接受范围内的两个元素作为参数，并返回可转换为bool的值。
返回的值表明，作为第一个参数传递的元素是否按照其定义的严格弱顺序先于第二个参数。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
none
☣ 示例
// sort algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::sort
#include <vector> // std::vector
bool myfunction (int i,int j) { return (i<j); }
struct myclass {
bool operator() (int i,int j) { return (i<j);}
} myobject;
int main () {
int myints[] = {32,71,12,45,26,80,53,33};
std::vector<int> myvector (myints, myints+8); // 32 71 12 45 26 80 53 33
// using default comparison (operator <):
std::sort (myvector.begin(), myvector.begin()+4); //(12 32 45 71)26 80 53 33
// using function as comp
std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)
// using object as comp
std::sort (myvector.begin(), myvector.end(), myobject); //(12 26 32 33 45 53 71 80)
// 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: 12 26 32 33 45 53 71 80
myvector contains: 12 26 32 33 45 53 71 80
✥ 复杂度
平均来说，first and last之间的距离的线性:执行大约N*log2(N)(其中N是这个距离) 比较元素，并直到元素交换(或移动)。
⇄ 数据竞争
范围[first,last)中的对象将被修改。
☂ 异常安全性
如果任何元素比较、元素交换(或移动)或迭代器上的操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| stable_sort | 对范围内的元素进行等价元素不变的排序(函数模板) |
| partial_sort | 对范围内的元素进行部分排序(函数模板) |
| search | 搜索范围的子序列(函数模板) |
| reverse | 反转元素(函数模板) |