这两天看了一个比较好的 sort 总结, 所以转载了一下
阅读目录
1.sort
2.sort 简介
3.sort 扩展
1.sort
使用:#include <algorithm>
using namespace std;
作用: 排序
时间复杂度: n*lg(n)
实现原理: sort 并不是简单的快速排序, 它对普通的快速排序进行了优化, 此外, 它还结合了插入排序和推排序. 系统会根据你的数据形式和数据量自动选择合适的排序方法, 这并不是说它每次排序只选择一种方法, 它是在一次完整排序中不同的情况选用不同方法, 比如给一个数据量较大的数组排序, 开始采用快速排序, 分段递归, 分段之后每一段的数据量达到一个较小值后它就不继续往下递归, 而是选择插入排序, 如果递归的太深, 他会选择推排序.
具体函数实现, 请参考: http://www.cnblogs.com/fengcc/p/5256337.html https://www.cnblogs.com/fengcc/p/5256337.html
2.sort 简介
函数声明:
- #include <algorithm>
- template<class RandomIt>
- void sort( RandomIt first, RandomIt last );
- template<class RandomIt, class Compare>
- void sort( RandomIt first, RandomIt last, Compare comp );
形式: sort(first_pointer,first_pointer+n,cmp)
参数解释: 第一个参数是数组的首地址, 一般写上数组名就可以, 因为数组名是一个指针常量. 第二个参数相对较好理解, 即首地址加上数组的长度 n(代表尾地址的下一地址). 最后一个参数是比较函数的名称 (自定义函数 cmp), 这个比较函数可以不写, 即第三个参数可以缺省, 这样 sort 会默认按数组升序排序.
简单例子: 对数组 A 的 0~n-1 元素进行升序排序, 只要写 sort(A,A+n) 即可; 对于向量 V 也一样, sort(v.begin(),v.end()) 即可.
3.sort 扩展
sort 不只是能像上面那样简单的使用, 我们可以对 sort 进行扩展, 关键就在于第三个参数 < cmp 比较函数 >, 我们想降序排列, 或者说我不是一个简简单单的数组, 而是结构体, 类怎么办, 下面给出一些方法和例子.
方法一: 定义比较函数 (最常用)
- // 情况一: 数组排列
- int A[100];
- bool cmp1(int a,int b)//int 为数组数据类型
- {
- return a>b;// 降序排列
- //return a<b;// 默认的升序排列
- }
- sort(A,A+100,cmp1);
- // 情况二: 结构体排序
- Student Stu[100];
- bool cmp2(Student a,Student b)
- {
- return a.id>b.id;// 按照学号降序排列
- //return a.id<b.id;// 按照学号升序排列
- }
- sort(Stu,Stu+100,cmp2);
注: 比较方法也可以放在结构体中或类中定义.
方法二: 使用标准库函数
另外, 其实我们还可以再懒一点, 在标准库中已经有现成的. 它在哪呢? 答案是 functional, 我们 include 进来试试看. functional 提供了一堆基于模板的比较函数对象, 它们是: equal_to<Type>,not_equal_to<Type>,greater<Type>,greater_equal<Type>,Less<Type>,less_equal<Type>. 这些东西的用法看名字就知道了. 在这里, 我么 sort 要用到的也只是 greater 和 Less 就足够了, 用法如下:
升序: sort(begin,end,Less<data-type>())
降序: sort(begin,end,greater<data-type>())
缺点: 也只是实现简单的排序, 结构体不适用.
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <functional>
- using namespace std;
- // 简单使用方法
- sort(A,A+100,greater<int>());// 降序排列
- sort(A,A+100,Less<int>());// 升序排列
方法三: 重载结构体或类的比较运算符
- // 情况一: 在结构体内部重载
- typedef struct Student{
- int id;
- string name;
- double grade;
- bool operator<(const Student& s)
- {
- return id>s.id;// 降序排列
- //return id<s.id;// 升序排列
- }
- };
- vector<Student> V;
- sort(V.begin(),V.end());
- // 情况二: 在外部重载
- vector<Student> V;
- bool operator<(const Student& s1, const Student& s2)
- {
- return s1.id>s2.id;// 降序排列
- //return s1.id<s2.id;// 升序排列
- }
- sort(V.begin(),V.end());
注意: 一定要重载 < 运算符, 因为系统默认是降序, 用的是 < 运算符.
方法四: 声明比较类 (少用)
- struct Less
- {
- bool operator()(const Student& s1, const Student& s2)
- {
- return s1.id<s2.id; // 升序排列
- }
- };
- sort(sutVector.begin(),stuVector.end(),Less());
作者: https://www.cnblogs.com/AlvinZH/
来源: http://www.bubuko.com/infodetail-3465284.html