《详细解说_STL_排序(Sort)》由会员分享，可在线阅读，更多相关《详细解说_STL_排序(Sort)（13页珍藏版）》请在金锄头文库上搜索。
1、详细解说 STL 排序(Sort) o0 前言: STL，为什么你必须掌握 o1 STL 提供的 Sort 算法 1.1 所有 sort 算法介绍 1.2 sort 中的比较函数 1.3 sort 的稳定性 1.4 全排序 1.5 局部排序 1.6 nth_element 指定元素排序 1.7 partition 和 stable_partition o2 Sort 和容器 o3 选择合适的排序函数 o4 小结 o5 参考文档 一切复杂的排序操作，都可以通过 STL 方便实现 ! 0 0 前言前言: : STLSTL ，为什么你必须掌握，为什么你必须掌握对于程序员来说，数据结构是必修的一门课。
2、从查找到排序，从链表到二叉树， 几乎所有的算法和原理都需要理解，理解不了也要死记硬背下来。幸运的是这 些理论都已经比较成熟，算法也基本固定下来，不需要你再去花费心思去考虑 其算法原理，也不用再去验证其准确性。不过，等你开始应用计算机语言来工 作的时候，你会发现，面对不同的需求你需要一次又一次去用代码重复实现这 些已经成熟的算法，而且会一次又一次陷入一些由于自己疏忽而产生的 bug 中。 这时，你想找一种工具，已经帮你实现这些功能，你想怎么用就怎么用，同时 不影响性能。你需要的就是 STL, 标准模板库！ 西方有句谚语：不要重复发明轮子！STL 几乎封装了所有的数据结构中的算法，从链表到队列，从
3、向量到堆栈，对 hash 到二叉树，从搜索到排序，从增加到删除.可以说，如果你理解了 STL，你会发现你已不用拘泥于算法本身，从而站在巨人的肩膀上去考虑更高级 的应用。排序是最广泛的算法之一，本文详细介绍了 STL 中不同排序算法的用法和区别。1 1 STLSTL 提供的提供的 SortSort 算法算法C+之所以得到这么多人的喜欢，是因为它既具有面向对象的概念，又保持了 C 语言高效的特点。STL 排序算法同样需要保持高效。因此，对于不同的需求， STL 提供的不同的函数，不同的函数，实现的算法又不尽相同。 1.11.1 所有所有 sortsort 算法介绍算法介绍所有的 sort 算法的参
4、数都需要输入一个范围，begin, end)。这里使用的迭代 器(iterator)都需是随机迭代器(RadomAccessIterator), 也就是说可以随机访 问的迭代器，如：it+n 什么的。（partition 和 stable_partition 除外） 如果你需要自己定义比较函数，你可以把你定义好的仿函数(functor)作为参数 传入。每种算法都支持传入比较函数。以下是所有 STL sort 算法函数的名字列 表: 函数名函数名功能描述功能描述sort对给定区间所有元素进行排序stable_sort对给定区间所有元素进行稳定排序partial_sort对给定区间所有元素部分排序
5、partial_sort_copy对给定区间复制并排序 nth_element找出给定区间的某个位置对应的元素is_sorted判断一个区间是否已经排好序partition使得符合某个条件的元素放在前面stable_partition相对稳定的使得符合某个条件的元素放在前面其中 nth_element 是最不易理解的，实际上，这个函数是用来找出第几个。例 如：找出包含 7 个元素的数组中排在中间那个数的值，此时，我可能不关心前 面，也不关心后面，我只关心排在第四位的元素值是多少。1.21.2 sortsort 中的比较函数中的比较函数当你需要按照某种特定方式进行排序时，你需要给 sort 指定
6、比较函数，否则程 序会自动提供给你一个比较函数。 vector vect; /. sort(vect.begin(), vect.end(); /此时相当于调用 sort(vect.begin(), vect.end(), less() );上述例子中系统自己为 sort 提供了 less 仿函数。在 STL 中还提供了其他仿函 数，以下是仿函数列表: 名称名称 功能描述功能描述 equal_to相等not_equal_to不相等less小于名称名称 功能描述功能描述 greater大于less_equal小于等于greater_equal大于等于 需要注意的是，这些函数不是都能适用于你的 s
7、ort 算法，如何选择，决定于你 的应用。另外，不能直接写入仿函数的名字，而是要写其重载的()函数： less() greater() 当你的容器中元素时一些标准类型（int float char)或者 string 时，你可以 直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式 排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载 类型的 #include #include #include using namespace std;class myclass public:myclass(int a, int b):first(a), second(b)in
8、t first;int second;bool operator vect;for(int i = 0 ; i void sort(RandomAccessIterator first, RandomAccessIterator last);template void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);template void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
9、;template void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);在第 1，3 种形式中，sort 和 stable_sort 都没有指定比较函数，系统会默认 使用 operator#include #include #include #include using namespace std;class studentpublic:student(const string int score;bool operator vect;student s
10、t1(“Tom“, 74);vect.push_back(st1);st1.name=“Jimy“;st1.score=56;vect.push_back(st1);st1.name=“Mary“;st1.score=92;vect.push_back(st1);st1.name=“Jessy“;st1.score=85;vect.push_back(st1);st1.name=“Jone“;st1.score=56;vect.push_back(st1);st1.name=“Bush“;st1.score=52;vect.push_back(st1);st1.name=“Winter“;st
11、1.score=77;vect.push_back(st1);st1.name=“Andyer“;st1.score=63;vect.push_back(st1);st1.name=“Lily“;st1.score=76;vect.push_back(st1);st1.name=“Maryia“;st1.score=89;vect.push_back(st1);cout();cout void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);temp
12、late void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);template RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);template R
13、andomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);理解了 sort 和 stable_sort 后，再来理解 partial_sort 就比较容易了。先看 看其用途: 班上有 10 个学生，我想知道分数最低的 5 名是哪些人。如果没有 partial_sort，你就需要用 sort 把所有人排好序，然后再取前 5 个。现在你
14、只 需要对分数最低 5 名排序，把上面的程序做如下修改： stable_sort(vect.begin(), vect.end(),less(); 替换为： partial_sort(vect.begin(), vect.begin()+5, vect.end(),less();输出结果为： -before sort. Tom: 74 Jimy: 56 Mary: 92 Jessy: 85 Jone: 56 Bush: 52Winter: 77 Andyer: 63 Lily: 76 Maryia: 89 -after sort . Bush: 52 Jimy: 56 Jone: 56 And
15、yer: 63 Tom: 74 Mary: 92 Jessy: 85 Winter: 77 Lily: 76 Maryia: 89 这样的好处知道了吗？当数据量小的时候可能看不出优势，如果是 100 万学生， 我想找分数最少的 5 个人. partial_sort 采用的堆排序（heapsort），它在任何情况下的复杂度都是 n*log(n). 如果你希望用 partial_sort 来实现全排序，你只要让 middle=last 就可以了。partial_sort_copy 其实是 copy 和 partial_sort 的组合。被排序(被复制)的 数量是first, last)和resul
16、t_first, result_last)中区间较小的那个。如 果result_first, result_last)区间大于first, last)区间，那么 partial_sort 相当于 copy 和 sort 的组合。1.61.6 nth_elementnth_element 指定元素排序指定元素排序nth_element 一个容易看懂但解释比较麻烦的排序。用例子说会更方便： 班上有 10 个学生，我想知道分数排在倒数第 4 名的学生。 如果要满足上述需求，可以用 sort 排好序，然后取第 4 位（因为是由小到大排),更聪明的朋友会用 partial_sort, 只排前 4 位，然后得到第 4 位。其实这是 你还是浪费，因为前两位你根本没有必要排序，此时，你就需要 nth_element: templ
