C++中的sort()能有n^2的性能吗？

Question

在尝试评估程序的性能时，我总是将sort()函数视为性能最差的-n^2函数。然而，我偶然看到了维基百科的一个页面：

sort(C++)

它指出GNU C Library sort()首先使用某种称为Introsort的混合排序算法，然后执行插入排序。Introsort的对应页面声称该算法的最坏情况性能为nlogn。但是，由于我不熟悉这个算法，所以我仍然对sort()有以下担忧：

1) GNU sort()使用的混合算法能保证O(nlogn)的性能吗？如果是这样，nlogn的恒定开销能有多大？

2)有没有其他实现可能导致sort()的性能比这个更差(或者更好，这会更好)？

编辑:回复Kevin:提到的sort()是std::sort()。

谢谢!

Answer 1

使用快速排序和内部排序(这是前者的一种变体，通过在最坏的情况下切换到堆排序来保证O(n log n)性能)来代替其他理论上更好的算法，如合并排序，这是因为平均情况是相同的，常量要低得多(在常量中，您可以包括它可以被就地排序的事实，所以没有重新分配和副本)。最坏的情况是坏的，但可以改善。通常，假设sort的性能为O( n log n )。

如果您关心的是隐藏常量，那么这个问题不是理论上的，而是一个性能问题。在尝试优化时，最好在实际数据上测量算法，分析测量结果，然后确定时间花在哪里以及是否可以改进。但这是一个与理论完全不同的问题。

Answer 2

如果您的标准库没有提供超过14882的保证，那么对于sort()的最坏情况行为似乎没有正式的限制--只有平均复杂度被列出。标准中有一个脚注，其中提到如果你关心，你应该使用stable_sort()或partial_sort()而不是sort()：

http://www.kuzbass.ru:8086/docs/isocpp/lib-algorithms.html#lib.alg.sorting

25.3.1.1 -排序lib.sort

模板空排序( RandomAccessIterator first，RandomAccessIterator last) template空排序(RandomAccessIterator first，RandomAccessIterator last，Compare comp)

1. Effects:对范围[first，last)中的元素进行排序。

1. 复杂度:平均约为N log N(其中N ==倒数第一)比较。*

脚注:如果最坏的情况很重要，则应该使用stable_sort() (lib.stable.sort)或partial_sort() (lib.partial.sort)。-结束脚注

特定的库实现可能会在标准之外提供更强大的保证。而且，直接查看代码当然也很有用。再说一次，这取决于你想要的可移植性。

Answer 3

Introsort的最坏情况运行时间实际上是O(n log(n))，而不是O(n^2)。另请参阅SGI STL规范中的this remark：

早期版本的排序使用快速排序算法，使用由三个中位数选择的枢轴。快速排序算法的平均复杂度为O(N log(N))，而最坏情况下的复杂度为二次。然而，当前的排序实现使用的是最坏情况下复杂度为O(N log(N))的内排序算法。内部排序与三中位数快速排序非常相似，并且平均速度至少与快速排序一样快。