std :: sort实现Quicksort吗？

Question

可能重复:
函数sort()中使用了哪种类型的排序？

std :: sort实现Quicksort吗？

Answer 1

传统上使用两种算法.

std::sort最有可能使用QuickSort,或者至少是一个名为IntroSort的QuickSort变体,当递归过深时,它会"退化"到HeapSort.

从标准:

复杂性:O(N log(N))比较.

std::stable_sort由于稳定性要求,最有可能使用MergeSort.但请注意,MergeSort需要额外的空间才能提高效率.

从标准:

复杂性:它最多进行N log ²(N)比较; 如果有足够的额外内存可用,则为N log(N).

我还没有看到一个std::sort实现的TimSort,它很有前途并且已经被Python(事实上为它制作),Java和Android(迄今为止)所采用.

Answer 2

我想是这样。std::list 有一个排序方法，或者您可以调用 sort 来获取 2 个迭代器（begin 和 end）。