基础算法——进阶sort与重载运算符
上次我们讲了桶排序与快速排序，上题：
题目描述： 输入n个数，对它们由大到小进行排序后输出。 输入描述: 第一行一个正整数n，表示有n个数。 第二行有n个不超过1000的正整数，中间用空格隔开。 输出描述： 经排序后的数，中间用空格隔开。 输入样例： 5 9 2 3 7 9 输出样例： 9 9 7 3 2 其他说明： n<1000000。
我们之前学的sort只能对整数或小数进行排序，但如果我们相对结构体进行排序，sort是无法实现的，因为你没有告诉程序怎么比较两个结构体的大小。因此，为了比较两个结构体的大小，你需要一个bool型函数。以之前的student类型为例：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。struct student { int num,c,m,e; }; bool cmp(student x,student y) { if(x.c+x.m+x.e>y.c+y.m+y.e)//先比总分 return 1; if(x.c+x.m+x.e<y.c+y.m+y.e) return 0; if(x.c>y.c)//总分相同比语文 return 1; if(x.c<y.c) return 0; if(x.m>y.m)//语文相同比数学 return 1; if(x.m<y.m) return 0; if(x.e>y.e)//数学相同比英语 return 1; if(x.e<y.e) return 0; return x.num<y.num;//全部相同学号小的在前 }
这时，你就可以使用以下语句来对一个student型数组a的前n个变量进行排序：
sort(a,a+n,cmp);
当然，这个方法比较低端，为了使你的代码更高端，也就是看起来更像那么回事，你需要用到一个叫“重载运算符”的高端操作。什么是重载运算符呢？简单地说，你的小于号<原来只能比较int、double、char等类型，现在你要让小于号能够比较student类型。很简单，只需要使用以下代码来代替刚才的cmp函数：
bool operator<(student x,student y) { if(x.c+x.m+x.e>y.c+y.m+y.e) return 1; if(x.c+x.m+x.e<y.c+y.m+y.e) return 0; if(x.c>y.c) return 1; if(x.c<y.c) return 0; if(x.m>y.m) return 1; if(x.m<y.m) return 0; if(x.e>y.e) return 1; if(x.e<y.e) return 0; return x.num<y.num; }
你会发现，唯一的区别就是把函数名cmp改为了operator<。operator就是运算符的意思。假设你有两个student类型的变量a和b，那么写重载运算符用a<b来比较和写cmp函数用cmp(a,b)来比较的结果是完全一样的。区别是，在写重载运算符后，可以直接用sort(a,a+n)来排序，而不用加“,cmp”。注意，由于sort用小于号<来比较大小，因此要用sort的话必须重载小于号<。其实，重载运算符还有一种更高端的写法——将重载写在结构体的定义中，如下：
struct student { int num,c,m,e; bool operator<(const student x)const { if(c+m+e>x.c+x.m+x.e) return 1; if(c+m+e<x.c+x.m+x.e) return 0; if(c>x.c) return 1; if(c<x.c) return 0; if(m>x.m) return 1; if(m<x.m) return 0; if(e>x.e) return 1; if(e<x.e) return 0; return num<x.num; } };
是不是看起来更高端了？这就是sort与重载运算符的用法，你学会了吗？
//答案代码 #include<cstdio> int n,a,buc[1001]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a); buc[a]++; } for(int i=1000;i>=0;i--) for(int j=1;j<=buc[i];j++) printf("%d ",i); return 0; }
Created by RFdragon
更多精彩
