轉自:http://blog.csdn.net/superhackerzhang/article/details/6410670
以SGI的STL為例
sort有兩種重載形式
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);
這兩種形式都要求形隨機訪問迭代器，因此只能用于容器vector或deque,這里我們只以第一種為例進行講解
在數據量大時，采用Quick Sort，分段遞歸排序，一旦分段后的數據量小于門限值時，為避免遞歸的額外開銷，便采用Insertion sort。
如果遞歸的層次過深，還會使用Heap Sort.
對于以下的以__開頭的命名函數，表示其為被內部的其它函數調用，而不能被用戶直接調用。
首先來看插入排序
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)); }
其所調用的 __linear_insert如下示：
template <class _RandomAccessIter, class _Tp>
inline
void __linear_insert(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*) {
_Tp __val = *__last;
if (__val < *__first) {
copy_backward(__first, __last, __last + 1);
*__first = __val;
}
else __unguarded_linear_insert(__last, __val);
}
這里需要對其進行一下說明，通常情況下在進行插入排序時，既要進行大小的比較，又要對邊界進行控制，經過上面的改進后，但只需要進行大小的比較便可，這就是代碼的高明這處。
首先對要插入有序部分的元素__val與隊首的最小元素 *__first進行比較，如果__val < *__first，則只__first與 __last之間的元素向后移一個位置，然后將__val插入隊首。
如果__val >= *__first，則說明__val在將要新生成的有序隊列中不是最小，因此，在下面的while中不用進行界限控制，只比較元素的大小即可。
template <class _RandomAccessIter, class _Tp>
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
_RandomAccessIter __next = __last;
--__next;
while (__val < *__next) {
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
在STL中對避免快排時每次都選擇最小或最大的元素做軸，使用以下函數選擇一個三點中值。
template <class _Tp>
inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
__STL_REQUIRES(_Tp, _LessThanComparable);
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;
}
下面是快排中所要使用的分割函數。對[first,last)區間的元素進行分割，使用得中軸右邊的元素大于等于中軸，左邊的元素小于等于中軸，并返回中軸所在位置。
template <class _RandomAccessIter, class _Tp>
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,_RandomAccessIter __last,_Tp __pivot) {
while (true) {
while (*__first < __pivot) ++__first;
--__last;
while (__pivot < *__last) --__last;
if (!(__first < __last))
return __first;
iter_swap(__first, __last);
++__first;
}
}
sort 代碼如下
template <class _RandomAccessIter>
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
if (__first != __last) {
__introsort_loop(__first, __last,
__VALUE_TYPE(__first),
__lg(__last - __first) * 2);
__final_insertion_sort(__first, __last);
}
}
基中__lg(n)用來找出2^k<=n的最大k值，用以控控制遞歸的深度。
template <class _Size>
inline _Size __lg(_Size __n) {
_Size __k;
for (__k = 0; __n != 1; __n >>= 1) ++__k;
return __k;
}
下面的是用來對區間使用快排，以達到部分有序狀態。
template <class _RandomAccessIter, class _Tp, class _Size>
void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit) {
while (__last - __first > __stl_threshold) {//__stl_threshold在這里用前面定義的常量16，當區間多于16個元素時，才有必要使用快排。
if (__depth_limit == 0) {//當遞歸的層次過深時，使用堆排序。
partial_sort(__first, __last, __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 _RandomAccessIter>
void __final_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
if (__last - __first > __stl_threshold) {
__insertion_sort(__first, __first + __stl_threshold);
__unguarded_insertion_sort(__first + __stl_threshold, __last);
} else __insertion_sort(__first, __last);
}
些函數先判斷元素個數是否大于16，如是大于，則先用__insertion_sort()對16個元素的子序列排序，再用__unguarded_insertion_sort()對
其余的排序。否則直接用__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, class _Compare>
void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp*, _Compare __comp) {
for (_RandomAccessIter __i = __first; __i != __last; ++__i)
__unguarded_linear_insert(__i, _Tp(*__i), __comp);
}
template <class _RandomAccessIter, class _Tp>
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
_RandomAccessIter __next = __last;
--__next;
while (__val < *__next) {
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
ps:個人感覺__final_insertion_sort()中區分區間大小是多此一舉，因為最終其調用的都是__unguarded_linear_insert()，其并沒用針對不
同的大小區間采用明顯不用的算法。