博客

1.sort介绍

sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序；

sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高；

sort函数包含在头文件为#include<algorithm>的c++标准库中。

2.函数介绍

语法

Sort(start,end,cmp)

参数

（1）start表示要排序数组的起始地址；

（2）end表示数组结束地址的下一位；

（3）cmp用于规定排序的方法，可不填，默认升序。

功能

sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。

一般是直接对数组进行排序，例如对数组a[10]排序，sort（a,a+10）。

而sort函数的强大之处在可与cmp函数结合使用，即排序方法的选择。

为什么要用c++标准库里的排序函数？

sort（）函数是c++一种排序方法之一，相较冒泡排序和选择排序所带来的执行效率不高的问题，sort（）函数使用的排序方法是类似于快速排序的方法，时间复杂度为n*log2(n)，执行效率较高。

3.示例

示例一

sort函数没有第三个参数，实现的是从小到大（升序）排列

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

    int a[10]

    for(int i=0;i<10;i++)

    cout<<a[i]<<endl;

    sort(a,a+10);

    for(int i=0;i<10;i++)

    cout<<a[i]<<endl;

    return 0;

}

示例二

如何实现从大到小的排序？

这就如前文所说需要在sort（）函数里的第三个参数了，告诉程序我要从大到小排序。

需要加入一个比较函数compare()，此函数的实现过程如下

bool compare(int a,int b)

{

    return a>b;

}

实现从大到小的排序的方法

#include<iostream>

#include<algorithm>

using namespace std;

bool compare(int a,int b)

{   

return a>b;

}

int main()

{

int a[10]；

for(int i=0;i<10;i++)

cout<<a[i]<<endl;  

sort(a,a+10,compare);//在这里就不需要对compare函数传入参数了   

for(int i=0;i<10;i++)

cout<<a[i]<<endl;

return 0;

}

结构体类型

struct node

{    

int a;    

int b;    

double c;

}

有一个node类型的数组node arr[100]，对它进行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b还相同，就按c降序排列。就可以写一个比较函数

bool cmp(node x,node y)

{    

if(x.a!=y.a) return x.a<y.a;    

if(x.b!=y.b) return x.b>y.b;    

return x.c>y.c;

}

4.例题

问题描述：

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 55 名学生发奖学金。期末，每个学生都有 33 门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 33 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前 55 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:

77 279279

55 279279

这两行数据的含义是:总分最高的两个同学的学号依次是 77 号、55 号。这两名同学的总分都是 279279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 77 的学生语文成绩更高一些。如果你的前两名的输出数据是:

55 279279

77 279279

则按输出错误处理，不能得分。

输入

共 n+1n+1行。

第 11 行为一个正整数n ( \le 300)n(≤300)，表示该校参加评选的学生人数。

第 22 到 n+1n+1 行，每行有 33 个用空格隔开的数字，每个数字都在 00 到 100100 之间。第 jj 行的 33 个数字依次表示学号为 j-1j−1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1\sim n1∼n（恰好是输入数据的行号减 11）。

所给的数据都是正确的，不必检验。

//感谢 黄小U饮品 修正输入格式

输出

共 55 行，每行是两个用空格隔开的正整数，依次表示前 55 名学生的学号和总分。

Sample 1

Inputcopy	Outputcopy
6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98	6 265 4 264 3 258 2 244 1 237

Sample 2

Inputcopy	Outputcopy
8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98	8 265 2 264 6 264 1 258 5 258

代码

#include<iostream>
#include<algorithm>
using namespace std;

struct stu
{
	int number;
	int Chinese,Math,English;
	int sum;
}student[500];

bool cmp(stu a,stu b)
{
	if(a.sum==b.sum&&a.Chinese==b.Chinese) return a.number<b.number;
	else if(a.sum==b.sum) return a.Chinese>b.Chinese;
	return a.sum>b.sum;
}

int main(void)
{
	int n;
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		student[i].number=i;
		scanf("%d%d%d",&student[i].Chinese,&student[i].Math,&student[i].English);
		student[i].sum=student[i].Chinese+student[i].Math+student[i].English;
	}
	sort(student+1,student+n+1,cmp);
	
	for(int i=1;i<=5;i++) 
	printf("%d %d\n",student[i].number,student[i].sum);
	
	return 0;
}