条目三十一《了解各种与排序有关的选择》
-
1.sort
template<class _RanIt,class _Pr> inline void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) 全排序,整个容器排序。
-
2.partial_sort
template<class _RanIt,class _Pr> inline void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred) 设定排序区间大小,即设定局部全排序
-
3.nth_element
template<class _RanIt,class _Pr> inline void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred) 选出符合条件的前n个,这n个不排序
-
4.partition
template<class _FwdIt,class _Pr> inline _FwdIt partition(_FwdIt _First, const _FwdIt _Last, _Pr _Pred) 对整个容器分区,根据符合的条件分区。返回的迭代器指向第一个不符合条件的元素。
1, 2, 3, 4都要求是随机迭代器,所以只能应用在vector,string,deque。
-
5.stable_sort/stable_partial
用于和目的于上面是一致的,只不过,这两个是稳定的排序,排序前后元素的前后顺序不会被打乱。
如何选择排序算法?
消耗资源的顺序(从少到多)
- 1.partition
- 2.stable_partial
- 3.nth_element
- 4.partial_sort
- 5.sort
- 6.stable_sort