STL中的排序函数
1.Sort函数
功能:对给定的区间所有元素进行排序
排序算法:快速排序，堆排序，插入排序
快速排序的最优时间复杂度：O(nlogn)，最差时间复杂度为：O(n^2)
插入排序的最优时间复杂度：O(N)，最差时间复杂度为：O(N^2)
堆排序的最优时间复杂度为：O(nlogn)，最差时间复杂度为：O(nlogn)
源码:
//1.快速排序
//2.堆排序
//3.插入排序
template
inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
if (__first != __last) {
//混合排序
//1.快速排序
//2.堆排序
__introsort_loop(__first, __last,
__VALUE_TYPE(__first),
//快速排序最大递归深度
__lg(__last - __first) * 2);
//插入排序
__final_insertion_sort(__first, __last);
}
}
//混合排序算法，内省式排序
//1.元素个数小于__stl_threshold个，结束内省式排序，返回sort函数，改用插入排序
//2.元素个数大于__stl_threshold个，如果递归深度超过最大层次的递归调用，
//说明快速排序不合适，使用partial_sort堆排序
//3.若是没有超过最大递归调用深度，调用函数unguarded_partition对当前元素快速排序，并返回位置。
template
void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit)
{
while (__last - __first > __stl_threshold) {
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);
//左半部分直接回到while函数
__last = __cut;
}
}
//插入排序
template
void __final_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
if (__last - __first > __stl_threshold) {//16
__insertion_sort(__first, __first + __stl_threshold);
//双循环 ，在个元素的基础 上，依次添加元素，不会比较 第一个元素
__unguarded_insertion_sort(__first + __stl_threshold, __last);
}
else
//小于个插入排序，调 用插入排序
//双循环 ，在个元素的基础 上，依次添加元素，会和数据中第一个元素first比较 __insertion_sort(__first, __last);
}
template
inline _Size __lg(_Size __n) {
_Size __k;
for (__k = 0; __n != 1; __n >>= 1) ++__k;
return __k;
}
//插入排序
//在迭代器last之前插入数据val，使之按照升序排列
//直接从元素尾判断
template
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
_RandomAccessIter __next = __last;
--__next;
while (__val < *__next) {
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
//插入排序
//在[first,last]中国对数据重新排序，使之按照升序排列
//先判断first元素
template
inline void __linear_insert(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*) {
_Tp __val = *__last;
//如果last数据小于first数据，整个区间右移一位，并且first等于last
//last+1中是不是还 是之前的last数据?
if (__val < *__first) {
copy_backward(__first, __last, __last + 1);
*__first = __val;
}
else
//如果last数据大于first，调 用之前函数将，最后一个函数插入列表，升序排序
__unguarded_linear_insert(__last, __val);
}
//插入排序
//以first为第一个数据，依次插入列表中的数据，通过函数linear_insert升序排列
template
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));
}
//以first为起点，依次对列表中的数据，通过函数unguarded_linear_insert升序排序
template
void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*) {
for (_RandomAccessIter __i = __first; __i != __last; ++__i)
__unguarded_linear_insert(__i, _Tp(*__i));
}
template
inline void __unguarded_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
__unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
}
2.Stable_sort函数
功能:对给定区间所有元素进行稳定排序
算法:归并排序，插入排序
归并排序的最优时间复杂度为：O(nlogn)，最差时间复杂度为：O(nlogn)
merge，指的是将两个顺序序列合并成一个顺序的序列的方法
归并排序是稳定的排序，即相等的元素的顺序不会改变，速度仅次于快速排序，一般用于总体无序，但是各个子项相对有序的数列，分配足够内存，其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n)
插入排序的最优时间复杂度：O(N)，最差时间复杂度为：O(N^2)
源码:
template
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
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
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
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;// sgi stl 7
//分段使用插入排序
__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
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 _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); } 3.Partial_sort函数 功能:对给定区间所有元素部分排序 算法:堆排序 堆排序在任何情况下复杂度都是n*log(n) 源码: //堆排序 template 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)); sort_heap(__first, __middle); } Heap算法 Heap不属于STL容器组件，priority_queue的助手，priority_queue允许以任何次序将任何元素推入容器内，但取出时一定是从优先级最高的元素开始取。 复杂度：初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog (n)，所以总的时间复杂度为(n+nlogn)=O(nlogn) STL堆：堆分为最大堆和最小堆，stl中实现的都是最大堆，堆一般通过数组实现 如果不用数组索引0的位置，N的父节点是N/2，N的左右子节点分别是2N和2N+1. 如果使用数组索引0的位置，N的父节点是(N-1)/2,N的左右子节点分别是2N+1和2(N+1) STL中实现使用索引0的位置 用法： Int ia[9] = {0, 1,2,3,4,8,9,3,5}; Vector Make_heap(ivec.begin(), ivec.end()); // 9 5 8 3 4 0 2 3 1 Ivec.push_back(7); Push_heap(ivec.begin(), ivec.end()); // 9 7 8 3 5 0 2 3 1 4 Pop_heap(ivec.begin(), ivec.end()); Ivec.back(); //9, return but no remove Ivec.pop_back(); //remove last elem and no return Sort_heap(ivec.begin(), ivec.end()); //0 1 2 3 3 4 5 7 8 如果底层使用array进行堆排序 不可以对满载的array进行push_heap() *** 作，因为得先在array尾端增加一个元素 源码： template void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value) { //父节点 _Distance __parent = (__holeIndex - 1) / 2; //尚未到顶端，并且父节点小于新值 while (__holeIndex > __topIndex && *(__first + __parent) < __value) { //将洞值设置为父节点 *(__first + __holeIndex) = *(__first + __parent); //更新holeIndex，继续向上层比较 __holeIndex = __parent; //更新父节点 __parent = (__holeIndex - 1) / 2; } //设置洞值为新值，完成插入 *** 作，直接存放新值的位置即可，不用每次交换位置 *(__first + __holeIndex) = __value; } template inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance*, _Tp*) { //holeIndex尾部，差入值为尾部元素，从0开始，在插入元素后，调用push_heap __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), _Tp(*(__last - 1))); } //上浮 *** 作 template inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __push_heap_aux(__first, __last, __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); } template void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value) { //顶点 _Distance __topIndex = __holeIndex; //右子节点 _Distance __secondChild = 2 * __holeIndex + 2; while (__secondChild < __len) { //左子节点比右子节点大 if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) //选择最大的子节点 __secondChild--; //最大子节点为洞值 *(__first + __holeIndex) = *(__first + __secondChild); __holeIndex = __secondChild; __secondChild = 2 * (__secondChild + 1); } if (__secondChild == __len) { *(__first + __holeIndex) = *(__first + (__secondChild - 1)); __holeIndex = __secondChild - 1; } __push_heap(__first, __holeIndex, __topIndex, __value); } template inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __value, _Distance*) { *__result = *__first; __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value); } template inline void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) { __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __DISTANCE_TYPE(__first)); } //将最大堆中的最大元素放置到容器底部 template inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __pop_heap_aux(__first, __last, __VALUE_TYPE(__first)); } //下沉 *** 作 template void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*, _Distance*) { if (__last - __first < 2) return; _Distance __len = __last - __first; //父节点，然后下沉 _Distance __parent = (__len - 2)/2; while (true) { //parent下沉到合适位置 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent))); //构造完成 if (__parent == 0) return; __parent--; } } //将容器中已有的数据，构造成满足堆属性的数据组合 template inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __make_heap(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } template void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { //依次将最大元素放置尾端，即可实现堆排序 while (__last - __first > 1) pop_heap(__first, __last--); } 4.Nth_element函数 功能:找出给定区间的某个位置对应的元素 算法:快速排序，插入排序 复杂度: 快速排序的平均复杂度是 O（N） 源码: template void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Tp*) { while (__last - __first > 3) { //快速排序 _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2), *(__last - 1)))); if (__cut <= __nth) __first = __cut; else __last = __cut; } //插入排序 __insertion_sort(__first, __last); } 5.Partition函数 功能:使符合某个条件的元素放在前面, 该函数不保证元素的原始相对位置，如果需要保留原始相对位置，应使用stable_partition 源码: template _ForwardIter __partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, forward_iterator_tag) { if (__first == __last) return __first; while (__pred(*__first)) if (++__first == __last) return __first; _ForwardIter __next = __first; while (++__next != __last) if (__pred(*__next)) { swap(*__first, *__next); ++__first; } return __first; } template _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; else break; --__last; while (true) if (__first == __last) return __first; else if (!__pred(*__last)) --__last; else break; iter_swap(__first, __last); ++__first; } } 6.Stable_partition函数 功能:相对稳定的使得符合某个条件的元素放在前面 源码: template 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 _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 _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)); } 从效率上由高到低为: Partion Stable_partition Nth_element Partial_sort Sort Stable_sort 1.若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort； 2.若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选. 3.若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序，nth_element是最理想的； 4.若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition； 5.若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。 若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）