在std :: sort()中使用哪种类型的排序？

Question

任何人都可以告诉我std::sort()在<algorithm>头文件中定义的函数中实现了哪种类型的排序技术(冒泡,插入,选择,快速,合并,计数......)？

Answer 1

大多数std::sort使用quicksort的实现,(或者通常是一种混合算法,如introsort,它结合了quicksort,heapsort和插入排序).

标准要求的唯一事情是以std::sort某种方式按照指定的顺序对数据进行排序,复杂度约为O(N log(N)); 它不能保证稳定.从技术上讲,introsort比quicksort更能满足复杂性要求,因为quicksort具有二次最坏情况时间.

Answer 2

C++标准ISO/IEC 14882:2003

25.3.1.1排序

template<class RandomAccessIterator>
   void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
   void sort(RandomAccessIterator first, RandomAccessIterator last,
          Compare comp);

1 效果:对范围[first,last]中的元素进行排序.

2 复杂性:大约N log N(其中N == last - first)平均值的比较.

没有关于方法的信息,但总是复杂N log N.

Answer 3

在MSVC2013 STL中有三种算法,参考源代码std::sort.

它最有可能使用QuickSort,或者QuickSort被称为变体IntroSort.

如果递归过深,HeapSort将在此处使用.

否则InsertSort将被使用.

Answer 4

可能所有std::sort使用introsort（又名introspection sort）的实现，这是一种结合了快速排序和堆排序的混合算法。实际上，introsort是在1997年特别发明的，目的是实现C ++ STL中的性能排序。

该标准唯一需要做的就是std::sort以某种方式按照指定的顺序对数据进行排序，复杂度为O（N log（N））；它不能保证稳定（std::stable_sort如果需要，可以使用单独的算法）。

从技术上讲，与快速排序相比，内部排序更好地满足了复杂性要求：这是因为堆排序在最坏的情况下保证了O（N log（N））复杂度，而快速排序在最坏的情况下具有二次排序时间。

但是，在一般情况下，从某种意义上说，堆排序比快速排序“慢”，这意味着堆排序执行C * N log（N），而快速排序具有D * N log（n）性能，其中D显着小于C（数字C和D是常数）。换句话说，堆排序的每个比较开销都比快速排序的开销高。

为了获得两全其美，内省排序从快速排序（一种递归算法）开始，但是当递归深度过高时（这意味着它进入了退化的最坏行为），它将切换到堆排序。

另请参见Wikipedia条目，以了解有关introsort的信息或David Musser 的原始论文，David Musser尤其为STL发明了introsort。