C++/C sort函数用法(详细),cmp的构造–一学就会,一用就对

  • Post author:
  • Post category:其他


sort函数



sort是c++STL标准库中提到的基于快速排序的排序函数,在做题的时候使用sort函数很方便,使用sort要使用#include


快速排序具有不稳定性
 不稳定性是指,对于指定区域内相等的元素,sort函数可能无法保证数据的元素不发生相对位置不发生改变。
 这对于普通的排序问题可能没有影响,比如对于
  2 2 3 1 5
  排序后
 1 2 2 3 1 5 (排序前第一个二可能在这里是第二个2)
 但是在这里,这些2么有其他含义,对题解影响不大
 !!!但是要注意
 假如上述两个2风别代表月份和日
 那这里可能就会产生歧义


c++中其他有关排序的函数
	sort (first, last,cmp)// 	对容器或普通数组中 [first, last) 范围内的元素进行排序,默认进行升序排序。
	stable_sort (first, last) //	和 sort() 函数功能相似,不同之处在于,对于 [first, last) 范围内值相同的元素,该函数不会改变它们的相对位置。
	partial_sort (first, middle, last)// 	从 [first,last) 范围内,筛选出 muddle-first 个最小的元素并排序存放在 [first,middle) 区间中。
	partial_sort_copy (first, last, result_first, result_last)// 	从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中。
	is_sorted (first, last)// 	检测 [first, last) 范围内是否已经排好序,默认检测是否按升序排序。
	is_sorted_until (first, last)// 	和 is_sorted() 函数功能类似,唯一的区别在于,如果 [first, last) 范围的元素没有排好序,则该函数会返回一个指向首个不遵循排序规则的元素的迭代器。
	void nth_element (first, nth, last)// 	找到 [first, last) 范围内按照排序规则(默认按照升序排序)应该位于第 nth 个位置处的元素,并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小,该位置右侧的所有元素都比其存放的元素大。


sort可以排序的对象:
	数组(sort函数的cmp不是必须的,不写默认升序排序)
	结构体


什么样的元素可以接受sort函数排序
元素类型接受使用>或<运算符
只能对vector,array,deque这三个容器进行排序	


cmp函数的使用

sort函数在不使用 cmp函数下,默认使用升序排序的cmp函数

升序:

#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp1(int i,int j)
{
	return i>j;//i>j返回值是bool类型,true/flase,可以用1/0来代替,假如t1表示x,y不需要互换,假如是0则需要互换.所以这里也可以这样写
/*if(i>j)
		return 1;//前面的数大,不换
	else if(i<=j)//换
		return 0;
*/
}
int main()
{
	int a[100]={1, 51 , 65 , 1 , 8 , 9 , 8 , 52 , 89 , 21 };
	sort(a,a+100,cmp1);
	for(int i=0;i<100;i++)
		printf("%d ",a[i]);
}

降序:

同理:
bool cmp2(int i,int j)
{
	return i<j;
	/*if (i>j)
		return 0;
	else if(i<=j)
		return 1;*/
}

对n个元素的a数组:sort(a,a+n,cmp)



对结构体进行排序

对结构体排序要构造cmp函数

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
struct student{
	int id;
	int score;
}p[10];
bool cmp3(struct student i,struct student j)
{
	return i.score>j.score;
}
int main()
{
	for(int i=0;i<10;i++)
		scanf("%d %d",&p[i].id,&p[i].score);
	sort(p,p+10,cmp3);
	for(int i=0;i<10;i++)
		printf("id:%d score%d\n",p[i].id,p[i].score);
	return 0;
}

结构体数组使用sort排序和数组排序很相似

对于cmp:使用

bool (struct 结构体 结构体变量名,struct 结构体 结构体变量名)

{


return 结构体1.待排序变量>或<结构体2.待排序变量

}



!!很多题目不会让你对于结构体内的某个变量进行单调排序,很可能会有其他限制条件,可能对于年龄排序来说,还要排学号等等

下面用洛谷P1104题目进行示范

cjf君想调查学校OI组每个同学的生日,并按照从大到小的顺序排序。但cjf君最近作业很多,没有时间,所以请你帮她排序。

输入:人数

姓名 年 月 日

例:

3

Yangchu 1992 4 23

Qiujingya 1993 10 13

Luowen 1991 8 1

输出:

Luowen

Yangchu

Qiujingya

分析:需要对年月日排序,先排年,年同再排月,月相同再排日:

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
struct struct{
	int id;
	char s[20];
	int y;
	int m;
	int d;
}p[100];
bool cmp(mate a,mate b)
{
	if(a.y<b.y)return 1;//先比年,前面小于后面就不换,因为前面老
	if(a.y>b.y)return 0;//前面年数大,换
	if(a.y==b.y)
	{
		if(a.m<b.m)return 1;//再比月
		if(a.m>b.m)return 0;
		if(a.m==b.m)
		{
			if(a.d<b.d)return 1;//再比日
			if(a.d>b.d)return 0;
			if(a.d==b.d)
			{
				if(a.id>b.id)return 1;//最后比编号
				else return 0;
			}
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%s %d %d %d",&p[i].s,&p[i].y,&p[i].m,&p[i].d);
		p[i].id=i;
	}
	sort(p,p+n,cmp);
	for(int i=0;i<n;i++)
	{
		if(i<n-1)
			printf("%s\n",p[i].s);
		else
			printf("%s",p[i].s);
	}
	return 0;
}

分析:简而言之,谁老谁在先,就是排年,年数小就老,年同然后接着比月,月同再比日



对于上文提及的快速排序的不稳定性,可以使用stable_sort函数,不会改变相等元素的位置


题目:洛谷P5740

现有 N(N≤1000) 名同学参加了期末考试,并且获得了每名同学的信息:姓名(不超过 8 个字符的字符串,没有空格)、语文、数学、英语成绩(均为不超过 150 的自然数)。总分最高的学生就是最厉害的,请输出最厉害的学生各项信息(姓名、各科成绩)。如果有多个总分相同的学生,输出靠前的那位。

eg:输入 3

senpai 114 51 4

lxl 114 10 23

fafa 51 42 60

输出

senpai 114 51 4

此题用结构体很方便,在获取分数的时候把总分存入结构体内,然后对结构体排序,输出第一个,这里最好使用stable_sort,因为可能存在同分数的情况,此时要输入靠前的,这里用stable_sort很方便

迟到的代码

#include<stdio.h>
#include<algorithm>
using namespace std;
struct stu{
	char a[10];
	int chinese;
	int math;
	int english;
	int score;
}p[1005];
bool cmp(struct stu x,struct stu y)
{
	return x.score>y.score;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%s %d %d %d",p[i].a,&p[i].chinese,&p[i].english,&p[i].math);
		p[i].score=p[i].chinese+p[i].english+p[i].math;
	}
	stable_sort(p,p+1005,cmp);
	printf("%s %d %d %d",p[0].a,p[0].chinese,p[0].english,p[0].math);
	
	return 0;
}



版权声明:本文为m0_52410356原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。