本文共 2166 字,大约阅读时间需要 7 分钟。
STL各种排序
//By skywind STL中有多种排序算法,各有各的适用范围,下面听我一一道来: I、完全排序 1.sort() 首先要隆重推出的当然是最最常用的sort了,sort有两种形式,第一种形式有两个迭代器参数,构成一个前开后闭的区间,按照元素的 less 关系排序;第二种形式多加一个指定排序准则的谓词。sort基本是最通用的排序函数,它使用快速排序算法,并且在递归过程中,当元素数目小于一个阈值(一般是16,我的试验是24)时,转成直接插入排序。伟大的数学家Knuth已经证明,在平均意义上,快速排序是最快的了;当然,最坏复杂性比较差。sort要求随机迭代器,因此对于很多编译器来说,对于前向迭代器(如list)使用sort是一个编译错误。(不过,在vc2005里面,这个错误信息实在很糟糕) sort的基本使用方式如下: PLAIN TEXT C++:#include#include #include #include using namespace std; void func1(){ vector ar; //向数组里面插入一些随机数 generate_n(back_inserter(ar), 100, rand); //按从小到大排序 sort(ar.begin(), ar.end());}
经常有人问如何从大到小逆排序,这个其实有很多种方式实现,如下面的例子:
PLAIN TEXT C++:`void func2() { vector ar; //向数组里面插入一些随机数 generate_n(back_inserter(ar), 100, rand);//方法1:使用函数作为谓词
sort(ar.begin(), ar.end(), GreateThan);
//方法2:使用仿函数作为谓词 //注意下面两种方法都需要有个括号,实际上是要产生一个临时对象 sort(ar.begin(), ar.end(), CompareInt()); //方法3:使用预定义的Adapter, 定义在 中 sort(ar.begin(), ar.end(), greater()); //方法4:正常排序,然后翻转过来 sort(ar.begin(), ar.end()); reverse(ar.begin(), ar.end()); //方法5:使用逆迭代器 sort(ar.rbegin(), ar.rend()); }`最后一种方法是我比较欣赏的,可以不能直接对原生数组使用,也就是说,如果ar的定义是int ar[MAXN],上面其他的排序算法都可以简单的改成sort(ar, ar+MAXN, …),但最后一个不行,要用另外一种比较丑陋的方式:
PLAIN TEXT C#include void func3(){ int ax[5]={1,3,4,5,2}; sort(reverse_iterator1.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 res(7);8. //前7项排序后放入res9. partial_sort_copy(ar, ar+7, res.begin(), res.end(), greater () );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、有序区间操作 这个准备单独写一篇转载地址:http://npxgi.baihongyu.com/