C++中的sort函数详解

0.简介

sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，sort函数包含在头文件为#include<algorithm>的c++标准库中

1.sort的参数

sort(start,end,cmp)

start:表示排序数组起始的位置

end:表示排序数组结束的位置

cmp：用于排序的方法，可以不填，不填默认升序

2.数组中的用法

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[5]={1,9,3,4,5};
    for(int i=0;i<5;i++)
    	cout<<a[i]<<" ";
    sort(a,a+5);  //数组从0开始，数组有多少个数就加多少 
    cout<<endl;
    for(int i=0;i<5;i++)
    	cout<<a[i]<<" ";
    return 0;
}

---

当我们加上cmp函数后，下面这种写法和上面的结果一样

---

#include<bits/stdc++.h>
using namespace std;
bool cmp(int x, int y)
{
	return x<y;	
	/*
		可以这样理解，sort第三个参数默认升序，
		这个地方是个bool函数。
		如果返回值结果为假，那么函数会互换他们的位置
		如果返回结果为真，就保持原来的位置不变 。
		如果x<y成立，那么就保持不变，否则就交换位置。 
	*/ 
} 
int main()
{
    int a[5]={1,9,3,4,5};
    for(int i=0;i<5;i++)
    	cout<<a[i]<<" ";
    sort(a,a+5,cmp);  //数组从0开始，数组有多少个数就加多少 
    cout<<endl;
    for(int i=0;i<5;i++)
    	cout<<a[i]<<" ";
    return 0;
}

可以这样理解，sort中的第三个参数，会去进行两两元素的比较，
函数这个地方是个bool类型的函数。
如果返回值结果为假，那么函数会互换他们的位置
如果返回结果为真，就保持原来的位置不变函数

---

那么，如果把cmp中的函数改成 return x>y; 那么默认就是 从大到小排序。

3.结构体中的用法

平常做题的时候可能会遇到下面几种情况：

• 一个结构体需要排序，里面属性太多，只根据一个属性进行排序，其余属性需要同步更改位置，单纯使用冒泡需要交换的东西太多
• 一个结构体需求排序，但是排序依据不唯一。例如下面结构体

struct student{
	char name[50];   //学生姓名 
	int sum;   //总成绩  
	int chinese;  //语文成绩 
	int math;  //数学成绩 
	int english;  //英语成绩 
};

要求先按照总成绩排序，如果总成绩相同，则按照数学成绩排序，如果数学成绩相同，则按照英语成绩排序，如果英语成绩相同则按照语文成绩排序。

。。。。。。

先来解决第一个问题，假如只按照总成绩排序，总成绩相同的不做任何排序处理。

#include<bits/stdc++.h>
using namespace std;

struct student{
	char name[50];   //学生姓名 
	int sum;   //总成绩  
	int chinese;  //语文成绩 
	int math;  //数学成绩 
	int english;  //英语成绩 
};
student s[50]; 
bool cmp(student x, student y)  //参数类型要写成结构体类型， 
{
	return x.sum>y.sum;	
} 
int main()
{	
	int n;// 定义数据
	cin>>n;
	for(int i=0;i<n;i++) 
	{
		cin>>s[i].name>>s[i].chinese>>s[i].math>>s[i].english;
		s[i].sum=s[i].chinese+s[i].math+s[i].english;	
	}    
	sort(s,s+n,cmp);
	cout<<"按总成绩排序后的结果是："<<endl; 
	cout<<"name"<<" "<<"语文"<<" "<<"数学"<<" "<<"英语"<<" "<<"总成绩"<<endl; 
	for(int i=0;i<n;i++) 
	{
		cout<<s[i].name<<" "<<s[i].chinese<<" "<<s[i].math<<" "<<s[i].english<<" "<<s[i].sum<<endl;	
	}   
	
    return 0;
}

/*
8
tom1 10 20 30
tom2 10 30 30
tom3 20 30 30
tom4 10 30 10
tom5 30 40 10
tom6 10 15 10
tom7 30 20 15
tom8 20 10 15	

*/

可以看出是按照总计成绩进行排序的。可以看出，我们在cmp函数中只要写一个结构体中的参数就可以了。

---

那么第二个问题来了。我们可以继续改cmp中的写法

#include<bits/stdc++.h>
using namespace std;

struct student{
	char name[50];   //学生姓名 
	int sum;   //总成绩  
	int chinese;  //语文成绩 
	int math;  //数学成绩 
	int english;  //英语成绩 
};
student s[50]; 
bool cmp(student x, student y)  //参数类型要写成结构体类型， 
{
	//先按照总成绩由大到小排(如果两个数的总成绩不相等，则根据大小关系判断是否交换位置)
	if(x.sum!=y.sum)     
		return x.sum>y.sum;
	//如果总成绩相同，再按照数学成绩进行排序  
	if(x.math!=y.math)
		return x.math>y.math;
	//如果数学成绩相同，再按照英语成绩进行排序 		
	if(x.english!=y.english)
		return x.english>y.english;
	else  //最后只剩语文了 
		return x.chinese>y.chinese; 
} 
int main()
{	
	int n;// 定义数据
	cin>>n;
	for(int i=0;i<n;i++) 
	{
		cin>>s[i].name>>s[i].chinese>>s[i].math>>s[i].english;
		s[i].sum=s[i].chinese+s[i].math+s[i].english;	
	}    
	sort(s,s+n,cmp);
	cout<<"按总成绩排序后的结果是："<<endl; 
	cout<<"name"<<" "<<"语文"<<" "<<"数学"<<" "<<"英语"<<" "<<"总成绩"<<endl; 
	for(int i=0;i<n;i++) 
	{
		cout<<s[i].name<<" "<<s[i].chinese<<" "<<s[i].math<<" "<<s[i].english<<" "<<s[i].sum<<endl;	
	}   
	
    return 0;
}

/*
8
tom1 10 20 50
tom2 10 30 40
tom3 10 40 30
tom4 20 20 40
tom5 30 20 30
tom6 40 20 20
tom7 30 20 30
tom8 20 20 30	

*/

可以看出，首先按照总成绩排序，如果总成绩相同，则按照数学成绩排序，如果数学成绩相同，则按照英语成绩排序。题目的样例不够完善，没有体现出如果在上面的条件下，如果英语成绩也相同的情况。

4.总结

不论是单纯的数组还是结构体，sort函数的第三个参数是用来决定两个元素是否要进行交换位置的。

---

返回目录：算法

---