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

Question

谁能告诉我在 std::sort() 函数中实现了哪种类型的排序技术（冒泡、插入、选择、快速、合并、计数...） ><算法>头文件？

Answer 1

std::sort 的大多数实现都使用快速排序（或者通常是像 introsort 这样的混合算法，它结合了快速排序、堆排序和插入排序）。

标准唯一要求的是 std::sort 以某种方式根据指定的顺序对数据进行排序，复杂度约为 O(N log(N))；不保证稳定。从技术上讲，内推排序比快速排序更好地满足复杂性要求，因为快速排序的最坏情况时间是二次的。

Answer 2

C++ 标准 ISO/IEC 14882:2003

25.3.1.1排序

模板
   void sort(RandomAccessIterator 首先，RandomAccessIterator 最后);
模板<类RandomAccessIterator，类比较>
   void sort(RandomAccessIterator 首先，RandomAccessIterator 最后，
          比较比较）；

1 效果：对元素进行排序
范围[第一个，最后一个）。

2 复杂性：
大约 N log N（其中 N == 最后一个
- 第一）平均比较。

没有有关方法的信息，但复杂性始终为N log N。

Answer 3

MSVC2013 STL中使用了三种算法，参考std::sort源码。

它最有可能使用 QuickSort，或 QuickSort 的变体，称为 IntroSort。

如果递归太深，这里将使用HeapSort。

否则将使用InsertSort。

Answer 4

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

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

从技术上讲，introsort 比快速排序更能满足复杂性要求：这是因为堆排序在最坏情况下保证了 O(N log(N)) 复杂性，而快速排序在最坏情况下的时间是二次方。

然而，在一般情况下，堆排序比快速排序“慢”，因为堆排序执行C*N log(N)，而快速排序执行D*N log(n) > 性能，D 明显小于 C（数字 C 和 D 是常数）。换句话说，堆排序的每次比较开销高于快速排序。

为了获得两全其美的效果，introsort 从快速排序（一种递归算法）开始，但是当递归深度变得太高时（这意味着它会陷入退化最坏情况的行为），它会切换到堆排序。

另请参阅introsort 的 Wikipedia 条目 或 来自 David Musser 的原始论文，他专门为 STL 发明了 introsort。

Answer 5

GCC 9.2.0 libstdc++ 源确认 introsort

其他提到了 introsort，但这里有一些证据libstc++，这是大多数 Linux 发行版上的默认 C++ 实现。

libstdc++ 是 GCC 本身的一部分，因此我们将研究 GCC 源代码。

libstdc++- v3/include/std/algorithm 是主标头，包含：

#include <bits/stl_algobase.h>
#include <bits/stl_algo.h>

然后， bits/stl_algo.h 包含排序重载的定义，其中之一是：

  /**
   *  @brief Sort the elements of a sequence.
   *  @ingroup sorting_algorithms
   *  @param  __first   An iterator.
   *  @param  __last    Another iterator.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [__first,__last) in ascending order,
   *  such that for each iterator @e i in the range @p [__first,__last-1),  
   *  *(i+1)<*i is false.
   *
   *  The relative ordering of equivalent elements is not preserved, use
   *  @p stable_sort() if this is needed.
  */
  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive(__first, __last);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
    }

所以我们看到这只是对输入进行一系列健全性检查，然后调用 std::__sort ，即 在同一个文件中定义：

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
       _Compare __comp)
    {
      if (__first != __last)
    {
      std::__introsort_loop(__first, __last,
                std::__lg(__last - __first) * 2,
                __comp);
      std::__final_insertion_sort(__first, __last, __comp);
    }
    }

我们已经到达了一个标识符称为 std::__introsort_loop ，其余的实现位于同一个文件上，任何人仍然有疑问。

在 Ubuntu 18.04 中，也应该可以将 GDB 单步调试到 std::sort 中，而无需进行任何进一步的设置，如 std::set 中所述：STL集的底层数据结构是什么在 C++ 中？

C++17 并行排序

我们现在也有并行排序，因此也值得研究一下它是如何完成的：C++17 并行算法已经实现了吗？

正如上面的答案中提到的，实现依赖于外部库：英特尔线程构建模块：https://github.com/intel/tbb

Answer 6

您的意思是 std::sort 吗？如果是这样，就可以按照他们想要的任何方式实施。它可能是快速排序，但也可能是基数或其他东西。据我所知，只要它能在至少 O(n log n) 内生成一个排序列表，实现就可以了。

Answer 7

只是一些经验结果：

我使用 std::sort （VS2008 工具链）将使用 numpy 1.9.2 sort 的 python 脚本翻译为 C++。

当我使用 numpy.sort 参数 kind='mergesort' 时，我只能在 python 和 C++ 方面得到相同的精确结果。当 kind='quicksort' 或 kind='heapsort' 时，具有相同键的元素的相对顺序不同。所以我猜想至少对于VS2008 std::sort自带的STL版本来说是使用mergesort的。