C++的sort函数

参考:

https://baike.baidu.com/item/sort%E5%87%BD%E6%95%B0/11042699?fr=aladdin

https://blog.csdn.net/ljl1015ljl/article/details/88096118

https://www.cnblogs.com/TX980502/p/8528840.html

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

函数原型

Sort(start,end,cmp)

参数

(1)start表示要排序数组的起始地址;
(2)end表示数组结束地址的下一位
(3)cmp用于规定排序的方法,可不填,默认升序

功能

sort函数用于C++中,对给定区间所有元素进行排序,默认为升序,也可进行降序排序。
一般是直接对数组进行排序,例如对基本类型的数组a[10]排序,sort(a,a+10)。而sort函数的强大之处在可与自定义的子函数cmp函数结合使用,即排序方法的选择。

关于cmp子函数返回值的规则说明

若满足某个条件时,a1应该在a2前面,则返回true,否则返回false。

说简单点就是:返回true说明参数一应该排在参数二前面,否则想发。具体参见下面的实例。

 sort类函数

整个sort类函数有很多其他东西可以使用,但是参数意义类似,下面只演示sort。

函数名 功能描述
sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition
相对稳定的使得符合某个条件的元素放在前面

 sort和stable_sort函数都应该掌握。stable_sort函数可以参见下文第五种用法中的例子

用sort进行排序(用法一)

基本类型的数组从小到大排序:  sort(数组名+n1,数组名+n2);
其中,n1和n2都是int类型的表达式,可以包含变量。若n1=0,则 + n1可以不写。

功能是:将下标范围[n1,n2)的元素从小到大排序。注意:下标n2的元素是不参与排序的。

例如:

int a[] = {15,4,3,9,7,2,6};     sort(a,a+7); //对整个数组从小到大排序
int a[] = {15,4,3,9,7,2,6};     sort(a,a+3); // 结果: {3,4,15,9,7,2,6}
int a[] = {15,4,3,9,7,2,6};     sort(a+2,a+5); //结果: {15,4,3,7,9,2,6}

用sort进行排序(用法二)
元素类型为T基本类型数组从大到小排序:    sort(数组名+n1,数组名+n2,greater<T>( )) ;

同理,上述代码是对下标区间[n1,n2)的元素作从大到小排序。下标n2的元素不参与排序。

例如:

int a[] = {15,4,3,9,7,2,6};
sort(a+1,a+4,greater<int>( ));   // 结果: {15,9,4,3,7,2,6}

用sort进行排序(用法三)

自定义的排序规则,对任何类型T的数组排序。

  sort(数组名+n1,数组名+n2,排序规则结构名( ));

排序规则结构体的定义方式:

1 struct 结构名
2 {
3     bool operator()( const T & a1,const T & a2) {
4         //若满足某个条件时,a1应该在a2前面,则返回true。
5         //否则返回false。
6     }
7 };
8     

例如:定义如下两个规则

 1 struct Rule1 //按从大到小排序
 2 {    
 3     bool operator()( const int & a1,const int & a2) {
 4     return a1 > a2;
 5     }
 6 };
 7 struct Rule2 //按个位数从小到大排序
 8 {    
 9     bool operator()( const int & a1,const int & a2) {
10     return a1%10 < a2%10;
11     }
12 };

可以如下调用sort函数:

int a[] = { 12,45,3,98,21,7};
sort(a,a+sizeof(a)/sizeof(int)); //从小到大
sort(a,a+sizeof(a)/sizeof(int),Rule1( )); //从大到小
sort(a,a+sizeof(a)/sizeof(int),Rule2( )); //按个位数从小到大

用sort进行排序(用法四)----对结构体数组排序

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 struct Student {
 6 char name[20];
 7 int id;
 8 double gpa;
 9 };
10 Student students [] = {
11                 {"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},
12                 {"Ala",333,3.5},{"Zero",101,4.0}  };
13 
14 //当某个条件满足时,s1应该在s2前面,则返回true;否则返回false。
15 struct StudentRule1//按姓名从小到大排
16 {       bool operator( ) (const Student & s1,const Student & s2)
17     {    if( strcmp(s1.name,s2.name) < 0)return true;
18         return false;
19     }
20 };
21 struct StudentRule2//按id从小到大排
22 {     bool operator( ) (const Student & s1,const Student & s2) 
23     {    return s1.id < s2.id; }
24 };
25 struct StudentRule3 //按gpa从高到低排
26 {    bool operator( ) (const Student & s1,const Student & s2)
27      {    return s1.gpa > s2.gpa;  }
28 };
29 
30 void PrintStudents(Student s[],int size){
31  for(int i = 0;i < size;++i)
32    cout << "(" << s[i].name << ","<< s[i].id <<"," << s[i].gpa << ") " ;
33  cout << endl;    
34 }
35 
36 int main()
37 {
38     int n = sizeof(students) / sizeof(Student);
39     sort(students,students+n,StudentRule1( )); //按姓名从小到大排
40     PrintStudents(students,n);
41     sort(students,students+n,StudentRule2( )); //按id从小到大排
42     PrintStudents(students,n);
43     sort(students,students+n,StudentRule3( )); //按gpa从高到低排
44     PrintStudents(students,n);
45     return 0;
46 }

上述用法一至用法4的完整演示代码如下:

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<time.h>
  4 #include<stdlib.h>
  5 #include<string.h> 
  6 #include<algorithm>
  7 using namespace std;
  8 
  9 struct Student
 10 {
 11     char name[20];
 12     int id;
 13     double gpa;
 14 };
 15 
 16 
 17 
 18 //----------------------------------------------------------
 19 //当某个条件满足时,a1应该在a2前面,则返回true;否则返回false。 
 20 struct Rule1 //按从大到小排序
 21 {
 22     bool operator()( const int & a1,const int & a2)
 23     {
 24         return a1 > a2;
 25     }
 26 };
 27 //当某个条件满足时,a1应该在a2前面,则返回true;否则返回false。
 28 struct Rule2 //按个位数从小到大排序
 29 {
 30     bool operator()( const int & a1,const int & a2) 
 31     {
 32         return a1%10 < a2%10;
 33     }
 34 };
 35 //当某个条件满足时,s1应该在s2前面,则返回true;否则返回false。
 36 struct StudentRule1//按姓名从小到大排
 37 {   
 38     bool operator() (const Student & s1,const Student & s2)
 39     {
 40         if( strcmp(s1.name,s2.name) < 0)return true;
 41         return false;
 42     }
 43 };
 44 //当某个条件满足时,s1应该在s2前面,则返回true;否则返回false。
 45 struct StudentRule2//按id从小到大排
 46 { 
 47     bool operator() (const Student & s1,const Student & s2) 
 48     {    return s1.id < s2.id; }
 49 };
 50 //当某个条件满足时,s1应该在s2前面,则返回true;否则返回false。
 51 struct StudentRule3 //按gpa从高到低排
 52 {
 53     bool operator() (const Student & s1,const Student & s2)
 54     {    return s1.gpa > s2.gpa;  }
 55 };
 56 
 57 
 58 
 59 
 60 
 61 //----------随机数相关子函数-----------------------------
 62 int getRandomInt(int a,int b)//返回[a,b]之间一个随机整数
 63 {   return (rand() % (b-a+1))+ a;   }
 64 double getRandomDouble()//返回0~1之间随机浮点数 
 65 {   return rand()/double(RAND_MAX); }
 66 char getUpChar()//返回随机大写字母
 67 {   return ((char)(rand()%26+'A')); } 
 68 char getDownChar()//返回随机小写字母
 69 {   return ((char)(rand()%26+'a')); } 
 70 void InitRandom()
 71 {  srand((unsigned)time(0)); }
 72 //-------------------------------------------------------
 73 void PrintStudents(Student s[],int size)
 74 {
 75     for(int i = 0;i < size;++i)
 76         cout<< "(" << s[i].name << ","
 77             << s[i].id <<"," << s[i].gpa << ") " ;
 78     cout<<endl;
 79 }
 80 
 81 int main()
 82 {
 83     int IntArr[15],IntArr2[15],IntArr3[15],i,n=15;
 84     double dArr[15];
 85     InitRandom();
 86     
 87     //-------------------------------------------------------
 88     for(i=0;i<n;i++)//生成随机整数数组 
 89     {
 90         IntArr3[i]=IntArr2[i]=IntArr[i]=getRandomInt(1,99);
 91         printf("%2d ",IntArr[i]);
 92     }
 93     printf("
");
 94     //--------使用默认排序规则对基本类型从小到大排序从小到大排序-----------------------------------------------
 95     sort(IntArr,IntArr+n);//默认从小到大排序 
 96     for(i=0;i<n;i++)
 97         printf("%2d ",IntArr[i]);
 98     printf("
");
 99     
100     sort(IntArr2,IntArr2+10);//对IntArr2[0]~IntArr2[9]从小到大排序 
101     for(i=0;i<n;i++)
102         printf("%2d ",IntArr2[i]);
103     printf("
");
104     
105     sort(IntArr3+2,IntArr3+10);//对IntArr3[2]~IntArr3[9]从小到大排序
106     for(i=0;i<n;i++)
107         printf("%2d ",IntArr3[i]);
108     printf("


");
109     //-------------------------------------------------------
110     
111     
112     
113     
114     
115     //-------------------------------------------------------
116     n=10;
117     for(i=0;i<n;i++)//生成随机浮点数数组 
118     {
119         dArr[i]=getRandomDouble()*1000;
120         printf("%.2lf ",dArr[i]);
121     }
122     printf("
");
123     //------对基本数据类型从大到小排序-------------------------
124     sort(dArr+1,dArr+4,greater<double>());//对dArr[1]~dArr[3]从大到小排序 
125     for(i=0;i<n;i++)
126         printf("%.2lf ",dArr[i]);
127     printf("


");
128     //-------------------------------------------------------
129     
130     
131     
132     
133     //-----使用自定义规则排序--------------------------------
134     n=15; 
135     sort(IntArr,IntArr+n); //默认从小到大
136     for(i=0;i<n;i++) printf("%2d ",IntArr[i]);
137     printf("
");
138     
139     sort(IntArr,IntArr+n,Rule1()); //Rule1()规则从大到小
140     for(i=0;i<n;i++) printf("%2d ",IntArr[i]);
141     printf("
");
142     
143     sort(IntArr,IntArr+n,Rule2()); //Rule2()规则按个位数从小到大
144     for(i=0;i<n;i++) printf("%2d ",IntArr[i]);
145     printf("


");
146     //-------------------------------------------------------
147     
148     
149     //--------自定义规则对结构体数组排序---------------------
150     Student students[]= 
151     {
152         {"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},
153         {"Ala",333,3.5},{"Zero",101,4.0}
154     };
155     n=sizeof(students)/sizeof(Student);
156     sort(students,students+n,StudentRule1()); //按姓名从小到大排
157     PrintStudents(students,n);
158     sort(students,students+n,StudentRule2()); //按id从小到大排
159     PrintStudents(students,n);
160     sort(students,students+n,StudentRule3()); //按gpa从高到低排
161     PrintStudents(students,n);
162     printf("


");
163     //-------------------------------------------------------
164     
165     
166     return 0;
167 }
View Code

上面第3、4种用法自定义排序规则使用的是运算符重载。其实可以按照sort函数里面关于cmp参数的规则,自己定义一个子函数来表示排序规则。下面第5种用法就是展示这种操作。

用sort进行排序(用法五)----子函数表示排序规则

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<time.h>
  4 #include<stdlib.h>
  5 #include<string.h> 
  6 #include<algorithm>
  7 using namespace std;
  8 
  9 
 10 typedef struct
 11 {
 12     int No;
 13     int yuWen,shuXue,yingYu,zongFen;
 14 }stu;
 15 typedef struct
 16 {
 17     int x,y;
 18 }point;
 19 
 20 
 21 //---------------------------------------------------------------
 22 bool cmp1(int a,int b)//对int数组从小到大排序.参数的类型应跟待排序数组元素类型一致 
 23 {//当某个条件满足时,a应该在b前面,则返回true;否则返回false。 
 24     if(a<b)return true;
 25     else return false;
 26     //return a<b; //直接这样写更简洁 
 27 }
 28 bool cmp2(int a,int b)//对int数组从大到小排序.参数的类型应跟待排序数组元素类型一致
 29 {//当某个条件满足时,a应该在b前面,则返回true;否则返回false。 
 30     if(a>b)return true;
 31     else return false;
 32     //return a>b; //直接这样写更简洁 
 33 }
 34 bool cmp3(int a,int b)//对int数组按个位从大到小排序.参数的类型应跟待排序数组元素类型一致
 35 {//当某个条件满足时,a应该在b前面,则返回true;否则返回false。 
 36     return a%10 > b%10; //直接这样写更简洁 
 37 }
 38 bool cmp6(stu a,stu b)//对stu结构体类型数组排序.参数的类型应跟待排序数组元素类型一致
 39 {    //优先按总分从大到小,总分相等则按学号从小到大 
 40     //当某个条件满足时,a应该在b前面,则返回true;否则返回false。
 41     if(a.zongFen<b.zongFen)return false;
 42     else if(a.zongFen>b.zongFen) return true;
 43     else
 44     {
 45         if(a.No<b.No)return true; 
 46         else if(a.No>b.No) return false;
 47     }
 48 }
 49 bool cmp7(point a,point b)//对point结构体类型数组元素排序.参数的类型应跟待排序数组元素类型一致 
 50 {    //优先按x从小到大排序,当x相等则按y从大到小排序。
 51     //当某个条件满足时,a应该在b前面,则返回true;否则返回false。
 52     if(a.x < b.x) return true;
 53     else if(a.x > b.x)return false;
 54     else
 55     {
 56         if(a.y > b.y)return true;
 57         else if(a.y < b.y)return false;
 58     }
 59 }
 60 bool cmp8(point a,point b)//对point结构体类型数组元素排序.参数的类型应跟待排序数组元素类型一致
 61 {    //优先按x从大到小排序。
 62     //当某个条件满足时,a应该在b前面,则返回true;否则返回false。
 63     return a.x>b.x;
 64 }
 65 
 66 
 67 
 68 //----------随机数相关子函数-----------------------------
 69 int getRandomInt(int a,int b)//返回[a,b]之间一个随机整数
 70 {   return (rand() % (b-a+1))+ a;   }
 71 double getRandomDouble()//返回0~1之间随机浮点数 
 72 {   return rand()/double(RAND_MAX); }
 73 char getUpChar()//返回随机大写字母
 74 {   return ((char)(rand()%26+'A')); } 
 75 char getDownChar()//返回随机小写字母
 76 {   return ((char)(rand()%26+'a')); } 
 77 void InitRandom()
 78 {  srand((unsigned)time(0)); }
 79 
 80 
 81 int main()
 82 {
 83     int IntArr[15],IntArr2[15],IntArr3[15],i,n=15;
 84     double dArr[15];
 85     stu stuArr[50];//每个元素表示一个学生的数据
 86     point pArr[50];//每个元素表示一个整数点的数据(x,y) 
 87     InitRandom();
 88     
 89     //-------------------------------------------------------
 90     for(i=0;i<n;i++)//生成随机整数数组 
 91     {
 92         IntArr3[i]=IntArr2[i]=IntArr[i]=getRandomInt(1,99);
 93         printf("%2d ",IntArr[i]);
 94     }
 95     printf("
");
 96     //--------使用默认排序规则对基本类型从小到大排序从小到大排序-----------------------------------------------
 97     sort(IntArr,IntArr+n);//默认从小到大排序 
 98     for(i=0;i<n;i++)
 99         printf("%2d ",IntArr[i]);
100     printf("
");
101     
102     sort(IntArr2,IntArr2+10);//对IntArr2[0]~IntArr2[9]从小到大排序 
103     for(i=0;i<n;i++)
104         printf("%2d ",IntArr2[i]);
105     printf("
");
106     
107     sort(IntArr3+2,IntArr3+10);//对IntArr3[2]~IntArr3[9]从小到大排序
108     for(i=0;i<n;i++)
109         printf("%2d ",IntArr3[i]);
110     printf("


");
111     
112 
113 
114     //-------------------------------------------------------
115     n=10;
116     for(i=0;i<n;i++)//生成随机浮点数数组 
117     {
118         dArr[i]=getRandomDouble()*1000;
119         printf("%.2lf ",dArr[i]);
120     }
121     printf("
");
122     //------对基本数据类型从大到小排序-------------------------
123     sort(dArr+1,dArr+4,greater<double>());//对dArr[1]~dArr[3]从大到小排序 
124     for(i=0;i<n;i++)
125         printf("%.2lf ",dArr[i]);
126     printf("


");
127     
128     
129     
130     
131     //-----使用自定义规则排序--------------------------------
132     n=15; 
133     sort(IntArr,IntArr+n); //默认从小到大
134     for(i=0;i<n;i++) printf("%2d ",IntArr[i]);
135     printf("
");
136     
137     sort(IntArr,IntArr+n,cmp2); //cmp2()规则从大到小
138     for(i=0;i<n;i++) printf("%2d ",IntArr[i]);
139     printf("
");
140     
141     sort(IntArr,IntArr+n,cmp1); //cmp1()规则从小到大
142     for(i=0;i<n;i++) printf("%2d ",IntArr[i]);
143     printf("
");
144     
145     sort(IntArr,IntArr+n,cmp3); //cmp3()规则按个位数从大到小
146     for(i=0;i<n;i++) printf("%2d ",IntArr[i]);
147     printf("


");
148     
149     
150     //--------自定义规则对结构体数组排序---------------------
151     n=10;
152     for(i=0;i<n;i++)//生成stu结构体类型的随机数据
153     {
154         stuArr[i].No=1000+i;
155         stuArr[i].yuWen=getRandomInt(90,150);
156         stuArr[i].shuXue=getRandomInt(90,150);
157         stuArr[i].yingYu=getRandomInt(90,150);
158         stuArr[i].zongFen=stuArr[i].yuWen+stuArr[i].shuXue+stuArr[i].yingYu;
159         printf("%d %3d %3d %3d %3d
",stuArr[i].No,stuArr[i].yuWen,stuArr[i].shuXue,stuArr[i].yingYu,stuArr[i].zongFen);
160     }
161     printf("
");
162     //-------------------------------------------------------
163     sort(stuArr,stuArr+n,cmp6);//对stu类型数组排序 
164     for(i=0;i<n;i++)
165         printf("%d %3d %3d %3d %3d
",stuArr[i].No,stuArr[i].yuWen,stuArr[i].shuXue,stuArr[i].yingYu,stuArr[i].zongFen);
166     printf("


");
167     
168     
169     
170     
171     //-------------------------------------------------------
172     n=10;
173     for(i=0;i<n;i++)//生成point结构体类型的随机数据 
174     {
175         pArr[i].x=getRandomInt(80,100);
176         pArr[i].y=getRandomInt(1,100);
177         printf("%2d %2d
",pArr[i].x,pArr[i].y);
178     }
179     printf("
");
180     //-------------------------------------------------------
181     sort(pArr,pArr+n,cmp7);//对point类型数组排序 
182     for(i=0;i<n;i++)
183         printf("%2d %2d
",pArr[i].x,pArr[i].y);
184     printf("
");
185         
186     stable_sort(pArr,pArr+n,cmp8);//对point类型数组排序,稳定排序 
187     for(i=0;i<n;i++)
188         printf("%2d %2d
",pArr[i].x,pArr[i].y);
189     printf("


");
190     
191     
192     
193     return 0;
194 }
View Code