排序


类别：算法	组件类型：函数

原型

Sort是一个重载名称；实际上有两个排序函数。

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

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

描述

Sort将[first, last)中的元素排序为升序，这意味着如果i和j是[first, last)中任何两个有效的迭代器，使得i在j之前，则*j不小于*i。注意排序不保证是稳定的。也就是说，假设*i和*j是等价的：两者都不小于另一个。不保证这两个元素的相对顺序会被排序. [1]

的两个版本排序在如何定义一个元素是否小于另一个元素方面有所不同。第一个版本使用operator<比较对象，第二个版本使用函数对象comp.

定义

在标准头文件algorithm中定义，并在非标准向后兼容头文件algo.h中定义。

类型要求

对于第一个版本，即接受两个参数的版本

RandomAccessIterator是随机访问迭代器的模型。
RandomAccessIterator是可变的。
RandomAccessIterator的值类型是可小于比较。
上的排序关系RandomAccessIterator的值类型是严格弱排序，如可小于比较要求中所定义。

对于第二个版本，即接受三个参数的版本

RandomAccessIterator是随机访问迭代器的模型。
RandomAccessIterator是可变的。
StrictWeakOrdering是严格弱排序的模型。
RandomAccessIterator的值类型可转换为StrictWeakOrdering的参数类型。

先决条件

[first, last)是一个有效的范围。

复杂度

O(N log(N))比较（平均和最坏情况），其中N是last - first. [2]

示例

int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
sort(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is " 1 2 4 5 7 8".

注释

[1] 如果您正在对具有多个字段的记录进行排序，则稳定排序有时很重要：例如，您可能希望按姓氏，然后按名字对人员列表进行排序。算法stable_sort确实保证保留等价元素的相对顺序。

[2] 早期版本的排序使用快速排序算法（C. A. R. Hoare，Comp. J. 5，1962），使用由三个数的中位数选择的枢轴（R. C. Singleton，CACM 12，1969）。快速排序具有O(N log(N))平均复杂度，但最坏情况复杂度为二次方。有关讨论，请参见 Knuth 的第 5.2.2 节。（D. E. Knuth，计算机程序设计艺术。第 3 卷：排序和查找。Addison-Wesley，1975。）当前的实现排序但是，使用introsort算法（D. R. Musser，“内省排序和选择算法”，软件实践与经验 27(8):983, 1997。）其最坏情况复杂度为O(N log(N))。Introsort 与三数中位数快速排序非常相似，并且平均速度至少与快速排序一样快。

另请参阅

stable_sort, partial_sort, partial_sort_copy, sort_heap, is_sorted, binary_search, lower_bound, upper_bound, less<T>，严格弱排序，可小于比较