青少年编程知识记录 codecoming

【高级篇】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.字典序问题

一些题目中，可能会要求按照字典序排序，一般多见于字符串的类型。

比如

例题1—单词排序：

【题目描述】输入一行单词序列，相邻单词之间由1个或者多个空格间隔，请按照字典序输出这些单词。

【输入】一行单词序列，最少1个单词，最多100个单词，每个单词长度不超过50，单词之间用至少1个空格间隔。数据不含除字母、空格外的其他字符。

【输出】按字典序输出这些单词。

【样例输入】

She  wants  to go to Peking University to study  Chinese

【样例输出】 

Chinese  Peking  She  University  go  study  to  wants

首先，这个题目简单一点的做法就是，直接for循环，按照ASCII码比较。但是，我们学了sort，用起来就比较简单了。

做法1：sort+结构体+字符数组

#include<iostream>  #include<cstdio>  #include<algorithm>  using namespace std;  struct student{  	char name[50];   }s[100];   bool cmp(student x, student y){  	return x.name > y.name;  }  int main(){  	int n;  	cin>>n; //确定长度  	for(int i=0;i<n;i++){  		cin>>s[i].name;  	}  	//sort(s,s+n); //因为是结构体，所以不加第三个参数，这里会报错   	sort(s,s+n,cmp);   	cout<<"-----结果-----"<<endl;  	for(int i=0;i<n;i++){  		cout<<s[i].name<<endl;  	}  }  /*  输入：   4  aa  bs  cf  ck   输出：   ck  cf  bs  aa  */

可以看出，我们如果结构体中只是用字符数组排序的话，只能按照输入的正序或者倒序排，但是没有按照字典序排。（但是如果是类似按照总成绩进行排序，那么名字会同步变化）

如果是结构体+字符串呢

#include<iostream>  #include<cstdio>  #include<algorithm>  using namespace std;  struct student{  	string name;   }s[100];   bool cmp(student x, student y){  	return x.name < y.name;  }  int main(){  	int n;  	cin>>n; //确定长度  	for(int i=0;i<n;i++){  		cin>>s[i].name;  	}  	//sort(s,s+n); //因为是结构体，所以不加第三个参数，这里会报错   	sort(s,s+n,cmp);   	cout<<"-----结果-----"<<endl;  	for(int i=0;i<n;i++){  		cout<<s[i].name<<endl;  	}  }    /*  输入：   4  aa  bs  cf  ck   输出：   aa  bs  cf  ck  */

可以看出这种是没有问题的。

也就是说，如果是成绩排序+字典序排序的话， 那么类似于名字这样的，要用字符串而不是字符数组。

做法2：sort+字符串数组

除了结构体之外，我们还可以用字符串数组来

#include<iostream>  #include<cstdio>  #include<algorithm>  using namespace std;  string s[100];   int main(){  	int n;  	cin>>n; //确定长度  	for(int i=0;i<n;i++){  		cin>>s[i];  	}  	sort(s,s+n);   	cout<<"-----结果-----"<<endl;  	for(int i=0;i<n;i++){  		cout<<s[i]<<endl;  	}  }    /*  输入：   4  Ajl  dsa  Bdr  rgk  输出：   Ajl  Bdr  dsa  rgk  */

可以看出，字符串数组可以不用加sort的第三个参数，默认按照字典序输出。当然，我们也可以加上第三个参数。

#include<iostream>  #include<cstdio>  #include<algorithm>  using namespace std;  string s[100];   bool cmp(string x, string y){  	return x>y;  }    int main(){  	int n;  	cin>>n; //确定长度  	for(int i=0;i<n;i++){  		cin>>s[i];  	}  	sort(s,s+n,cmp);   	cout<<"-----结果-----"<<endl;  	for(int i=0;i<n;i++){  		cout<<s[i]<<endl;  	}  }    /*  输入：   4  Ajl  dsa  Bdr  rgk  输出：   rgk  dsa  Bdr  Ajl  */
5.总结

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



(adsbygoogle = window.adsbygoogle || []).push({});

作者:亿万年的星光 分类:C++知识 浏览: