详细解说 stl 排序(sort)-ag真人游戏

其输出是：

------before sort... tom: 74 jimy: 56 mary: 92 jessy: 85 jone: 56 bush: 52 winter: 77 andyer: 63 lily: 76 maryia: 89 -----after sort .... bush: 52 jimy: 56 jone: 56 andyer: 63 tom: 74 lily: 76 winter: 77 jessy: 85 maryia: 89 mary: 92sort采用的是成熟的"快速排序算法"(目前大部分stl版本已经不是采用简单的快速排序，而是结合内插排序算法)。

注1

，可以保证很好的平均性能、复杂度为n*log(n)，由于单纯的快速排序在理论上有最差的情况，性能很低，其算法复杂度为n*n，但目前大部分的stl版本都已经在这方面做了优化，因此你可以放心使用。stable_sort采用的是"归并排序"，分派足够内存是，其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n)，其优点是会保持相等元素之间的相对位置在排序前后保持一致。

1.5 局部排序

局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为：

template <class randomaccessiterator> void
partial_sort(randomaccessiterator first, randomaccessiterator middle, randomaccessiterator last); template <class randomaccessiterator, class strictweakordering> void
partial_sort(randomaccessiterator first, randomaccessiterator middle, randomaccessiterator last, strictweakordering comp); template <class inputiterator, class randomaccessiterator>

randomaccessiterator partial_sort_copy(inputiterator first, inputiterator last, randomaccessiterator result_first, randomaccessiterator result_last); template 

<class inputiterator, class
randomaccessiterator, class strictweakordering>

randomaccessiterator 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个。现在你只需要对分数最低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: 52 winter: 77 andyer: 63 lily: 76 maryia: 89 -----after sort .... bush: 52 jimy: 56 jone: 56 andyer: 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)和[result_first, result_last)中区间较小的那个。如果[result_first, result_last)区间大于[first, last)区间，那么partial_sort相当于copy和sort的组合。

1.6 nth_element 指定元素排序

nth_element一个容易看懂但解释比较麻烦的排序。用例子说会更方便：
班上有10个学生，我想知道分数排在倒数第4名的学生。
如果要满足上述需求，可以用sort排好序，然后取第4位（因为是由小到大排), 更聪明的朋友会用partial_sort, 只排前4位，然后得到第4位。其实这是你还是浪费，因为前两位你根本没有必要排序，此时，你就需要nth_element:

template <class randomaccessiterator> void
nth_element(randomaccessiterator first, randomaccessiterator nth, randomaccessiterator last); template <class randomaccessiterator, class strictweakordering> void

 nth_element(randomaccessiterator first, randomaccessiterator nth, randomaccessiterator last, strictweakordering comp);

对于上述实例需求，你只需要按下面要求修改1.4中的程序：

stable_sort(vect.begin(), vect.end(),less());

替换为：

nth_element(vect.begin(), vect.begin() 3, vect.end(),less());

运行结果为：

------before sort... tom: 74 jimy: 56 mary: 92 jessy: 85 jone: 56 bush: 52 winter: 77 andyer: 63 lily: 76 maryia: 89 -----after sort .... jone: 56 bush: 52 jimy: 56 andyer: 63 jessy: 85 mary: 92 winter: 77 tom: 74 lily: 76 maryia: 89 第四个是谁？andyer，这个倒霉的家伙。

1.7 partition 和stable_partition

好像这两个函数并不是用来排序的，'分类'算法，会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为：

template <class forwarditerator, class predicate>

forwarditerator partition(forwarditerator first, forwarditerator last, predicate pred) template 

<class forwarditerator, class predicate>

forwarditerator stable_partition(forwarditerator first, forwarditerator last, predicate pred);

看看应用吧：班上10个学生，计算所有没有及格（低于60分）的学生。你只需要按照下面格式替换1.4中的程序：

stable_sort(vect.begin(), vect.end(),less());

替换为：

student exam("pass", 60
); stable_partition(vect.begin(), vect.end(), bind2nd(less(), exam));

其输出结果为：------before sort... tom: 74 jimy: 56 mary: 92 jessy: 85 jone: 56 bush: 52 winter: 77 andyer: 63 lily: 76 maryia: 89 -----after sort .... jimy: 56 jone: 56 bush: 52 tom: 74 mary: 92 jessy: 85 winter: 77 andyer: 63 lily: 76 maryia: 89而且使用的是stable_partition, 元素之间的相对次序是没有变。

2 sort 和容器

stl中标准容器主要vector, list, deque, string, set, multiset, map, multimay， 其中set, multiset, map, multimap都是以树结构的方式存储其元素详细内容请参看：学习stl map, stl set之数据结构基础. 因此在这些容器中，元素一直是有序的。

这些容器的迭代器类型并不是随机型迭代器，因此，上述的那些排序函数，对于这些容器是不可用的。上述sort函数对于下列容器是可用的：

• vector
• string
• deque

如果你自己定义的容器也支持随机型迭代器，那么使用排序算法是没有任何问题的。

对于list容器，list自带一个sort成员函数list::sort()。它和算法函数中的sort差不多，但是list::sort是基于指针的方式排序，也就是说，所有的数据移动和比较都是此用指针的方式实现，因此排序后的迭代器一直保持有效（vector中sort后的迭代器会失效)。

3 选择合适的排序函数

为什么要选择合适的排序函数？可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小， 因此你觉得随便用哪个函数都无关紧要。其实不然，即使你不关心效率，如果你选择合适的排序函数，你会让你的代码更容易让人明白，你会让你的代码更有扩充性，逐渐养成一个良好的习惯，很重要吧。

如果你以前有用过c语言中的qsort, 想知道qsort和他们的比较，那我告诉你，qsort和sort是一样的，因为他们采用的都是快速排序。从效率上看，以下几种sort算法的是一个排序，效率由高到低（耗时由小变大）：

1. partion
2. stable_partition
3. nth_element
4. partial_sort
5. sort
6. stable_sort

记得，以前翻译过effective stl的文章，其中对如何选择排序函数总结的很好：

• a、若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort；
• b、若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选.
• c、若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序，nth_element是最理想的；
• d、若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition；
• e、若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。正如上面介绍的有几种方式可以选择。

总之记住一句话： 如果你想节约时间，不要走弯路, 也不要走多余的路!

4 小结

讨论技术就像个无底洞，经常容易由一点可以引申另外无数个技术点。因此需要从全局的角度来观察问题，就像观察stl中的sort算法一样。其实在stl还有make_heap, sort_heap等排序算法。本文章没有提到。本文以实例的方式，解释了stl中排序算法的特性，并总结了在实际情况下应如何选择合适的算法。