『ACM C++』HDU杭电OJ | 1425 - sort （排序函数…
2019-02-25 16:09:31来源：博客园 阅读 ()
今天真的是累哭了，周一课从早八点半一直上到晚九点半，整个人要虚脱的感觉，因为时间不太够鸭所以就回头看看找了一些比较有知识点的题来总结总结分析一下，明天有空了就开始继续打题，嘻嘻嘻。
今日兴趣电影：
《超能查派》
这是一部关于未来人工智能的一个故事，感觉特别有思维开拓性，一个程序员写出了真正的AI智能机器人，可以从婴儿开始学习，然后以极快极强的学习速度不断成长，最后拯救身边人的故事。很感人，强烈推荐哈哈~
爱奇艺：https://www.iqiyi.com/v_19rroly1wo.html?flashvars=videoIsFromQidan%3Ditemviewclkrec#vfrm=5-7-0-1
------------------------------------------------题目----------------------------------------------------------
Sort
Problem Description
Input
Output
Sample Input
5 3 3 -35 92 213 -644
Sample Output
213 92 3
------------------------------------------------题目----------------------------------------------------------
（一） 题目分析：
题目其实很简单，直接使用sort函数就可以了，没有太多的想法，特别地方就是对sort的排序规则进行自定义而已。这题没必要用什么冒泡啊快排了，只是巩固sort的用法，而今天这篇文章就对sort函数进行研究。
（二）代码分块：
第一步：先规定sort的排序规则：
bool cmp(long long int a,long long int b){ return a>b; }
第二步：使用sort排序再输出即可：
sort(num,num+N,cmp); for(i = 0;i<M;i++) { if(i<M-1) printf("%lld ",num[i]); else{ printf("%lld\n",num[i]); break; } }
（三）AC代码：
#include<stdio.h> #include <algorithm> using namespace std; long long int num[1000005]; long long int N,M,i; bool cmp(long long int a,long long int b){ return a>b; } int main() { while(~scanf("%lld%lld",&N,&M)) { for(i = 0;i<N;i++) scanf("%lld",&num[i]); sort(num,num+N,cmp); for(i = 0;i<M;i++) { if(i<M-1) printf("%lld ",num[i]); else{ printf("%lld\n",num[i]); break; } } } return 0; }
（四）AC截图：
（五）解后分析：
这里想要总结一下sort一些特殊用法，所以就把sort完完整整的说一遍吧~当作对自己的复习嘻嘻嘻。
A、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 );
时间复杂度：n*log10(n)
实现原理：除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。
（参考：http://www.cnblogs.com/fengcc/p/5256337.html）
函数原型：sort(first_pointer,first_pointer+n,cmp)
注意：当cmp不写时，默认是升序排序。
B、自定义cmp比较函数的使用方法：
（1）数组排序自定义：
在本题中，就使用了数组排序的自定义化，核心代码：
int A[1000]; bool cmp(int a,int b)//int为数组数据类型 { return a>b;//降序排列 } sort(A,A+1000,cmp);
（2）结构排序自定义：
这个自定义也是经常遇到的，因为经常要做线性表的一个插入删除排序查找工作，核心代码：
Student stu[1000]; bool cmp(Student a,Student b) { return a.id>b.id;//按照学号降序排列 } sort(Stu,Stu+1000,cmp);
核心就在return处进行细微的修改处理啦~同理应该能够用到类了~
C、重载结构体或类的比较运算符：
（1）直接在结构体里进行重载比较运算符：
typedef struct Student{ int id; string name; double grade; bool operator<(const Student& s) { return id>s.id;//降序排列 } }; vector<Student> V; sort(V.begin(),V.end());
这里用到了vector容器，是在ACM集训中学到的，前阵子还没开通博客也没来得及总结学习，坚持每天一个博客，努力把总结内容补起来~
（2）直接声明重载：
vector<Student> V; bool operator<(const Student& s1, const Student& s2) { return s1.id>s2.id;//降序排列 } sort(V.begin(),V.end());
注意：sort默认使用的是<运算符，所以要针对<来重载，而不能使用>哦~。
D、使用标准库中的函数：
functional提供了一堆基于模板的比较函数对象，
但sort要用到的也只是greater和less就够了：
升序：sort(begin,end,less<data-type>())
降序：sort(begin,end,greater<data-type>())
缺点：也只是实现简单的排序，结构体不适用，所以推荐自己写规则吧~。
注：如果有更好的解法，真心希望您能够评论留言贴上您的代码呢~
原文链接:https://www.cnblogs.com/winniy/p/10434667.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换（用户自定义类类型） 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
