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

C++ sort()函数的源码

2023-07-02 14:01:59 深夜i -- --

C++ sort() 源码

C++ sort()函数是一种非常常用的排序算法，它能够对 C++ 中的数组进行排序，其源码如下：


template<class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
  __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
  __final_insertion_sort(first, last, value_type(first));
}

其中，__introsort_loop()和__final_insertion_sort()是 sort() 的两个主要子函数，它们负责实际的排序过程。介绍这两个函数之前，我们先来看看 sort() 函数中的各个参数：

- RandomAccessIterator：表示排序数组中元素的指针类型，通常为迭代器类型；

- first：表示要排序的数组的开始位置；

- last：表示要排序的数组的结束位置。

接下来，我们来看看这两个子函数的源码。

1. __introsort_loop()


template<class RandomAccessIterator, class Size, class T>
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, Size depth_limit, T*) {
  while (last - first > __STL_INTROSORT_THRESHOLD) {
    if (depth_limit == 0) {
      __partial_sort(first, last, last);
      return;
    }
    --depth_limit;
    RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first) / 2), *(last - 1))));
    __introsort_loop(cut, last, depth_limit, (T*) nullptr);
    last = cut;
  }
}

__introsort_loop() 采用一种自适应的排序算法，通过分解问题来排序整个序列。具体来说，__introsort_loop() 的基本思想是使用快速排序来排序数组，不过在递归下降的过程中，它将以下面方式逐渐减小快速排序的工作量：

- 每当一次分区的元素个数低于一个阈值 __STL_INTROSORT_THRESHOLD 时，使用插入排序算法来对其进行排序；

- 每当递归深度低于其最大允许深度时，使用堆排序算法代替快速排序算法。

2. __final_insertion_sort()


template<class RandomAccessIterator, class T>
inline void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, T*) {
  if (last - first > __STL_INSERTION_SORT_THRESHOLD) {
    __insertion_sort(first, first + __STL_INSERTION_SORT_THRESHOLD, T());
    __unguarded_insertion_sort(first + __STL_INSERTION_SORT_THRESHOLD, last, T());
  }
  else
    __insertion_sort(first, last, T());
}

当数组中剩余元素的个数不足以使用其他排序算法时，__final_insertion_sort() 使用插入排序算法进行排序操作。具体而言，它将未排序部分分割成已排序和未排序两个部分，然后按照插入排序算法的方式将其依次加入到已排序的序列中。

综上所述，C++ sort() 函数的源码使用的是一种自适应的排序方法，它可以根据数组大小和深度这两个参数来动态选择排序算法，从而确保排序效率的最大化。

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

下一篇: C++源代码的编译方法

评论区

()

相似文章