sort的应用；
1、可以传入两个参数；
sort(a,a+N) ,其中a是数组，a+N表示对a[0]至a[N-1]的N个数进行排序(默认从小到大排序)；
2、传入三个参数；
sort(a,a+N,cmp),第三个参数是一个函数 ；
如果让函数从大到小排序，可以用如下算法实现；
bool cmp(int a,int b){return a>b};
sort(A,A+N,cmp);
分排序函数函数：partial_sort：
例如，你现有一 个包含Widget对象（Widget意为“小挂件”）的vector容器，并且你想把其中质量最好的20个Widget送给你最好的客户，那么你需做的 只是找出这20个质量最好的Widget元素，剩下的并不需关心它们的顺序。这时你需要的是部分排序（相对于全排序）
bool qualityCompare(const Widget& lhs, const Widget& rhs) { // lhs的质量不比rhs的质量差时返回true，否则返回false } … partial_sort (widgets.begin(), // 把质量最好的20元素 widgets.begin() + 20, // 顺序放入widgets容器中 widgets.end(), qualityCompare); … // 使用 widgets
通过调用partial_sort，容器中开始的20个元素就是你需要的质量最好的20个Widget，并按顺序排列，质量排第一的就是 widgets[0], 紧接着就是widgets[1]，依次类推。这样你就可以把质量第一的Widget送给你最好的顾客，质量第二的Widget就可以送给下一个顾客。
如果你只是想把这20个质量最好的Widget礼物送给你最好的20位顾客，而不需要给他们一一对应，partial_sort在这里就有些显得大 材小用了。因为在这里，你只需要找出这20个元素，而不需要对它们本身进行排序。这时你需要的不是partial_sort，而是 nth_element。
nth_element排序算法
只是对一个区间进行排序，一直到你指定的第n个位置上放上正确的元素为止，也就是说，和你进行全排序和 nth_element排序相比，其共同点就是第n个位置是同一个元素。当nth_element函数运行后，在全排序中应该在位置n之后的元素不会出现 在n的前面，应该在位置n前面的元素也不会出现在n的后面。
nth_element (widgets.begin(), // 把质量最好的20元素放在 widgets.begin() + 20, // widgets容器的前面, widgets.end(), // 但并不关心这20个元素 qualityCompare); //本身内部的顺序
partial_sort把前 20个元素还进行排列了，而nth_element并不关系他们内部的顺序。两个算法都实现了同样的功能：把质量最好的20个元素放在vector容器的 开始部分。
nth_element功能却是不少，除了让你找到无关顺序的top n个元素外，它还能找到某个范围的中值，或者找到在某个特定百分点的值。
vector<Widget>::iterator begin(widgets.begin()); // widgets的第一个 vector<Widget>::iterator end(widgets.end()); //和最后一个迭代器 // vector<Widget>::iterator goalPosition; // 需要定位的那个迭代器 //以下代码用来得到质量排在中间的那个元素的迭代器 goalPosition = begin + widgets.size() / 2; // 要找的那个元素应该 //在vector的中部。 nth_element(begin, goalPosition, end, // 找到容器widgets元素的中值 qualityCompare); // … // goalPosition现在指向中值元素 //以下代码用来得到质量排在75%的元素 vector<Widget>::size_type goalOffset = // 计算出要找的值 0.25 * widgets.size(); //离begin迭代器的距离。 // nth_element( begin, begin + goalOffset, end, // 得到质量排在75％的元素 qualityCompare); // … // goalPosition 现在指向质量排在75％的元素。
stable_sort
在一个“稳定”的排序算法中，如果两个元素有相同的值， 它们的相对位置在排序后也会保持不变。例如：如果在未排序时Widget A在Widget B之前，而且都有相同的质量等级，那么“稳定”排序算法就可以保证在排序之后，Widget A仍然在Widget B之前。而非“稳定”排序算法就不能保证这一点。
partial_sort和nth_element都不是“稳定”排序算法，真正的“稳定”排序算法是stable_sort。
#include <algorithm>
stable_sort，因为要对结构体排序，所以要使用该函数的三个参数的重载，例：stable_sort(vectorArray.begin(), vectorArray.end(),myCmp);
partition算法
partition只是给你确定一个区间，把 符合特定条件的元素放到这个区间中。举例来说，要把质量等级好于等于等级2的Widget的元素放在widget容器的前端，我们可以定义一个用于识别 Widget质量等级的函数：
bool hasAcceptableQuality(const Widget& w) { //如果w的质量等于或好于2，返回true，否则返回false } 然后把这个判断函数传递给partion算法： vector<Widget>::iterator goodEnd = // 把所有满足hasAcceptableQuality partition(widgets.begin(), // 条件的放在widgets容器的前面， widgets.end(), // 返回第一个不满足条件的 hasAcceptableQuality); //元素的位置
这样一来，所有在迭代器widgets.begin()和迭代器goodEnd之间的元素都是满足需求的元素：其质量等级好于或等于2。而在 goodEnd 到 widgets.end() 之间的元素的质量等级都会低于质量等级2。如果你对质量等级相同元素的相对位置很关心的话，你可以选择stable_partition算法来代替 partition。
总结：
若需对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排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。正如上面介绍的有几种方式可以 选择。
例子
#include<iostream> #include<vector> #include<iterator> #include<cstdlib> #include<algorithm> #include<functional> using namespace std; bool less5(int a) { return a<5; } int main() { const size_t n=10; int a[10]={3,6,9,2,5,8,1,4,7,0}; vector<int> ive(a,a+n); cout<<"After sort; "; sort(a,a+n); for(int i=0;i<n;++i) cout<<a[i]<<" "; cout<<endl; cout<<"The top 4 number: "<<endl; partial_sort(ive.begin(),ive.begin()+4,ive.end(),greater<int>()); copy(ive.begin(),ive.begin()+4,ostream_iterator<int>(cout," ")); cout<<" The 4th number: "<<endl; nth_element(ive.begin(),ive.begin()+3,ive.end(),greater<int>()); //注意是 ive.begin()+3 cout<<ive[3]; cout<<" The top 4 number: "<<endl; copy(ive.begin(),ive.begin()+4,ostream_iterator<int>(cout," ")); cout<<" The numbers are divided less or greater 5:"<<endl; partition(ive.begin(),ive.end(),less5); copy(ive.begin(),ive.end(),ostream_iterator<int>(cout," ")); cout<<endl; system("pause"); return 0; }