sort有两种重载形式，一种是依靠自定义的比较函数comp的排序函数，一种是依靠<运算符的排序函数。下面的源码解读选择<运算符的版本。 sort函数的流程图如下

1 提供给外界的接口sort源码

template <class _RandomAccessIter> inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__first != __last) {//元素个数>1才会排序 __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2);//先进行快速排序分割序列块 __final_insertion_sort(__first, __last);//到这一步，__first~__last范围中已经有多个子序列，并且每一个子序列中的值都比前一个子序列大 } }

1.1快排分割序列块函数__introsort_loop，以及用来限定分割次数的函数__lg

template <class _RandomAccessIter, class _Tp, class _Size> void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*,//traits萃取作用 _Size __depth_limit)//快排递归深度限制，每用快排分割一次，__depth_limit就减一，如果__depth_limit为零，就不会再分割了。 { while (__last - __first > __stl_threshold) {//当每个分块的元素个数大于阈值(__stl_threshold)时， //就会继续用快排分块，而如果≤阈值时，就直接跳过这个函数，用插入排序来排列小型序列，问题一 if (__depth_limit == 0) {//当递归深度限制为0时，就使用堆排序，问题二 partial_sort(__first, __last, __last);//将__first~__last序列按升序排列 return; } --__depth_limit;//每次快排分割之前，先将深度限制减一 //接下来就是将一个序列以枢轴为中奖，分成左右两块，左边都比枢轴小，右边都比枢轴大 _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1))));//通过快排找到分割点 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);//对分割点右边的部分递归快排 __last = __cut;//分割点左边的部分进入下一个循环，同样是继续快排分割操作，只是没有递归，这样少一轮递归，速度会加快很多 } } template <class _Size> inline _Size __lg(_Size __n) {//计算快排递归深度限制的函数，n是整个排序序列的尺寸大小 _Size __k; for (__k = 0; __n != 1; __n >>= 1) ++__k; return __k;//最后k值是满足不等式：2^k≤n的最大整数 }

问题1：为什么当被分割的子序列尺寸在阈值之下，就会停止快排，而采用插入排序

因为当一个序列只有十来个元素时，未必是快排最快，因为快排是递归实现的，对于小规模排序，递归的代价显得有点大，反而会拖慢程序。由于是被快排分割成小序列时，所以每个小序列中的元素全部或大于或小于一个值，也就是几近排好序的序列，这时候使用插入排序会有很好表现。 问题2：为什么需要有递归深度限制？因为在快排中，不当的枢轴选择会导致快排从O(nlogn)恶化成O(n^2)。所以这里使用的是introsort方法，也就是当快排有恶化成二次复杂度倾向时，能够停止继续分割，而使用堆排序。

1.1.1 部分堆排序函数partial_sort

找到序列中最小的(__middle-__first)个元素，由小到大排好序，放在序列的__first~__middle

template <class _RandomAccessIter> inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last) { __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter, class _Tp> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*) { make_heap(__first, __middle); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first) __pop_heap(__first, __middle, __i, _Tp(*__i), __DISTANCE_TYPE(__first));//把__first位置的元素移到i位置，然后把i位置原来的元素移到最大堆中并排好序 sort_heap(__first, __middle); //将最大堆转换成有序数组 }

1.1.2 快排分割函数__unguarded_partition以及找枢轴函数__median

__unguarded_partition函数就是根据第三个输入参数枢轴值，将__first~__last分成个子序列，一个子序列中的元素都大于枢轴，一个子序列中的元素都小于枢轴。（三点中值法）__median就是如何在一个序列中确定枢轴值，就是将一个序列中的头、尾和中央三个位置的元素数值作比较，找到这三个数值中中间那个值，作为枢值。 template <class _RandomAccessIter, class _Tp> _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot) //__pivot就是枢值 { while (true) { while (*__first < __pivot)//first找到≥__pivot就结束循环 ++__first; --__last; while (__pivot < *__last)//last找到≤__pivot 就结束循环 --__last; if (!(__first < __last))//如果first位置≥last位置就结束 return __first;//最后以first停留的位置作为分界 iter_swap(__first, __last);//否则就交换first位置和last位置的元素，也就是把≥__pivot的元素放到右边，把≤__pivot的元素放到左边 ++__first; } } //这个函数就是找a，b，c中值 template <class _Tp> inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { if (__a < __b) if (__b < __c) return __b; else if (__a < __c) return __c; else return __a; else if (__a < __c) return __a; else if (__b < __c) return __c; else return __b; }

__unguarded_partition函数的示例图：

1.2 插入排序函数__final_insertion_sort

template <class _RandomAccessIter> void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__last - __first > __stl_threshold) {//如果超过阈值，就分两段排序 __insertion_sort(__first, __first + __stl_threshold);//第一段需要加上边界判断，是因为前16个值可能比__first要小，会移到__first前面，因为可能都属于第一个子序列 __unguarded_insertion_sort(__first + __stl_threshold, __last);//但是后面的值一定不可能比__first值要小，因为后面的元素肯定不属于第一个子序列，根据快排的性质，不可能比前面序列要小，所以不需要加边界判断。 } else __insertion_sort(__first, __last);//否则就分一段，但是不确定里面有几个子序列，所以都加了边界判断。 }

问题：为什么超过16的位置处可以不用加边界判断？ 因为经过快排分割以后，从__first~__last中就是由若干个子序列组成的，比如上面那张图，可能完全排列以后是这样的：所以其实只有第一个子序列需要进行边界判断，因为后面的子序列中的值一定小于第一个子序列中的值。而第一个子序列一定小于阈值，如果比阈值大，只有可能是已经堆排序的了。所以小于阈值的进性边界检测，只是因为不确定第一子序列的元素个数，所以设定的安全值。

1.2.1 快排的封装函数__insertion_sort和__linear_insert

__insertion_sort函数就是主要是把所有元素都按照同一种插入排序的方法进行排序__linear_insert函数就是把__last插入到__first~__last-1的序列中。首先把__last< *__first的情况单独拿出来，如果是这种情况，那么__last元素一定添加在__first前面。如果不是这种情况，就再执行__unguarded_linear_insert函数。 template <class _RandomAccessIter>//插入排序 void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) __linear_insert(__first, __i, __VALUE_TYPE(__first)); }//插入排序，迭代器范围从左往右逐渐扩大，每次都把迭代器范围的最后一个元素往前移动，移到比它小的第一个数后面，如下图所示 template <class _RandomAccessIter, class _Tp> inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*) {//last就是要插入的值 _Tp __val = *__last; /*先把最后一个数和第一个数比较，避免出现最坏情况*/ if (__val < *__first) {//如果最后一个数小于第一个数 copy_backward(__first, __last, __last + 1); *__first = __val;//直接把最后一个数放到前面，整体往后移 }/*把最后一个元素从后往前依次比较，找到最后一个元素应该放置的位置*/ //由于有了第一个判断，所以下面的情况中最后一个元素一定大于等于第一个元素，所以__unguarded_linear_insert就不许哟进行边界判断了。节省了一些时间 else//如果最后一个数不小于第一个数，就从后面往前找到小于__val的第一个数，然后将__val插在它的后面 //相当于把比__val大的数都往后面移动一格 __unguarded_linear_insert(__last, __val);//__val就是__last迭代器指向的值 }

相当于从头开始，每一次都在已经排好序的队列中找到新加入元素的位置，所以叫插入排序。

1.2.1.1 不检测边界的插值排序__unguarded_linear_insert函数

这个函数没有边界判断的，就是不需要判断–__next会不会超过first，因为如果会超过first，就不会进入这个函数了

//从_last往前寻找，把比__val大的数整体往后移一位，直到找到一个比__val小的值 template <class _RandomAccessIter, class _Tp> void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { _RandomAccessIter __next = __last; --__next;//在这个函数中，__next和__last之间的距离一直是1 while (__val < *__next) {//这个循环一定会在first之前结束的，因为在执行这个函数之前已经判断了，first一定比__val小 *__last = *__next;//迭代器所指向的值交换 __last = __next;//迭代器所指向元素交换，其实就是将__next和__last元素位置调换 --__next; } *__last = __val; }

1.2.2 __unguarded_insertion_sort函数

执行不带边界判断的插入排序

template <class _RandomAccessIter> inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter, class _Tp> void __unguarded_insertion_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*) { for (_RandomAccessIter __i = __first; __i != __last; ++__i) __unguarded_linear_insert(__i, _Tp(*__i)); }