注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

C++ STL的sort 的简单的应用,非常适合于学C的朋友,推荐————比冒泡泡简单那  

2014-03-11 23:09:20|  分类: ACM学习小结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
sort的使用前提
要使用C++ STL的sort,必须要写这2行:
#include <algorithm>
using namespace std;

这里顺带说一句,非常建议OJ上直接使用G++编译
1)不要因为自己只会C而完全排斥、逃避C++的任何内容,包括方便的要死的sort
2)经无数次测试,hdoj上用G++直接编译带有C风格头文件的(#include <stdio.h>)代码完全没事
也就是说,用G++编译完全可以保留GCC编译的时候写代码的全部习惯
3)实际赛场上看上去用Linux编译的可能性极大,也就是说,只有GCC/G++了
早点抛弃void main(),转投int main()的怀抱没错的!
=================================================================
1、sort的两种原型以及效果
sort函数有两种原型:
template<class RanIt>
    void sort(RanIt first, RanIt last); //--> 1)
template<class RanIt, class Pred>
    void sort(RanIt first, RanIt last, Pred pr); //--> 2)

看上去看不懂,换一个实用的就好懂多了——
#define N 30
int a[N];
//对a输入以后
sort(a,a+N);//第一种
sort(a,a+N,cmp);//第二种

提醒:
1、用sort的时候数组可以直接上
2、用sort排序只能排序1维数组或者多维数组的最大维度

先讲第一种
第一种就是对数组a从a[0]开始到a[N-1](0到N-1,刚好N个)进行排序,排完序以后是升序的(从小到大的)

那如果我排序的结果要降序(从大到小)呢?如果我有更多的排序需求呢?
这个时候第二种的第3个参数就有存在意义了
第3个参数,就直接打一个函数名
这个函数的作用就是,自定义排序规则

比如,我们需要对一个整数数组降序排列,定义函数:
int cmp(int a,int b)
{
return a>b;
}
从上面这个比较函数的样例中,我们可以得知:
1、需要接受2个传入参数,前一个可能在数组中靠前,后一个在数组中靠后
2、如果根据比较规则,前一个就应该在后一个前面(即两者前后顺序正确),返回真,否则返回假。
(不需要把两者相等的情况给特殊照顾,相等的情况交换和不交换等效)
=====================================================================
2、更多的要求——结构体数组和比较函数的一点复杂化

考虑下面的要求:
给出n(<=100)个学生的姓名(<=10字节)和期末绩点(无顺序,假设没有绩点完全相同的两人),要求按照绩点从高到低排序,输出排序后的结果。
如果把姓名和绩点分两个数组存储……
绩点排了序,姓名对不上号了!
那我们要考虑一下把姓名和绩点捆绑在一起。
结构体!
因此,做出如下定义
#define N 100
struct Student
{
char name[30];
double grade;
}student[N+1];

然后,定义排序规则:
int cmp(const Student a,const Student b)//如果怕自己在写比较函数的时候手滑了,导致修改了数据,写参数表的时候多打2个const没错的
{
return a.grade>b.grade;
}

最后,调用排序
int n;
//读入n个之后
sort(student,student+n,cmp);

还是很显然的吧?
======================================================================
3、多关键词排序——比较函数的进一步讨论

在之前的问题基础上,进一步的,考虑以下情况:
如果有同学的绩点一样,要求按名字的ASCII从小到大排序。
——也就是说,这是一个多关键词排序的问题了……

这次定义不用变,调用方法当然也不变,重头戏在排序规则上。
先分析一下:
如果a.grade>b.grade,返回1;
如果a.grade<b.grade,返回0;
如果a.grade==b.grade,比较名字,名字前者小返回1,否则返回0。

对这个双关键词的例子,我们可以调整一下:
如果a.grade==b.grade,比较名字,名字前者小返回1,否则返回0。
否则,返回a.grade与b.grade的比较结果。
于是,写出以下代码:

int cmp(const Student a,const Student b)
{
if (a.grade==b.grade) return strcmp(a.name,b.name)<0;
return a.grade>b.grade;
}

至于更多的关键词的比较,希望大家能举一反三了。

THE END.
  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017