STL排序函数

标准模板库（STL）在库头文件<algorithm>中提供了几个排序函数。STL类List就有自己的内置的sort函数。对容器来说，List的sort函数比一般的排序算法快，因为它对列表进行了优化，而且是交换指针，不是复制对象。在排序双向队列、字符串、数组、或矢量时，使用一般的sort函数，注意这个sort函数不稳定，值相同的元素不能保证处于相同的顺序位置上，为此应使用stable_sort函数。只有在需要对一个区域的元素进行排序或分区时，其他排序算法才比较高效，如果只需要对一定区域的元素进行排序，可以使用partial_sort。该区域在参数中指定，partial_sort_copy函数会生成一个容器，其中包含指定区域的元素。Nth_element 函数可以对一定区域的元素进行部分排序，但只能保证第n个元素是分界点。在数组中第n个元素左边的所有元素会小于或等于第n 个,第n个元素右边的所有元素则大于第n个元素的值。注意在任意顺序中都不需要指定区域。Nth_element函数用于确定中间点或百分点。
在根据某个条件对元素进行排序时，不是像nth_element函数那样对前n个元素排序，而是使用partion或stable_parition函数代替nth_element函数。这两个函数把容器分成两个区域，第一个区域包含满足特定条件的元素，第二个区域包含不满足特定条件的元素。最后，<algorithm>还包含merge和inplace_merge函数。但是，这两个函数都把已排序的区域作为参数，所以他们仅执行归并排序的一次调用。函数partition或stable_partition要求使用双向迭代器，而其他STL排序函数要求使用随机访问的迭代器。函数的规范如下所示。注意每个函数都有附加参数来确定排序的顺序，默认的比较运算符<。

void sort(RandomIter first,RandomIter last);
void sort(RandomIter first,RandomIter last,Compare cmp);
//Sorts first to last into ascending order by default
//A comparison function object may be supplied

void stable_sort(RandomIter first,RandomIter last);
void stable_sort(RandomIter first,RandomIter last ,Compare cmp);
//Sorts first to last into ascending order by fefault
//A comparison function object may be supplied
//Perserves original ordering of equivalent elements

void partial_sort(RandomIter first,RandomIter middle,RandomIter last);
void partial_sort(RandomIter first,RandomIter middle,RandomIter last,Compare cmp);
//Sorts the number of elements from first to last
//and places them in the range from first to middle
//Elements from middle to last are not ordered
//Default sort is in ascending order
//A comparison function object may be supplied

RandomIter partial_sort_copy(InputIter first,Input last,RandomIter first2,
		RandomIter last2);
RandomIter partial_sort_copy(InputIter first,Input last,RandomIter first2,
		RandomIter last2,Compare cmp);
//Sorts the number of elements from first to last
//and copies them into a comtainer in the rang from
//first2 to last2.
//default sort is in asending order
//A comparison function object may be supplied

void nth_element(RandomIter first,RandomIter nth,RandomIter last);
void nth_element(RandomIter first,RandomIter nth,RandomIter last,Compare cmp);
//the nth element becomes a dividing point for the container
//The range from first to nth ans nth to last are not sorted
//all elements from the first to nth are less than or equal to nth;
//all elements from the nth to last are greater than nth;
//A comparison function object may be supplied

BiIter partition(BiIter first,BiIter last,Predicate p);
//the container is partitioned to place all elements that
//satisfy a particular predicate predicate p before every element that
//does not satisfy the predicate p.
//the two ranges are not sorted
//the return iterator points to either the first element that
//does not satisfy the predicate p or the end;
//Relative order of equivalent elements is not maintained

BiIter stable_partition(BiIter first,BiIter last,Predicate p);
//the container is partitioned to place all elements that
//satisfy a particular predicate p before every element that
//the two ranges are not sorted
//the return iterator points to either the first element that
//dosnot satisfy the predicate p or the end
//relative order of equivalent elements is maintained
OutputIter merge(InputIter first ,InputIter last,InputIter first2,
		InputIter last2,OutputIter res);
OutputIter merge(InputIter first,InputIter last,InputIter first2,
		InputIter last2,OutputIter res,Compare cmp);
//Takes two sorted ranges and merges them into anoter sorted container
//A comparison function object may be supplied
//For equivalent elements ,elements from the first range
//will orecede elements from the second

void inplace_merge(BiIter first,BiIter middle,BiIter last);
void inplace_merge(BiIter first ,BiIter middle ,BiIter last,Compare cmp);
//Takes two sorted ranges and merges them in place
//the two ranges are first to middle and middle to last
//A comparison function object may be supplied
//For equivalent elements,elements from the first range 
//will orecede elements from the second.