STL中最常用的函数之一,排序的神器。

sort

function sort.cpp
1
2
3
4
5
6
<algorithm>
template <class RandomAccessIterator>
  void sort ( RandomAccessIterator first, RandomAccessIterator last );

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

function

Sort elements in range Sorts the elements in the range first,last) into ascending order.

The elements are compared using operator< for the first version, and comp for the second.

Elements that would compare equal to each other are not guaranteed to keep their original relative order.

Parameters

first, last Random-Access iterators to the initial and final positions of the sequence to be sorted. The range used is first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. comp Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return value

none

Example

example.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// sort algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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};
  vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
  vector<int>::iterator it;

  // using default comparison (operator <):
  sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}

Output:

myvector contains: 12 26 32 33 45 53 71 80

Complexity

Approximately NlogN comparisons on average (where N is last-first). In the worst case, up to N2, depending on specific sorting algorithm used by library implementation.