STL排序算法

简介: STL中有多种排序算法,各有各的适用范围,下面听我一一道来: I、完全排序 sort() 首先要隆重推出的当然是最最常用的sort了,sort有两种形式,第一种形式有两个迭代器参数,构成一个前开后闭的区间,按照元素的 less 关系排序;第二种形式多加一个指定排序准则的谓词。

 

STL中有多种排序算法,各有各的适用范围,下面听我一一道来:

I、完全排序

  1. sort()

首先要隆重推出的当然是最最常用的sort了,sort有两种形式,第一种形式有两个迭代器参数,构成一个前开后闭的区间,按照元素的 less 关系排序;第二种形式多加一个指定排序准则的谓词。sort基本是最通用的排序函数,它使用快速排序算法,并且在递归过程中,当元素数目小于一个阈值(一般是16,我的试验是24)时,转成直接插入排序。伟大的数学家Knuth已经证明,在平均意义上,快速排序是最快的了;当然,最坏复杂性比较差。sort要求随机迭代器,因此对于很多编译器来说,对于前向迭代器(如list)使用sort是一个编译错误。

#include <vector> 
#include <algorithm> 
#include <functional> 
#include <cstdlib> 
  
using namespace std; 
  
void func1() 
{ 
    vector<int> ar; 
    //向数组里面插入一些随机数 
    generate_n(back_inserter(ar), 100, rand); 
    //按从小到大排序 
    sort(ar.begin(), ar.end()); 
} 

/*
list<int> l1;
fill_n(back_inserter(l1), 200, 1000);
*/

如何从大到小逆排序,这个其实有很多种方式实现。

 1 void func2() 
 2 { 
 3     vector<int> ar; 
 4     //向数组里面插入一些随机数 
 5     generate_n(back_inserter(ar), 100, rand); 
 6   
 7     //方法1:使用函数作为谓词 
 8     sort(ar.begin(), ar.end(), GreateThan); 
 9     //方法2:使用仿函数作为谓词 
10     //注意下面两种方法都需要有个括号,实际上是要产生一个临时对象 
11     sort(ar.begin(), ar.end(), CompareInt()); 
12     //方法3:使用预定义的Adapter, 定义在 <functional> 中 
13     sort(ar.begin(), ar.end(), greater<int>()); 
14     //方法4:正常排序,然后翻转过来 
15     sort(ar.begin(), ar.end()); 
16     reverse(ar.begin(), ar.end()); 
17     //方法5:使用逆迭代器 
18     sort(ar.rbegin(), ar.rend()); 
19 } 

1.stable_sort

sort优点一大堆,一个缺点就是它不是一种稳定的排序。什么是排序的稳定性?就是如果出现两个元素相等时,要求排序之后他们之间保持原来的次序(比如我们先按学号排序,然后按成绩排序,这时就希望成绩相同的还是按照学号的次序排)。很可惜,快速排序算法就不是稳定的,要追求这个,只好用stable_sort了。

在各种排序算法中,合并排序是稳定的,但一般的合并排序需要额外的O(N)的存储空间,而这个条件不是一定能够满足的(可能是比较奢侈的)。所以在stable_sort内部,首先判断是否有足够的额外空间(如vector中的capcity()部分),有的话就使用普通合并函数,总的时间复杂性和快速排序一个数量级,都是O(N*logN)。如果没有额外空间,使用了一个merge_without_buffer的关键函数进行就地合并(如何实现是比较有技巧的,完全可以专门谈一谈),这个合并过程不需要额外的存储空间(递归的堆栈除外),但时间复杂度变成O(N*logN),这种情况下,总的stable_sort时间复杂度是O(N*logN*logN)。

总之,stable_sort稍微慢一点儿,但能够保证稳定,使用方法和sort一样。但很多时候可以不用这种方式和这个函数,比如上面的例子,完全可以在排序比较准则中写入成绩和学号两个条件就OK了。

2.sort_heap

堆排序也是一种快速的排序算法,复杂度也是O(N*logN)。STL中有一些和堆相关的函数,能够构造堆,如果在构造好的堆上每次取出来根节点放在尾部,所有元素循环一遍,最后的结果也就有序了。这就是sort_heap了。它的使用要求区间已经被构造成堆,如:

 1 void func5() 
 2 { 
 3     vector<int> ar; 
 4     //生成数据 
 5     generate_n(back_inserter(ar), 100, rand); 
 6     //构造堆 
 7     make_heap(ar.begin(), ar.end()); 
 8     //堆排序 
 9     sort_heap(ar.begin(), ar.end()); 
10 } 

3.list.sort

对于list容器,是不能直接使用sort的(包括stable_sort),从技术的角度来说,sort要求随机迭代器;从算法的角度来说,list这种链表结构本身就不适合用快速排序。因此,list容器内部实现了专门的sort算法,这个算法采用的是合并排序,应该是稳定的(不确定)。如:

list<int> li; 
    li.sort(); 

 

4.其他

优先队列(priority_queue)每次弹出的都是max值。实际上就是heap的一个容器方式的包装。

关联式容器自身就必须是有序的(针对key),对其迭代时,key是递增的。

 

II、部分排序

这些部分排序功能能够完成一段数据(而不是所有)的排序,在适当的适合使用可以节省计算量。用的人不多,可能了解的也比较少。

  1. partial_sort(), partial_sort_copy()

  这两个函数能够将整个区间中给定数目的元素进行排序,也就是说,结果中只有最小的M个元素是有序的。你当然也可以使用sort,区别就在于效率。如果M显著地小于N,时间就比较短;当然M太小了也不好,那      还不如挨个找最小值了。partial_sort接受三个参数,分别是区间的头,中间和结尾。执行后,将前面M(M=中间-头)个元素有序地放在前面,后面的元素肯定是比前面的大,但他们内部的次序没有保证。partial_sort_copy的区别在于  把结果放到另外指定的迭代器区间中:

 1 void func6() 
 2 { 
 3     int ar[12]={69,23,80,42,17,15,26,51,19,12,35,8}; 
 4     //只排序前7个数据 
 5     partial_sort(ar, ar+7, ar+12); 
 6     //结果是 8 12 15 17 19 23 26 80 69 51 42 35,后5个数据次序不定,依赖于实现 
 7     vector<int> res(7); 
 8     //前7项排序后放入res 
 9     partial_sort_copy(ar, ar+7, res.begin(), res.end(), greater<int>() ); 
10 } 

这两个函数的实现使用的是堆的方法,先将前M个元素构造成堆,然后挨个检查后面的元素,看看是否小于堆的最大值,是的话就彼此交换,然后重排堆;最后将前面已经是最小的M个元素构成的堆作一次sort_heap就可以了。算法的复杂度差不多是O(N*logM)

  1. nth_element

  这个函数只真正排序出一个元素来,就是第n个。函数有三个迭代器的输入(当然还可以加上一个谓词),执行完毕后,中间位置指向的元素保证和完全排序后这个位置的元素一致,前面区间的元素都小于(精确地说,是不大于)后面区间的元素。

熟悉快速排序的马上就能发现,这实际上是一个按位置划分的算法。STL的规范中要求此函数的平均复杂度是线性的,和快速排序一样,这种算法的最坏复杂度比较差。在一般的实现(如SGI)中,采用三种取1的方法寻找划分元素,最坏复杂度是O(N^N)。虽然理论上有一些算法可以保证最坏线性复杂度,但算法过于复杂,STL一般也不采用。

III、排序辅助功能

  1. partition, stable_partition
  2. merge, inplace_merge

IV、有序区间操作

这个准备单独写一篇

 

 

目录
相关文章
|
7月前
|
算法 搜索推荐 C++
【C++STL基础入门】vector运算和遍历、排序、乱序算法
【C++STL基础入门】vector运算和遍历、排序、乱序算法
|
2月前
|
存储 算法 JavaScript
【C++ 泛型编程 入门篇】 C++ 中的泛型算法 STL(sort,find)(二)
【C++ 泛型编程 入门篇】 C++ 中的泛型算法 STL(sort,find)
32 0
|
2月前
|
算法 搜索推荐 程序员
【C++ 泛型编程 入门篇】 C++ 中的泛型算法 STL(sort,find)(一)
【C++ 泛型编程 入门篇】 C++ 中的泛型算法 STL(sort,find)
39 0
|
3月前
|
存储 算法 搜索推荐
C++模板与STL【常用算法】
C++模板与STL【常用算法】
|
3月前
|
算法 C++ 容器
【C++】 --- STL常用算法总结(三)
【C++】 --- STL常用算法总结
27 0
|
3月前
|
存储 算法 搜索推荐
【C++】 --- STL常用算法总结(二 )
【C++】 --- STL常用算法总结
37 0
|
3月前
|
算法 C++ 容器
【C++】 --- STL常用算法总结(一)
【C++】 --- STL常用算法总结
34 0
|
9月前
|
算法 安全 搜索推荐
7.1 C++ STL 非变易查找算法
C++ STL 中的非变易算法(Non-modifying Algorithms)是指那些不会修改容器内容的算法,是C++提供的一组模板函数,该系列函数不会修改原序列中的数据,而是对数据进行处理、查找、计算等操作,并通过迭代器实现了对序列元素的遍历与访问。由于迭代器与算法是解耦的,因此非变易算法可以广泛地应用于各种容器上,提供了极高的通用性和灵活性。
34 0
|
9月前
|
算法 容器
C++STL算法篇之集合算法
C++STL算法篇之集合算法
|
9月前
|
算法
C++STL算法篇之查找算法(下)
C++STL算法篇之查找算法(下)