STL算法之sort排序算法 · STL源碼剖析

### 前言 ? 由于在前文的《[STL算法剖析](http://blog.csdn.net/chenhanzhun/article/details/39698523)》中，源碼剖析非常多，不方便學習，也不方便以后復習，這里把這些算法進行歸類，對他們單獨的源碼剖析進行講解。本文介紹的STL算法中的sort排序算法，SGI STL中的排序算法不是簡單的快速排序，而是交叉利用各種排序：堆排序、插入排序和快速排序；這樣做的目的是提高效率，針對數據量比較大的采用快速排序，數據量比較小的可以采用堆排序或插入排序。本文介紹了有關排序的算法random_shuffle、partition、stable_partition、sort、stable_sort、partial_sort、partial_sort_copy、nth_element；注意：STL的sort排序算法的迭代器必須是隨機訪問迭代器。 ### sort排序算法剖析 ~~~ // Return a random number in the range [0, __n). This function encapsulates // whether we're using rand (part of the standard C library) or lrand48 // (not standard, but a much better choice whenever it's available). template <class _Distance> inline _Distance __random_number(_Distance __n) { #ifdef __STL_NO_DRAND48 return rand() % __n; #else return lrand48() % __n; #endif } // random_shuffle //將區間[first,last)內的元素隨機重排 //兩個版本的不同是隨機數的取得 //版本一是使用內部隨機數產生器 //版本二是使用一個會產生隨機數的仿函數 /* 函數功能：Rearranges the elements in the range [first,last) randomly. 函數原型： generator by default (1) template <class RandomAccessIterator> void random_shuffle (RandomAccessIterator first, RandomAccessIterator last); specific generator (2) template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle (RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& gen); */ //版本一 template <class _RandomAccessIter> inline void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __random_number((__i - __first) + 1)); } //版本二 template <class _RandomAccessIter, class _RandomNumberGenerator> void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, _RandomNumberGenerator& __rand) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __rand((__i - __first) + 1)); } // random_sample and random_sample_n (extensions, not part of the standard). template <class _ForwardIter, class _OutputIter, class _Distance> _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); while (__m > 0) { if (__random_number(__remaining) < __m) { *__out = *__first; ++__out; --__m; } --__remaining; ++__first; } return __out; } template <class _ForwardIter, class _OutputIter, class _Distance, class _RandomNumberGenerator> _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n, _RandomNumberGenerator& __rand) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); while (__m > 0) { if (__rand(__remaining) < __m) { *__out = *__first; ++__out; --__m; } --__remaining; ++__first; } return __out; } template <class _InputIter, class _RandomAccessIter, class _Distance> _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out, const _Distance __n) { _Distance __m = 0; _Distance __t = __n; for ( ; __first != __last && __m < __n; ++__m, ++__first) __out[__m] = *__first; while (__first != __last) { ++__t; _Distance __M = __random_number(__t); if (__M < __n) __out[__M] = *__first; ++__first; } return __out + __m; } template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator, class _Distance> _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out, _RandomNumberGenerator& __rand, const _Distance __n) { __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); _Distance __m = 0; _Distance __t = __n; for ( ; __first != __last && __m < __n; ++__m, ++__first) __out[__m] = *__first; while (__first != __last) { ++__t; _Distance __M = __rand(__t); if (__M < __n) __out[__M] = *__first; ++__first; } return __out + __m; } template <class _InputIter, class _RandomAccessIter> inline _RandomAccessIter random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); return __random_sample(__first, __last, __out_first, __out_last - __out_first); } template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator> inline _RandomAccessIter random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last, _RandomNumberGenerator& __rand) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); return __random_sample(__first, __last, __out_first, __rand, __out_last - __out_first); } // partition, stable_partition, and their auxiliary functions //若迭代器的類型為forward_iterator_tag，則調用此函數 template <class _ForwardIter, class _Predicate> _ForwardIter __partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, forward_iterator_tag) { if (__first == __last) return __first;//若為空，直接退出 while (__pred(*__first))//若pred出first的值為true if (++__first == __last) return __first;//先移動迭代器first，在判斷是否到達尾端last _ForwardIter __next = __first;//繼續判斷 while (++__next != __last)//若下一個位置依然不是尾端 if (__pred(*__next)) {//繼續pred出next的值，若為true swap(*__first, *__next);//交換值 ++__first;//繼續下一位置 } return __first; } //若迭代器的類型為bidirectional_iterator_tag，則調用此函數 template <class _BidirectionalIter, class _Predicate> _BidirectionalIter __partition(_BidirectionalIter __first, _BidirectionalIter __last, _Predicate __pred, bidirectional_iterator_tag) { while (true) { while (true) if (__first == __last)//若為空 return __first;//直接退出 else if (__pred(*__first))//first的值符合不移動條件，則不移動該值 ++__first;//只移動迭代器 else//若頭指針符合移動 break;//跳出循環 --__last;//尾指針回溯 while (true) if (__first == __last)//頭指針等于尾指針 return __first;//操作結束 else if (!__pred(*__last))//尾指針的元素符合不移動操作 --__last;//至移動迭代器，并不移動具體元素 else//尾指針的元素符合移動操作 break;//跳出循環 iter_swap(__first, __last);//頭尾指針交換元素 ++__first;//準備下一次循環 } } //將區間[first,last)的元素進行排序，被pred判斷為true的放在區間的前段，判定為false的放在區間后段 //該算算可能會使元素的元素位置放生改變. /* 算法功能：Rearranges the elements from the range [first,last), in such a way that all the elements for which pred returns true precede all those for which it returns false. The iterator returned points to the first element of the second group. 算法原型： template <class BidirectionalIterator, class UnaryPredicate> BidirectionalIterator partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred); */ template <class _ForwardIter, class _Predicate> inline _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_ForwardIter>::value_type); //首先萃取出迭代器first的類型，根據迭代器的類型調用不同的函數 return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); } //partition函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::partition #include <vector> // std::vector bool IsOdd (int i) { return (i%2)==1; } int main () { std::vector<int> myvector; // set some values: for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9 std::vector<int>::iterator bound; bound = std::partition (myvector.begin(), myvector.end(), IsOdd); // print out content: std::cout << "odd elements:"; for (std::vector<int>::iterator it=myvector.begin(); it!=bound; ++it) std::cout << ' ' << *it; std::cout << '\n'; std::cout << "even elements:"; for (std::vector<int>::iterator it=bound; it!=myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: odd elements: 1 9 3 7 5 even elements: 6 4 8 2 */ template <class _ForwardIter, class _Predicate, class _Distance> _ForwardIter __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Distance __len) { if (__len == 1) return __pred(*__first) ? __last : __first; _ForwardIter __middle = __first; advance(__middle, __len / 2); return rotate(__inplace_stable_partition(__first, __middle, __pred, __len / 2), __middle, __inplace_stable_partition(__middle, __last, __pred, __len - __len / 2)); } template <class _ForwardIter, class _Pointer, class _Predicate, class _Distance> _ForwardIter __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size) { if (__len <= __buffer_size) { _ForwardIter __result1 = __first; _Pointer __result2 = __buffer; for ( ; __first != __last ; ++__first) if (__pred(*__first)) { *__result1 = *__first; ++__result1; } else { *__result2 = *__first; ++__result2; } copy(__buffer, __result2, __result1); return __result1; } else { _ForwardIter __middle = __first; advance(__middle, __len / 2); return rotate(__stable_partition_adaptive( __first, __middle, __pred, __len / 2, __buffer, __buffer_size), __middle, __stable_partition_adaptive( __middle, __last, __pred, __len - __len / 2, __buffer, __buffer_size)); } } template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> inline _ForwardIter __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Tp*, _Distance*) { _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); if (__buf.size() > 0) return __stable_partition_adaptive(__first, __last, __pred, _Distance(__buf.requested_size()), __buf.begin(), __buf.size()); else return __inplace_stable_partition(__first, __last, __pred, _Distance(__buf.requested_size())); } template <class _ForwardIter, class _Predicate> inline _ForwardIter stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __first; else return __stable_partition_aux(__first, __last, __pred, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } //找出快速排序的樞紐位置 //版本一采用operator< template <class _RandomAccessIter, class _Tp> _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot) { //找出樞紐軸的位置 //令頭端迭代器向尾端方向移動，尾端迭代器向頭端移動。 //當*first不小于樞紐值時，就停下來，當*last不大于樞紐值時也停下來，然后檢測兩個迭代器是否交錯 //如果first仍然在左側而last仍然在右側，就交換兩個元素，然后各自調整位置，向中央逼近，再繼續執行相同的行為. //直到first和last兩個迭代器交錯，此時表示已找到樞紐軸位置即first所在的位置 while (true) { while (*__first < __pivot) ++__first;//first向尾端移動，直到遇到不小于樞紐值時，停止 --__last; while (__pivot < *__last) --__last;//last向頭端移動，直到遇到不大于樞紐值時，停止 if (!(__first < __last))//檢測兩個迭代器是否交錯 return __first;//交錯，則此時已找到，即為first迭代器所指位置 iter_swap(__first, __last);//否則交換迭代器所指的元素 ++__first;//繼續執行相同行為 } } //版本一采用__comp template <class _RandomAccessIter, class _Tp, class _Compare> _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot, _Compare __comp) { while (true) { while (__comp(*__first, __pivot)) ++__first; --__last; while (__comp(__pivot, *__last)) --__last; if (!(__first < __last)) return __first; iter_swap(__first, __last); ++__first; } } const int __stl_threshold = 16; // sort() and its auxiliary functions. //__insertion_sort版本一的輔助函數 template <class _RandomAccessIter, class _Tp> void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { _RandomAccessIter __next = __last; --__next; //__insertion_sort的內循環 //注意：一旦不再出現逆轉對，循環就結束 while (__val < *__next) {//存在逆轉對 *__last = *__next;//調整元素 __last = __next;//調整迭代器 --__next;//左移一個位置 } *__last = __val;//value的正確插入位置 } //__insertion_sort版本二的輔助函數 template <class _RandomAccessIter, class _Tp, class _Compare> void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) { _RandomAccessIter __next = __last; --__next; while (__comp(__val, *__next)) { *__last = *__next; __last = __next; --__next; } *__last = __val; } //__insertion_sort版本一的輔助函數 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); } //__insertion_sort版本二的輔助函數 template <class _RandomAccessIter, class _Tp, class _Compare> inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Compare __comp) { _Tp __val = *__last; if (__comp(__val, *__first)) { copy_backward(__first, __last, __last + 1); *__first = __val; } else __unguarded_linear_insert(__last, __val, __comp); } //__insertion_sort以雙層循環形式進行。外循環遍歷整個序列，每次迭代決定出一個子區間； //內循環遍歷子區間，將子區間內的每一個“逆轉對”倒轉過來，如果一旦不存在“逆轉對”，表示排序完畢。 //“逆轉對”概念：指任何兩個迭代器i和j，i<j,而*i>*j. //版本一 template <class _RandomAccessIter> void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__first == __last) return; //若區間為空，則退出 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)//外循環，遍歷整個區間 //[first,i)形成的子空間 __linear_insert(__first, __i, __VALUE_TYPE(__first)); } //版本二 template <class _RandomAccessIter, class _Compare> void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp); } 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)); } //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 _Compare> inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first), __comp); } //sort版本一的輔助函數 template <class _RandomAccessIter> void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__last - __first > __stl_threshold) {//判斷元素個數是否大于16 //則把區間分割成兩段，一端長度為16，另一端為剩余的長度 __insertion_sort(__first, __first + __stl_threshold); __unguarded_insertion_sort(__first + __stl_threshold, __last); } else//若不大于16，直接調用插入排序 __insertion_sort(__first, __last); } template <class _RandomAccessIter, class _Compare> void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__last - __first > __stl_threshold) { __insertion_sort(__first, __first + __stl_threshold, __comp); __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); } else __insertion_sort(__first, __last, __comp); } //_lg()函數是用來控制分割惡化的情況 //該函數找出2^k <= n 的最大值k; //例如：n=7,得k=2; n=20,得k=4; n=8,得k=3; template <class _Size> inline _Size __lg(_Size __n) { _Size __k; for (__k = 0; __n != 1; __n >>= 1) ++__k; return __k; } //sort版本一的輔助函數 //參數__depth_limit表示最大的分割層數 template <class _RandomAccessIter, class _Tp, class _Size> void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Size __depth_limit) { //__stl_threshold為全局常量，其值為16 while (__last - __first > __stl_threshold) {//若區間長度大于16 if (__depth_limit == 0) {//表示分割惡化 partial_sort(__first, __last, __last);//轉而調用堆排序heap_sort() return; } --__depth_limit; //計算分割點cut，樞紐值是采用首、尾、中央三個的中間值 _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, class _Tp, class _Size, class _Compare> void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Size __depth_limit, _Compare __comp) { while (__last - __first > __stl_threshold) { if (__depth_limit == 0) { partial_sort(__first, __last, __last, __comp); return; } --__depth_limit; _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1), __comp)), __comp); __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); __last = __cut; } } //SGI STL的排序算法，迭代器參數的類型必須是隨機訪問迭代器_RandomAccessIter /* 函數功能：Sorts the elements in the range [first,last) into ascending order. 函數原型： default (1) ：版本一采用默認的operator< template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); custom (2) ：版本二采用仿函數comp template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); */ //版本一 template <class _RandomAccessIter> inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); //_lg()函數是用來控制分割惡化的情況 if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2); //進行插入排序 __final_insertion_sort(__first, __last); } } //版本二 template <class _RandomAccessIter, class _Compare> inline void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2, __comp); __final_insertion_sort(__first, __last, __comp); } } // stable_sort() and its auxiliary functions. template <class _RandomAccessIter> void __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__last - __first < 15) { __insertion_sort(__first, __last); return; } _RandomAccessIter __middle = __first + (__last - __first) / 2; __inplace_stable_sort(__first, __middle); __inplace_stable_sort(__middle, __last); __merge_without_buffer(__first, __middle, __last, __middle - __first, __last - __middle); } template <class _RandomAccessIter, class _Compare> void __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__last - __first < 15) { __insertion_sort(__first, __last, __comp); return; } _RandomAccessIter __middle = __first + (__last - __first) / 2; __inplace_stable_sort(__first, __middle, __comp); __inplace_stable_sort(__middle, __last, __comp); __merge_without_buffer(__first, __middle, __last, __middle - __first, __last - __middle, __comp); } template <class _RandomAccessIter1, class _RandomAccessIter2, class _Distance> void __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, _RandomAccessIter2 __result, _Distance __step_size) { _Distance __two_step = 2 * __step_size; while (__last - __first >= __two_step) { __result = merge(__first, __first + __step_size, __first + __step_size, __first + __two_step, __result); __first += __two_step; } __step_size = min(_Distance(__last - __first), __step_size); merge(__first, __first + __step_size, __first + __step_size, __last, __result); } template <class _RandomAccessIter1, class _RandomAccessIter2, class _Distance, class _Compare> void __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, _RandomAccessIter2 __result, _Distance __step_size, _Compare __comp) { _Distance __two_step = 2 * __step_size; while (__last - __first >= __two_step) { __result = merge(__first, __first + __step_size, __first + __step_size, __first + __two_step, __result, __comp); __first += __two_step; } __step_size = min(_Distance(__last - __first), __step_size); merge(__first, __first + __step_size, __first + __step_size, __last, __result, __comp); } const int __stl_chunk_size = 7; template <class _RandomAccessIter, class _Distance> void __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Distance __chunk_size) { while (__last - __first >= __chunk_size) { __insertion_sort(__first, __first + __chunk_size); __first += __chunk_size; } __insertion_sort(__first, __last); } template <class _RandomAccessIter, class _Distance, class _Compare> void __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Distance __chunk_size, _Compare __comp) { while (__last - __first >= __chunk_size) { __insertion_sort(__first, __first + __chunk_size, __comp); __first += __chunk_size; } __insertion_sort(__first, __last, __comp); } template <class _RandomAccessIter, class _Pointer, class _Distance> void __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance*) { _Distance __len = __last - __first; _Pointer __buffer_last = __buffer + __len; _Distance __step_size = __stl_chunk_size; __chunk_insertion_sort(__first, __last, __step_size); while (__step_size < __len) { __merge_sort_loop(__first, __last, __buffer, __step_size); __step_size *= 2; __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); __step_size *= 2; } } template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> void __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance*, _Compare __comp) { _Distance __len = __last - __first; _Pointer __buffer_last = __buffer + __len; _Distance __step_size = __stl_chunk_size; __chunk_insertion_sort(__first, __last, __step_size, __comp); while (__step_size < __len) { __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); __step_size *= 2; __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); __step_size *= 2; } } template <class _RandomAccessIter, class _Pointer, class _Distance> void __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance __buffer_size) { _Distance __len = (__last - __first + 1) / 2; _RandomAccessIter __middle = __first + __len; if (__len > __buffer_size) { __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size); __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size); } else { __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0); __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0); } __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), _Distance(__last - __middle), __buffer, __buffer_size); } template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> void __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance __buffer_size, _Compare __comp) { _Distance __len = (__last - __first + 1) / 2; _RandomAccessIter __middle = __first + __len; if (__len > __buffer_size) { __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, __comp); __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, __comp); } else { __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0, __comp); __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0, __comp); } __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), _Distance(__last - __middle), __buffer, __buffer_size, __comp); } template <class _RandomAccessIter, class _Tp, class _Distance> inline void __stable_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Distance*) { _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); if (buf.begin() == 0) __inplace_stable_sort(__first, __last); else __stable_sort_adaptive(__first, __last, buf.begin(), _Distance(buf.size())); } template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> inline void __stable_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Distance*, _Compare __comp) { _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); if (buf.begin() == 0) __inplace_stable_sort(__first, __last, __comp); else __stable_sort_adaptive(__first, __last, buf.begin(), _Distance(buf.size()), __comp); } template <class _RandomAccessIter> inline void stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __stable_sort_aux(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } template <class _RandomAccessIter, class _Compare> inline void stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __stable_sort_aux(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), __comp); } // partial_sort, partial_sort_copy, and auxiliary functions. //重新安排序列[first,last)，使序列前半部分middle-first個最小元素以遞增順序排序，并將其置于[first,middle) //其余last-middle個元素不指定任何排序，并將其置于[middle,last) //注意：迭代器middle是在[first,last)范圍之內 /* 函數功能：Rearranges the elements in the range [first,last), in such a way that the elements before middle are the smallest elements in the entire range and are sorted in ascending order, while the remaining elements are left without any specific order. 函數原型： default (1) 版本一 operator< template <class RandomAccessIterator> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); custom (2) 版本二 comp template <class RandomAccessIterator, class Compare> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); */ template <class _RandomAccessIter, class _Tp> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*) { //利用heap的知識，在SGI STL中，是采用最大堆 //將[first,middle)區間的元素創建成最大堆 //再根據最大堆的性質，一個一個彈出堆，并將其保存，即堆排序 make_heap(__first, __middle);//創建最大堆，定義與<stl_heap.h>文件 //以下是在區間中[first,last)找出middle-first個最小元素 //這里的是將后半部分[middle,last)的元素依次與最大堆的根節點元素(即堆的最大元素)比較 //若小于堆的最大元素，則與堆的最大元素交換，并調整堆，使其依次成為最大堆 //若不小于堆的最大元素，則不作任何操作 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first) __pop_heap(__first, __middle, __i, _Tp(*__i), __DISTANCE_TYPE(__first)); sort_heap(__first, __middle);//對最大堆進行堆排序 } //版本一 template <class _RandomAccessIter> inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*, _Compare __comp) { make_heap(__first, __middle, __comp); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (__comp(*__i, *__first)) __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, __DISTANCE_TYPE(__first)); sort_heap(__first, __middle, __comp); } //版本二 template <class _RandomAccessIter, class _Compare> inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp); } //partial_sort_copy與partial_sort的實現機制是相同，只是partial_sort_copy將元素排序后放在以result起始的容器中 template <class _InputIter, class _RandomAccessIter, class _Distance, class _Tp> _RandomAccessIter __partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Distance*, _Tp*) { if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { *__result_real_last = *__first; ++__result_real_last; ++__first; } make_heap(__result_first, __result_real_last); while (__first != __last) { if (*__first < *__result_first) __adjust_heap(__result_first, _Distance(0), _Distance(__result_real_last - __result_first), _Tp(*__first)); ++__first; } sort_heap(__result_first, __result_real_last); return __result_real_last; } template <class _InputIter, class _RandomAccessIter> inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, _LessThanComparable); return __partial_sort_copy(__first, __last, __result_first, __result_last, __DISTANCE_TYPE(__result_first), __VALUE_TYPE(__first)); } template <class _InputIter, class _RandomAccessIter, class _Compare, class _Distance, class _Tp> _RandomAccessIter __partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp, _Distance*, _Tp*) { if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { *__result_real_last = *__first; ++__result_real_last; ++__first; } make_heap(__result_first, __result_real_last, __comp); while (__first != __last) { if (__comp(*__first, *__result_first)) __adjust_heap(__result_first, _Distance(0), _Distance(__result_real_last - __result_first), _Tp(*__first), __comp); ++__first; } sort_heap(__result_first, __result_real_last, __comp); return __result_real_last; } template <class _InputIter, class _RandomAccessIter, class _Compare> inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp) { __STL_REQUIRES(_InputIter, _InputIterator); __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); return __partial_sort_copy(__first, __last, __result_first, __result_last, __comp, __DISTANCE_TYPE(__result_first), __VALUE_TYPE(__first)); } // nth_element() and its auxiliary functions. //nth_element版本一輔助函數 template <class _RandomAccessIter, class _Tp> void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Tp*) { while (__last - __first > 3) {//區間長度大于3 //獲取分割點cut _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1)))); if (__cut <= __nth)//若分割點小于指定位置，則nth位置在右半段 __first = __cut;//再對右半段進行分割 else //否則，對左半段進行分割 __last = __cut; } __insertion_sort(__first, __last); } //重新排序序列[first,last)，使迭代器nth所指的元素，與“整個[first,last)序列完整排序后，同一位置的元素”同值. //此外，必須保證[nth,last)內的所有元素不小于[first,nth)內的元素，但是對于序列[first,nth)和序列[nth,last)內的元素的排序順序不能確定. /* 函數功能：Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. 函數原型： default (1) template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); custom (2) template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); */ //nth_element版本一 template <class _RandomAccessIter> inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __nth_element(__first, __nth, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Tp*, _Compare __comp) { while (__last - __first > 3) { _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1), __comp)), __comp); if (__cut <= __nth) __first = __cut; else __last = __cut; } __insertion_sort(__first, __last, __comp); } template <class _RandomAccessIter, class _Compare> inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp); } // is_sorted, a predicated testing whether a range is sorted in // nondescending order. This is an extension, not part of the C++ // standard. template <class _ForwardIter> bool is_sorted(_ForwardIter __first, _ForwardIter __last) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, _LessThanComparable); if (__first == __last) return true; _ForwardIter __next = __first; for (++__next; __next != __last; __first = __next, ++__next) { if (*__next < *__first) return false; } return true; } template <class _ForwardIter, class _StrictWeakOrdering> bool is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) { __STL_REQUIRES(_ForwardIter, _ForwardIterator); __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, typename iterator_traits<_ForwardIter>::value_type, typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return true; _ForwardIter __next = __first; for (++__next; __next != __last; __first = __next, ++__next) { if (__comp(*__next, *__first)) return false; } return true; } ~~~ 參考資料：《STL源碼剖析》侯捷