sort()排序详解 – liang

本文最后更新于270 天前，其中的信息可能已经过时，如有错误请发送邮件到1663714611@qq.com

一、简介：

1.优势：

手写就有点浪费时间，调函数快。

2.实现原理：

也许你会疑问，我使用sort方法对数据进行排序就一定合适吗？sort()可以根据我的需要对数据进行排序吗？其实sort()函数还是一个比较灵活的函数。很多解释是：sort()函数是类似于快速排序的方法，时间复杂度为n*log2(n)，执行效率较高。其实STL中的sort()并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。所以说sort()是一个比较灵活的函数，它也会根据我们数据的需要进行排序，所以我们就不用担心以上的问题了。对于大部分的排序需求，sort()都是可以满足的。

二、使用方法：

1.头文件：

在C++中使用sort()函数需要使用#include<algorithm>头文件。algorithm意为”算法”,是C++的标准模版库（STL）中最重要的头文件之一，提供了大量基于迭代器的非成员模版函数。

2.基本使用方法:

sort(begin,end,cmp),有三个参数，begin第一个元素的指针,end最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。如果我们想从大到小排序可以将cmp参数写为greater<int>()就是对int数组进行排序，当然<>中我们也可以写double、long、float等等。

3.自定义排序准则：

sort()函数可以自定义排序准则，以便满足不同的排序情况。使用sort()我们不仅仅可以从大到小排或者从小到大排，还可以按照一定的准则进行排序。比如说我们按照每个数的个位进行从大到小排序，我们就可以根据自己的需求来写一个函数作为排序的准则传入到sort()中。我们可以将这个函数定义为：

#include<iostream>
#include<algorithm>
using namespace std;

bool cmp(int x,int y){
	return x % 10 > y % 10;
}

int main(){
	int num[10] = {65,59,96,13,21,80,72,33,44,99};
	sort(num,num+10,cmp);
	for(int i=0;i<10;i++){
		cout<<num[i]<<" ";
	}//输出结果：59 99 96 65 44 13 33 72 21 80
	
	return 0;
	
}

4.对结构体进行排序:

sort()也可以对结构体进行排序，比如我们定义一个结构体含有员工的姓名和ID的结构体Emplyee，然后我们按照每个员工的ID从底到高进行排序。首先我们将结构体定义为：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

struct Emplyee{
    string name;
    int ID;
    Emplyee() {}
    Emplyee(string n,int s):name(n),score(s) {}
};

bool cmp_score(Emplyee x,Emplyee y){
    return x.ID < y.TD;
}

int main(){
    Emplyee emp[3];
    string n;
    int s;
    for(int i=0;i<3;i++){
        cin>>n>>s;
        emp[i] = emp(n,s);
    }
    sort(emp,emp+3,cmp_score);
    
    for(int i=0;i<3;i++){
        cout<<emp[i].name<<" "<<emp[i].ID<<endl;
    }
    return 0;
}

再比如，我们要根据员工的3个方面的平均分高低进行排名，那么这个cmp函数我们可定义为：

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

struct Emplyee{
    string name;
    double score[3];
}
bool cmp_score(Emplyee x,Emplyee y){
    double average_x,average_y;
    average_x = (x.score[0]+x.score[1]+x.score[2])/3;
	average_y = (y.score[0]+y.score[1]+y.score[2])/3;
	return average_x > average_y;
}
int main(){
    Emplyee emp[3];
    string n;
    int s;
    for(int i=0;i<3;i++){
        cin>>emp[i].name;
        for(int j=0;j<3;j++){
            cin>>emp.score[j];
        }
    }
    
 	sort(stu,stu+3,cmp_score);
	
	for(int i=0;i<3;i++){
		cout<<stu[i].name<<" ";
		for(int j=0;j<4;j++){
			cout<<stu[i].score[j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}