STL提供了好几种算法对区间内的元素排序。出来完全排序外，还支持局部排序。
对所有元素排序
void
sort(RandomAccessIterator beg,RandomAccessIterator end)
void
sort(RandomAccessIterator beg,RandomAccessIteratro end,
BinaryPredicate op)
void
stable_sort(RandomAccessIterator beg,RandomAccessIterator end)
void
stable_sort(RandomAccessIterator beg,RandomAccessIterator end,
BinaryPredicate op)
1.sort()和stable_sort()的上述第一形式，使用operator<对区间[beg,end)内的所有元素进行排序
2.sort()和stable_sort()的上述第二形式，使用判断式op(elem1,elem2)作为排序准则，对区间[beg,end)内的所有元素进行排序
3.sort()和stable_sort()的区别是，后者保证相等元素的原本相对次序在排序后保持不变。
下面这个例子示范sort()的用法
#include "algostuff.hpp"
using namespace std; int main()
{
deque<int> coll;
INSERT_ELEMENTS(coll,,);
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll,"on entry: ");
sort(coll.begin(),coll.end());
PRINT_ELEMENTS(coll,"sorted: ");
sort(coll.begin(),coll.end(),greater<int>());
PRINT_ELEMENTS(coll,"sorted >:");
}
以下程序示范sort()和stable_sort()两者间的区别
#include "algostuff.hpp"
using namespace std; bool lessLength(const string& s1,const string& s2)
{
return s1.length() < s2.length();
} int main()
{
vector<string> coll1;
vector<string> coll2;
coll1.push_back("1xxx");
coll1.push_back("2x");
coll1.push_back("3x");
coll1.push_back("4x");
coll1.push_back("5xx");
coll1.push_back("6xxxx");
coll1.push_back("7xx");
coll1.push_back("8xxx");
coll1.push_back("9xx");
coll1.push_back("10xxx");
coll1.push_back("");
coll1.push_back("");
coll1.push_back("");
coll1.push_back("14xx");
coll1.push_back("");
coll1.push_back("");
coll1.push_back("");
coll2=coll1;
PRINT_ELEMENTS(coll1,"on entry:\n");
sort(coll1.begin(),coll1.end(),lessLength);
stable_sort(coll2.begin(),coll2.end(),lessLength);
PRINT_ELEMENTS(coll1,"\nwith sort():\n");
PRINT_ELEMENTS(coll2,"\nwith stable_sort():\n");
}
局部排序
void
partial_sort(RandomAccessIterator beg,
RandomAccessIterator sortEnd,
RandomAccessIterator end)
void
partial_sort(RandomAccessIterator beg,
RandomAccessIterator sortEnd,
RandomAccessIterator end,
BinaryPredicate op)
1.以上第一形式，以operator<对区间[beg,end)内的元素进行排序，是区间[beg,end)内的元素处于有序状态。
2.以上第二形式，运用二元判断式: op(elem1,elem2)进行局部排序。
以下程序示范partial_sort()的用法
#include "algostuff.hpp"
using namespace std; int main()
{
deque<int> coll;
INSERT_ELEMENTS(coll,,);
INSERT_ELEMENTS(coll,,);
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll);
partial_sort(coll.begin(),coll.begin()+,coll.end());
PRINT_ELEMENTS(coll);
partial_sort(coll.begin(),coll.begin()+,coll.end(),greater<int>());
PRINT_ELEMENTS(coll);
partial_sort(coll.begin(),coll.end(),coll.end());
PRINT_ELEMENTS(coll);
}
RandomAccessIterator
partital_sort_copy(InputIterator sourceBeg,
InputIterator sourceEnd,
RandomAccessIterator destBeg,
RandomAccessIterator destEnd)
RandomAccessIterator
partial_sort_copy(InputIterator sourceBeg,
InputIterator sourceEnd,
RandomAccessIterator destBeg,
RandomAccessIterator destEnd,
BinaryPredicate op)
1.两者都是copy()和partial_sort()的组合
2.它们将元素从源区间[sourceBeg,sourceEnd)复制到目标区间[destBeg,destEnd)，同时进行排序
3.被排序(被复制)的元素数量是源区间和目标区间两者所含元素数量的较少值
以下程序示范partial_sort_copy()的用法
#include <iterator>
#include "algostuff.hpp"
using namespace std; int main()
{
deque<int> coll1;
vector<int> coll6();
vector<int> coll30();
INSERT_ELEMENTS(coll1,,);
INSERT_ELEMENTS(coll1,,);
INSERT_ELEMENTS(coll1,,);
PRINT_ELEMENTS(coll1);
vector<int>::iterator pos6;
pos6=partial_sort_copy(coll1.begin(),coll1.end(),coll6.begin(),coll6.end());
copy(coll6.begin(),pos6,ostream_iterator<int>(cout," "));
cout<<endl;
vector<int>::iterator pos30;
pos30=partial_sort_copy(coll1.begin(),coll1.end(),coll30.begin(),coll30.end(),greater<int>());
copy(coll30.begin(),pos30,ostream_iterator<int>(cout," "));
cout<<endl;
}
根据第n个元素排序
void
nth_element(RandomAccessIterator beg,
RandomAccessIterator nth,
RandomAccessIterator end)
void
nth_element(RandomAccessIterator beg,
RandomAccessIterator nth,
RaddomAccessIterator end,
BinaryPredicate op)
1.两种形式都对区间[beg,end)内的元素进行排序，使第n个位置上的元素就位。也就是说：
所有在位置n之前的元素都小于等于它，所有在位置n之后的元素都大于等于它。
以下程序示范nth_element()的用法
#include "algostuff.hpp"
#include <iterator>
using namespace std; int main()
{
deque<int> coll;
INSERT_ELEMENTS(coll,,);
INSERT_ELEMENTS(coll,,);
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll);
nth_element(coll.begin(),coll.begin()+,coll.end());
cout<<"the four lowest elements are: ";
copy(coll.begin(),coll.begin()+,ostream_iterator<int>(cout," "));
cout<<endl;
}
Heap算法
就排序而言，heap是一种特别的元素组织方式，应用于heap排序法(heapsort)。
heap可被视为一个以序列式群集视作而成的二叉树，具有两大性质：
1.第一个元素总是最大
2.总是能够在对数时间内增加或移除一个元素
关于heapsort，可以查看之前的博客：http://www.cnblogs.com/runnyu/p/4677170.html
为了处理heap，STL提供四种算法
1.make_heap() 将某区间内的元素转化成heap
2.push_heap() 对着heap增加一个元素
3.pop_heap() 对着heap取出下一个元素
4.sort_heap() 将heap转化为一个已序群集(此后它就不再是heap了)
heap算法细节
void
make_heap(RandomAccessIterator beg,
RandomAccessIterator end)
void
make_heap(RandomAccessIterator beg,
RandomAccessIterator end,
BinaryPredicate op)
两种形式都将区间[beg,end)内的元素转化为heap
void
push_heap(RandomAccessIterator beg,RandomAccessIterator end)
void
push_heap(RandomAccessIterator beg,RandomAccessIterator end,
BinaryPredicate op)
两种形式都将end之前的最后一个元素加入原本就是heap的[beg,end-1)区间内，是区间[beg,end)成为一个heap
void
pop_heap(RandomAccessIterator beg,RandomAccessIterator end)
void
pop_heap(RandomAccessIterator beg,RandomAccessIterator end,
BinaryPredicate op)
以上两种形式都将heap[beg,end)内的最高元素，也就是第一元素，移到最后位置，并将剩余区间[beg,end-1)内的元素组织起来成为一个新的heap
void
sort_heap(RandomAccessIterator beg,RandomAccessIterator end)
void
sort_heap(RandomAccessIterator beg,RandomAccessIterator end,
BinaryPredicate op)
两种形式都可以将heap[beg,end)转换为一个已序序列
以下程序示范如何使用各种heap算法
#include "algostuff.hpp"
using namespace std; int main()
{
vector<int> coll;
INSERT_ELEMENTS(coll,,);
INSERT_ELEMENTS(coll,,);
INSERT_ELEMENTS(coll,,);
PRINT_ELEMENTS(coll,"on entry: ");
make_heap(coll.begin(),coll.end());
PRINT_ELEMENTS(coll,"after make_heap(): ");
coll.push_back();
push_heap(coll.begin(),coll.end());
PRINT_ELEMENTS(coll,"after push_heap()");
sort_heap(coll.begin(),coll.end());
PRINT_ELEMENTS(coll,"after sort_heap(): ");
}