C++ 的 sort 函数源码 |21xrx.com

C++ 的 sort 函数源码

2023-06-28 18:35:28 深夜i 13 0

C++ sort函数源码

C++的sort函数是一个十分常用的STL算法函数，它可以帮助程序员按照一定的规则对一个数组或容器内的元素进行排序。sort函数的底层实现是一个快速排序算法，而快速排序算法又是一个Divide-and-Conquer（分治）的算法。下面我们来一探sort函数的源码。

sort函数的C++源码位于头文件中，函数声明如下：

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

其中，第一个函数是默认排序规则的sort函数，它的参数first和last是排序的范围，它会根据范围内的元素类型进行排序；第二个函数是支持自定义排序规则的sort函数，它的参数first、last和comp三个参数，其中comp是用来比较两个元素的函数对象。

sort函数的主体代码采用了递归的方式实现快速排序，其中递归函数实现在sort函数内部：

template <class _RandomAccessIterator, class _Compare>
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
 _ValueType __val = _GLIBCXX_MOVE(*__last);
 auto __next = __last;
 --__next;
 while (__comp(__val, *__next))
 {
  *__last = _GLIBCXX_MOVE(*__next);
  __last = __next;
  --__next;
 }
 *__last = _GLIBCXX_MOVE(__val);
}
template <class _RandomAccessIterator, class _Compare>
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _Compare __comp)
{
 if (__first == __last)
 {
  return;
 }
 for (auto __i = __first + 1; __i != __last; ++__i)
 {
  if (__comp(*__i, *__first))
  {
   _ValueType __val = _GLIBCXX_MOVE(*__i);
   _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
   *__first = _GLIBCXX_MOVE(__val);
  }
  else
  {
   __unguarded_linear_insert(__i, __comp);
  }
 }
}
template <class _RandomAccessIterator, class _Compare>
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _Size __depth_limit, _Compare __comp)
{
 while (__last - __first > _S_threshold)
 {
  if (__depth_limit == 0)
  {
   __partial_sort(__first, __last, __last, __comp);
   return;
  }
  --__depth_limit;
  auto __cut = __unguarded_partition_pivot(__first, __last, __comp);
  __introsort_loop(__cut, __last, __depth_limit, __comp);
  __last = __cut;
 }
}
template <class _RandomAccessIterator, class _Compare>
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
              _Compare __comp)
{
 if (__last - __first > _S_threshold)
 {
  __insertion_sort(__first, __first + _S_threshold, __comp);
  __unguarded_insertion_sort(__first + _S_threshold, __last, __comp);
 }
 else
 {
  __insertion_sort(__first, __last, __comp);
 }
}
template <class _RandomAccessIterator, class _Compare>
void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      _Size __depth_limit, _Compare __comp)
{
 while (__last - __first > _S_threshold)
 {
  if (__depth_limit == 0)
  {
   __heap_sort(__first, __last, __comp);
   return;
  }
  --__depth_limit;
  auto __cut = __unguarded_partition_pivot(__first, __last, __comp);
  __sort(__cut, __last, __depth_limit, __comp);
  __last = __cut;
 }
 __final_insertion_sort(__first, __last, __comp);
}
template <class _RandomAccessIterator>
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
 if (__first != __last)
 {
  __sort(__first, __last, __lg(__last - __first) * 2, __gnu_cxx::__ops::__iter_less());
 }
}
template <class _RandomAccessIterator, class _Compare>
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
 if (__first != __last)
 {
  __sort(__first, __last, __lg(__last - __first) * 2, __gnu_cxx::__ops::__iter_comp_val(__comp));
 }
}

sort函数通过判断元素的数量和深度限制来确定用什么方式排序。当元素的个数超过了_S_threshold（= 16）并且深度限制还没有达到上限时，用快速排序递归调用sort函数。当元素的个数小于_S_threshold或深度限制达到上限时，采用插入排序或堆排进行排序。从代码中可以看出，sort函数实现了要求的功能，同时还保证了性能和效率。

上一篇: idea打包java可执行jar包

下一篇: C++如何限制输入数字位数？

评论区

相似文章