C++ std::sort算法：不只是快速排序 #

回答重点

std::sort 非常高效，它不单纯是快速排序，而是使用了一种名为 introspective sort（内省排序）的算法。

内省排序是快速排序、堆排序和插入排序的结合体，它结合这些算法优点的同时避免它们的缺点，特别是快速排序在最坏情况下的性能下降问题。

注意：本文介绍，仅限于GCC的源码实现。

扩展知识 #

快速排序 #

内省排序首先使用快速排序算法。利用快速排序分而治之的特点，通过选取一个pivot元素，将数组分为两个子数组，一个包含小于pivot的元素，另一个包含大于pivot的元素，然后递归地对这两个子数组进行快速排序。快速排序在平均情况下非常高效，时间复杂度为 O(n log n)。

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Size, typename _Compare>
_GLIBCXX20_CONSTEXPR void
__introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
                 _Size __depth_limit, _Compare __comp)
{
  while (__last - __first > int(_S_threshold))
    {
      if (__depth_limit == 0)
        {
          std::__partial_sort(__first, __last, __last, __comp);
          return;
        }
      --__depth_limit;
      _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp);
      std::__introsort_loop(__cut, __last, __depth_limit, __comp);
      __last = __cut;
    }
}

// sort
template <typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR 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);
    }
}

内省排序 #

通过限制快速排序递归深度，避免其最坏情况的性能问题。递归深度的限制基于输入数组的大小，通常是对数组长度取对数然后乘以一个常数（在 GCC 实现中是 2 * log(len)）。如果排序过程中递归深度超过了这个限制，算法会切换到堆排序。

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Size, typename _Compare>
_GLIBCXX20_CONSTEXPR void
__introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
                 _Size __depth_limit, _Compare __comp)
{
  while (__last - __first > int(_S_threshold))
    {
      if (__depth_limit == 0)
        {
          std::__partial_sort(__first, __last, __last, __comp);
          return;
        }
      --__depth_limit;
      _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp);
      std::__introsort_loop(__cut, __last, __depth_limit, __comp);
      __last = __cut;
    }
}

// sort
template <typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR 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);
    }
}

堆排序 #

当快速排序的递归深度超过限制时，内省排序会切换到堆排序，保证最坏情况下的时间复杂度为 O(n log n)。堆排序不依赖于数据的初始排列，因此它的性能无论在最好、平均和最坏情况下都是稳定的。

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Size, typename _Compare>
_GLIBCXX20_CONSTEXPR void
__introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
                 _Size __depth_limit, _Compare __comp)
{
  while (__last - __first > int(_S_threshold))
    {
      if (__depth_limit == 0)
        {
          std::__partial_sort(__first, __last, __last, __comp);
          return;
        }
      --__depth_limit;
      _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp);
      std::__introsort_loop(__cut, __last, __depth_limit, __comp);
      __last = __cut;
    }
}

插入排序 #

最后，当数组的大小减小到一定程度时，内省排序会使用插入排序来处理小数组。插入排序在小数组上非常高效，尽管它的平均和最坏情况时间复杂度为 O(n^2)，但在数据量小的情况下，这种复杂度不是问题。此外，插入排序是稳定的，可以保持等值元素的相对顺序。

/// This is a helper function for the sort routine.
template <typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR void
__final_insertion_sort(_RandomAccessIterator __first,
                       _RandomAccessIterator __last, _Compare __comp)
{
  if (__last - __first > int(_S_threshold))
    {
      std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
                                      __comp);
    }
  else
    std::__insertion_sort(__first, __last, __comp);
}

总结 #

std::sort 采用了内省排序算法，它是：

快速排序的基础实现
堆排序作为最坏情况的保障
插入排序处理小规模数据
智能切换保证最优性能

这种混合策略使得 std::sort 在各种场景下都能保持良好的性能表现。