C++中的sort()是否具有^ 2性能？

Question

在尝试估计程序的性能时,我总是将sort()函数视为性能最差的n ^ 2函数.但是,我遇到了一个维基百科页面:

排序(C++)

其中说明GNU C Library sort()首先使用一种名为Introsort的混合排序算法,然后进行插入排序.Introsort的相应页面声称该算法具有nlogn的最差情况.但是,由于我不熟悉这个算法,我仍然担心sort():

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

2)是否有任何其他实现可能导致sort()执行比这更差(或更好,这将是伟大的)？

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

谢谢!

Answer 1

使用quicksort和introsort(这是前者的变体,O(n log n)通过在最坏情况输入时切换到heapsort来保证性能)代替其他理论上更好的算法,例如mergesort,这是因为平均情况是相同的,并且常量要低得多(在常量中你可以包括它可以在适当位置排序的事实,因此没有重新分配和副本).而最糟糕的情况是坏的,但很容易改进.一般来说,假设性能sort是O( n log n ).

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