symfony rxjs reference Material UI pmp学习视频 查看kafka消费情况 datetimepicker赋值 cpm计算 spark算法 bentley软件介绍 abaqus是什么软件 bootstrap模态框传参 android调试工具 math保留两位小数 js控制台打印 java入门编程 java编程学习入门 java字符串反转 java数组删除 java怎么写接口 java获取本机ip java声明变量 怎么安装linux javascript源代码 opengl编程指南 acmecadconverter 日历制作模板 深入浅出通信原理 免费的视频剪辑 fdisk下载 win10有几个版本 pr蒙版 原创检测工具 子节点 python求和 foobar2000插件 无线网密码修改 cpu和显卡怎么搭配 bat转exe ps怎么裁剪圆形
当前位置: 首页 > 学习教程  > 编程语言

sort函数用法(详细),cmp的构造

2021/2/13 19:20:54 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

sort函数 sort是cSTL标准库中提到的基于快速排序的排序函数,在做题的时候使用sort函数很方便,使用sort要使用#include 快速排序具有不稳定性 不稳定性是指,对于指定区域内相等的元素,sort函数可能无法保证数据的元素不发生相对位…

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.待排序变量>/<结构体1.待排序变量
}

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

下面用洛谷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函数,不会改变相等元素的位置


本文链接: http://www.dtmao.cc/news_show_700310.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?