C++ STL函数：sort源码阅读

sort和qsort区别

1. 一个是c标准库函数，sort是STL中的函数模板，位于
2. qsort的参数用指针表示范围；sort 的参数用迭代器表示范围
3. qsort使用的是快排，sort在大体框架上遵循传统的快排算法（递归），在极端情况下转为堆排序，最后会在整个数组上做一次插入排序

sort源码阅读标记

  //sort 带有比较函数的重载类型 函数源码
  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
       _Compare __comp)
    {
      if (__first != __last)
    {
    // __introsort_loop先进行一遍IntroSort，但是不是严格意义上的IntroSort。因为执行完之后区间并不是完全有序的，而是基本有序的。
  	//__introsort_loop和IntroSort不同的地方是，__introsort_loop会在一开始会判断区间的大小，当区间小于2^4（_S_threshold 为枚举定义 == 16）的时候，就直接返回。
      std::__introsort_loop(__first, __last,
                std::__lg(__last - __first) * 2,
                __comp); 
      // 在区间基本有序的基础上再做一遍插入排序，使区间完全有序
      std::__final_insertion_sort(__first, __last, __comp);
    }
    }

  //__introsort_loop源码
  enum { _S_threshold = 16 };

  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    void
    __introsort_loop(_RandomAccessIterator __first,
             _RandomAccessIterator __last,
             _Size __depth_limit, _Compare __comp)
    {
      // 若区间大小<=16就不再排序。
      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;
    // 回到while循环，对左半区间进行排序，这么做能显著减少__introsort_loop的调用的次数
    }
    }

  //__final_insertion_sort源码
   template<typename _RandomAccessIterator, typename _Compare>
    void
    __final_insertion_sort(_RandomAccessIterator __first,
               _RandomAccessIterator __last, _Compare __comp)
    {
      if (__last - __first > int(_S_threshold)) // 区间长度大于16
    {
      // 插入排序
      std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 
      // 也是插入排序，只是在插入排序的内循环时，不再判断边界条件，因为已经保证了区间前面肯定有比待插入元素更小的元素
      std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 
                      __comp);
    }
      else // 区间长度小于等于16的话
    std::__insertion_sort(__first, __last, __comp); // 插入排序
    }

总结

sort就是在递归次数小于等于16时，使用快排进行排序，当快排的递归次数大于16时，自动转换成堆排序，最后会进行一次插入排序使完全排序