stable_sort


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

原型

Stable_sort是一个重载名称; 实际上有两个stable_sort函数。

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

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

描述

Stable_sort很像sort: 它对[first, last)中的元素进行升序排序，意味着如果i和j是[first, last)中的任何两个有效迭代器，使得i在j之前，那么*j不小于*i. Stable_sort与sort有两个不同之处。首先，stable_sort使用与sort不同的运行时复杂度的算法。其次，顾名思义，stable_sort是稳定的: 它保留了等价元素的相对顺序。也就是说，如果x和y是[first, last)中的任何两个有效迭代器，使得x在y中的元素，并且如果这两个元素是等价的（既不是x < y也不是y < x），那么stable_sort的后置条件是x仍然在y. [1]

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

定义

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

类型要求

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

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

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

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

前提条件

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

复杂度

Stable_sort是一个自适应算法: 它尝试分配一个临时内存缓冲区，其运行时复杂度取决于可用内存量。最坏情况行为（如果不可用辅助内存）是N (log N)^2比较，其中N是last - first，最佳情况（如果可用足够大的辅助内存缓冲区）是N (log N). [2]

例子

对字符序列进行排序，忽略其大小写。注意，仅大小写不同的字符的相对顺序将被保留。

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }

int main()
{
  char A[] = "fdBeACFDbEac";
  const int N = sizeof(A) - 1;
  stable_sort(A, A+N, lt_nocase);
  printf("%s\n", A);
  // The printed result is ""AaBbCcdDeEfF".
}

注意事项

[1] 注意，两个元素可能在不等价的情况下等价。一个标准的例子是对按姓氏排序的姓名序列进行排序: 如果两个人有相同的姓氏，但不同的名字，那么他们就是等价的，但并不相等。这就是为什么stable_sort有时很有用: 如果你要对具有多个不同字段的记录序列进行排序，那么你可能希望按一个字段对它进行排序，而不会完全破坏你之前从按另一个字段对它进行排序获得的排序。例如，你可以按名字排序，然后按姓氏进行稳定排序。

[2] Stable_sort使用归并排序算法; 参见 Knuth 的第 5.2.4 节。（D. E. Knuth，计算机程序设计艺术。第 3 卷: 排序和查找。Addison-Wesley，1975。）

另请参阅

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