sort（排序）

语法：

#include <algorithm>
 
template <class RandomAccessIterator>
void sort( RandomAccessIterator start, RandomAccessIterator end );
 
template <class RandomAccessIterator, class Compare>
void sort( RandomAccessIterator start, RandomAccessIterator end, Compare cmp );

排序 sort 算法将[start,end)范围内的元素排列成升序。如果两个元素相同，不能保证它们的顺序。

如果函数对象cmp被给定，那么它将取代<用来比较两个对象。cmp应该产生从start到end严格的弱顺序。

注意sort只对RandomAccessIterators操作。比如，你不能对 list使用sort；而应该使用 list::sort。

参数

start and end are RandomAccessIterators pointing to the range of elements to be sorted.

cmp is an optional function object that is used in place of < to perform comparisons between pairs of elements.

返回值

none

例子

下面的代码将一组整数向量排列成升序：

std::vector<int> v;
v.push_back( 23 );
v.push_back( -1 );
v.push_back( 9999 );
v.push_back( 0 );
v.push_back( 4 );
 
std::cout << "Before sorting: ";
for( unsigned int i = 0; i < v.size(); i++ ) {
  std::cout << v[i] << " ";
}
std::cout << std::endl;
 
std::sort( v.begin(), v.end() );
 
std::cout << "After sorting: ";
for( unsigned int i = 0; i < v.size(); i++ ) {
  std::cout << v[i] << " ";
}
std::cout << std::endl;

When run, the above code displays this output:

Before sorting: 23 -1 9999 0 4
After sorting: -1 0 4 23 9999

Alternatively, the following code uses the sort function to sort a normal array of integers, and displays the same output as the previous example:

const unsigned int array_size = 5;
int array[array_size] = { 23, -1, 9999, 0, 4 };
 
std::cout << "Before sorting: ";
for( unsigned int i = 0; i < array_size; i++ ) {
  std::cout << array[i] << " ";
}
std::cout << endl;
 
std::sort( array, array + array_size );
 
std::cout << "After sorting: ";
for( unsigned int i = 0; i < array_size; i++ ) {
  std::cout << array[i] << " ";
}
std::cout << std::endl;

This next example shows how to use sort with a user-specified comparison function. The function cmp is defined to do the opposite of the < operator. When sort is called with cmp used as the comparison function, the result is a list sorted in descending, rather than ascending, order:

bool cmp( int a, int b ) {
  return a > b;
}
 
...
 
std::vector<int> v;
for( int i = 0; i < 10; i++ ) {
  v.push_back(i);
}
 
std::cout << "Before: ";
for( int i = 0; i < 10; i++ ) {
  std::cout << v[i] << " ";
}
std::cout << endl;
 
std::sort( v.begin(), v.end(), cmp );
 
std::cout << "After: ";
for( int i = 0; i < 10; i++ ) {
  std::cout << v[i] << " ";
}
std::cout << std::endl;

复杂度

The algorithm behind sort is the introsort algorithm. sort runs in O(N log(N)) time (average and worst case) which is faster than polynomial time but slower than linear time.

另见

binary_search, merge, partial_sort, partial_sort_copy, stable_sort, c/other/qsort