Question

C++ vector插入一个元素然后使用stl的sort排序效率如何

本来就是有序的，我想知道sort有优化这种情况么，这种情况下复杂度是n还是nlgn，还是直接退化成n^2

Answer 1

stl的sort一般来说是在各种情况下最优化的.从你这个情况的描述,stl的sort应该会默认为插入排序(insertion sort).如果你实在不放心可以自己写一个插入排序.这个复杂度最差情况应该只有O(n)当然最好情况也可以写成O(log n).

追问

我想知道这里面具体是怎么实现的，具体是什么复杂度

追答

比如向一个有序的vector里面push back一个int，并且通过sort把它安排到属于它的位置。
嗯，大致思路是这样的：如果你要一个数一个数从左到右或者从右到左和这个数去比的话那么这个程序的复杂程度是O（n）。
但是更快的一种方法是把这个数去和vector里面的中位数去比，然后再和剩下那些数的中位数去比，直到找到那个数的正确位置。这样每次可以排除一半的数。所以复杂度是O（log（n））
至于stl里面具体里面是怎么实现的问题呢。。。我能答的就是每个版本的这个写法都不一样。但是stl的sort可以保证在O（nlog（n））