std::sort的底层是快速排序吗？可能远不止如此

C语言与CPP编程 · 发表于 4 天前

请介绍下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);}——EOF——你好，我是飞宇。日常分享C/C++、计算机学习经验、工作体会，欢迎点击此处查看我以前的学习笔记&经验&分享的资源。
我组建了一些社群一起交流，群里有大牛也有小白，如果你有意可以一起进群交流。

od4ehbbfuu564032156258.png

欢迎你添加我的微信，我拉你进技术交流群。此外，我也会经常在微信上分享一些计算机学习经验以及工作体验，还有一些内推机会。

2tcbqhvr1as64032156358.png

加个微信，打开另一扇窗
↓推荐关注↓
感谢你的分享，点赞，在看三连

jj2fggiqx5z64032156458.gif