stl排序总结

学习网站：http://www.stlchina.org/twiki/bin/view.pl/Main/STLTechArticles http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms

排序(sort)：所有sort算法介绍:使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator)

1. 所有STL sort算法函数的名字列表: 函数名 sort stable_sort partial_sort partial_sort_copy nth_element is_sorted partition stable_partition 2. 比较函数：当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数。 vector < int > vect; //...

sort(vect.begin(), vect.end()); //此时相当于调用

sort(vect.begin(), vect.end(), less() ); sort 中的其他比较函数 equal_to not_equal_to less greater less_equal greater_equal 相等 不相等 小于 大于 小于等于 大于等于 功能描述 对给定区间所有元素进行排序 对给定区间所有元素进行稳定排序 对给定区间所有元素部分排序 对给定区间复制并排序 找出给定区间的某个位置对应的元素 判断一个区间是否已经排好序 使得符合某个条件的元素放在前面 相对稳定的使得符合某个条件的元素放在前面 上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表:

不能直接写入仿函数的名字，而是要写其重载的()函数： less();

当你的容器中元素时一些标准类型（int float char)或者string时，你可以直接使用这些函数模板。但如果你

时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的'<'操作赋。如： bool less_second(const myclass & m1, const myclass & m2) { return m1.second < m2.second; }

3. 全排序：全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的\快速排序算法\目前大部分STL版本已经不是采用简单的快速排序，而是结合内插排序

算法)。复杂度为n*log(n).stable_sort采用的是\归并排序\，分派足够内存是，其算法复杂度为n*log(n), 否则其复杂度为n*log(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).

局部排序其实是为了减少不必要的操作而提供的排序方式。 其函数原型为： 1) void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);

2) void partial_sort(RandomAccessIterator first,RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);

3) RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first,RandomAccessIterator result_last);

4) RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,

RandomAccessIterator result_first,RandomAccessIterator result_last, Compare comp); 用法使用情况：班上有1000个学生，我想知道分数最低的5名是哪些人。 partial_sort(vect.begin(), vect.begin()+5, vect.end(),less()); 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());

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(\

stable_partition(vect.begin(), vect.end(), bind2nd(less(), exam)); 7. 效率由高到低（耗时由小变大）： partion

stable_partition nth_element

partial_sort sort

stable_sort

8. Effective STL对如何选择排序函数总结的很好：

1) 若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort；

若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选.

若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top

2) n中的内部顺序，nth_element是最理想的；

3) 若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition；

4) 若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。

声明：JavaEye文章版权属于作者，受法律保护。没有作者书面许可不得转载。

本文来源：https://www.bwwdw.com/article/mhpf.html