STl中的排序算法

浏览数：15 / 时间：2015年06月08日

本文转自：STl中的排序算法

1. 所有STL sort算法函数的名字列表:

函数名　　　　　　　　　功能描述

sort 　　　　　　　对给定区间所有元素进行排序

stable_sort 　　　　对给定区间所有元素进行稳定排序

partial_sort 　　　　对给定区间所有元素部分排序

partial_sort_copy 对给定区间复制并排序

nth_element 　　　找出给定区间的某个位置对应的元素

is_sorted 判断一个区间是否已经排好序

partition 　　　　使得符合某个条件的元素放在前面

stable_partition 相对稳定的使得符合某个条件的元素放在前面

2. 比较函数：

当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数

vector < int > vect;

sort(vect.begin(), vect.end());//此时相当于调用

sort(vect.begin(), vect.end(), less<int>() );

sort 中的其他比较函数

equal_to 相等

not_equal_to 不相等

less 小于

greater 大于

less_equal 小于等于

greater_equal 大于等于

上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表: 不能直接写入仿函数的名字，而是要写其重载的()函数： less<int>();

当你的容器中元素时一些标准类型（int float char)或者string时，你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序，你可以有两种方法来达到效果：一种是自己写比较函数。另一种是重载类型的‘<‘操作赋。

3. 全排序：

全排序即把所给定范围所有的元素按照大小关系顺序排列。sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序，而是结合内插排序算法)。复杂度为n*log(n)。stable_sort采用的是"归并排序"，分派足够内存时，其算法复杂度为n*log(n), 否则其复杂度为n*log(n)*log(n)，其优点是会保持相等元素之间的相对位置在排序前后保持一致。

用于全排序的函数有：

1.void sort(RandomAccessIterator first, RandomAccessIterator last);

2.void sort(RandomAccessIterator first, RandomAccessIterator last,StrictWeakOrdering comp);

3.void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

4.void stable_sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

4. 局部排序：

partial_sort采用的堆排序（heapsort），它在任何情况下的复杂度都是n*log(n)。

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

其函数原型为：

4.1 void partial_sort(RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);

4.2 void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last, StrictWeakOrdering comp);

4.3 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last);

4.4 RandomAccessIterator partial_sort_copy(InputIterator first, InputIteratorlast,RandomAccessIteratorresult_first,RandomAccessIterator result_last, Compare comp);

例如：班上有1000个学生，我想知道分数最低的5名是哪些人。

partial_sort(vect.begin(),vect.begin()+5,vect.end(),less<student>());

5. nth_element 指定元素排序

5.1 void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

5.2 void nth_element(RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last,

StrictWeakOrdering comp);

例如：班上有1000个学生，我想知道分数排在倒数第4名的学生。

nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

6. partition 和stable_partition

partition就是把一个区间中的元素按照某个条件分成两类，并没有排序。

其函数原型为：

6.1 ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)