【GeekBand】Week05-STL-01

STL中一些算法的总结

1.函数的名字列表:

sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition 相对稳定的使得符合某个条件的元素放在前面

2. 比较函数：

equal_to相等
not_equal_to 不相等
less 小于
greater 大于
less_equal小于等于
greater_equal大于等于

上述例子中系统 自己为sort提供了less仿函数。在STL中还提供了其他仿函 数，以下是仿函数列表: 不能直接写入仿 函数的名字，而是要写其重载的()函数： less<int>();
当你的容器中元 素时一些标准类型（int float char)或者string时，你可以直 接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数，另一种是重载类型的<操作符。

3. 全排序：

全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序，而是结合内插排序算法)。复杂度为nlog(n)。stable_sort采用的是"归并排序"，分派足够内存时，其算法复杂度为nlog(n), 否则 其复杂度为nlog(n)log(n)，其优点是会保持相等元素之间的相对位置在排序前后保持一致。
用于全排序的函 数有：

void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator 
last,StrictWeakOrdering comp);
void stable_sort(RandomAccessIterator first, RandomAccessIterator 
last);
void stable_sort(RandomAccessIterator first, RandomAccessIterator
 last, StrictWeakOrdering comp);

4. 局部排序：

partial_sort采用的堆排序（heapsort），它在任何情况下的复杂度都是n*log(n)。
局部排序其实是为了减少不必要的操作而提供的排序方式。
其函数原型为：

void partial_sort(RandomAccessIterator first, RandomAccessIterator 
middle,RandomAccessIterator last);
void partial_sort(RandomAccessIterator first,RandomAccessIterator 
middle,RandomAccessIterator last, StrictWeakOrdering comp);
RandomAccessIterator partial_sort_copy(InputIterator first, 
InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIter
ator result_last);
RandomAccessIterator partial_sort_copy(InputIterator first, 
InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIter
ator result_last, Compare comp);

例如：
班上有1000个学生，我想知道分数最低的5名是哪些人。
partial_sort(vect.begin(),vect.begin()+5,vect.end(),less<student>());

5. nth_element

指定元素排序

void nth_element(RandomAccessIterator first, 
RandomAccessIterator nth, RandomAccessIterator last);
void nth_element(RandomAccessIterator first, 
RandomAccessIterator nth,RandomAccessIterator last,
StrictWeakOrdering comp);

例如：
班上有1000个学生，我想知道分数排在倒数第4名的学生。
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

6. partition 和stable_partition

partition就是把一个区间中的元素按照某个条件分成两类，并没有排序。
其函数原型为：

ForwardIterator partition(ForwardIterator first, ForwardIterator last, 
Predicate pred)
ForwardIterator stable_partition(ForwardIterator first, 
ForwardIterator last, Predicate pred);

例如：班上10个学生，计算所有没有及格（低于60分）的学生：
student exam("pass", 60); stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

7.效率由高到低（耗时由小变大）：

partion
stable_partition
nth_element
partial_sort
sort
stable_sort

8. 如何选择排序函数：

若需对vector, string, deque,或array容器进行全排序，你可选择sort或stable_sort；
若只需对vector, string, deque, 或array容器中取得top n的元素，部分排序partial_sort是首选.
若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部 顺序，nth_element是最理想的；
若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition；
若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。