一、简介

1、头文件：#include<algorithm>

2、时间复杂度：类似于快排，为nlog(2)n，效率较高

3、sort函数有三个参数：

    （1）要排序数组的起始地址

    （2）要排序数组的最后一个数据元素的下一个地址

    （3）排序方法，如果没有排序方法的话，默认从小到大排序

二、实例

1、sort函数实现数的排序

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)///实现从大到小排序的比较函数
{
    return a>b;
}

int main()
{
    int i,j;
    int arr[10]={1,33,56,74,34,34,555,43,43,343};
    sort(arr,arr+10,cmp);
    for(i=0;i<10;i++)
        cout<<arr[i]<<" "<<endl;
    return 0;
}

2、sort函数实现字符串的排序（根据长度，字母顺序两种情况）

 （1）sort函数对string内的字符进行排序（string为字符串类型数据）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
bool cmp(char a,char b)///比较函数
{
    return a>b;
}
int main()
{
    string s;
    cin>>s;
    sort(s.begin(),s.end());///从小到大
    cout<<s<<endl;
    sort(s.begin(),s.end(),cmp);///从大到小
    cout<<s<<endl;
    cout<<s.length()<<endl;///字符串长度函数
}

（2）sort对一维字符数组内的字符进行排序

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
bool cmp(char a,char b)///比较函数
{
    return a>b;
}
int main()
{
    char a[100];
    scanf("%s",a);
    sort(a,a+strlen(a));///从小到大
    cout<<a<<endl;
    sort(a,a+strlen(a),cmp);///从大到小
    cout<<a<<endl;
    cout<<strlen(a)<<endl;///输出字符数组a的长度

}

 （3）sort对string类型的数组按照字典序排序

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
bool cmp(string a,string b)///按照字典序从大到小排序
{
    return a>b;
}
int main()
{
    int i,j;
    string  s[12]=
    {
        "January",
        "February",
        "March",
        "April",
        "May",
        "June",
        "July",
        "August",
        "September",
        "October",
        "November",
        "December"
    };
    sort(s,s+12);///字符串默认按照字典序从小到大排序，数默认按照大小从小到大排序
  for(i=0;i<12;i++)
        cout<<s[i]<<endl;

        cout<<endl;
    sort(s,s+12,cmp);///按照字典序从大到小排序
    for(i=0;i<12;i++)
        cout<<s[i]<<endl;
  return 0;
}

（4）sort对char类型的二维数组进行字典序排序

   错误，不能这样做。同样也不能进行根据字符串长度的排序

   解决方法有：1、使用qsort  2、改用string

（5）sort对string类型的数组根据长度进行排序

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
bool cmp1(string a,string b)///按照长度从小到大排序
{
    return a.length()<b.length();
}
bool cmp2(string a,string b)///按照长度从大到小排序
{
    return a.length()>b.length();
}
int main()
{
    int i,j;
    string  s[12]=
    {
        "January",
        "February",
        "March",
        "April",
        "May",
        "June",
        "July",
        "August",
        "September",
        "October",
        "November",
        "December"
    };
    sort(s,s+12,cmp1);///按照长度从小到大排序
  for(i=0;i<12;i++)
        cout<<s[i]<<endl;

        cout<<endl;
    sort(s,s+12,cmp2);///按照长度从大到小排序
    for(i=0;i<12;i++)
        cout<<s[i]<<endl;
  return 0;
}

6、对结构体数组进行排序（根据结构体中的某元素）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int n=3;
struct Student
{
        char name[20];///姓名
        char id[20]; ///学号
        int score;  ///成绩
        int r;          ///排名
}stu[100010];
/*
(1)如果两个学生的分数不同，则分数高的排在前面
(2)否则，将姓名字典序小的排在前面
*/
bool cmp(Student a,Student b)
{
    if(a.score!=b.score) return a.score>b.score;
    else return strcmp(a.name,b.name)<0;
}

/*
排名的实现，一般规则为：分数不同，排名不同，分数相同排名相同但占用同一个排位
例如：分数为90,88,88,88,86;排名为1,2,2,2,5
*/
void Rank()
{
    int i,j;
    stu[0].r=1;
    for(i=1;i<n;i++)
    {
        if(stu[i].score==stu[i-1].score) stu[i].r=stu[i-1].r;
        else stu[i].r=i+1;
    }
}
int main()
{
    int i,j;
    stu[0]={"guo","001",82,3};///这样赋值不对，算了，以后再改吧
    stu[1]={"zhang","002",82,3};
    stu[2]={"wu","003",99,2};
    sort(stu,stu+n,cmp);
    for(i=0;i<n;i++)
        cout<<stu[i]<<endl;
}

C++ Sort函数详解

前言 ：sort函数是algorithm库下的一个函数，sort函数是不稳定的，即大小相同的元素在排序后相对顺序可能发生改变，如果某些场景需要保持相同元素间的相对顺序，可使用stable_sort函数，这里不过多介绍。

一、sort函数调用的两种方式

• 默认: 两个参数first,last，将[first, last)区间内元素升序排列。【注意区间为左闭右开】

• 自定义排序: 需用户指定排序规则Compare comp,将 [first, last)区间内的元素按照用户指定的顺序排列。

二、sort函数使用场景

由于在排序过程中涉及到元素交换等操作，所以sort函数仅支持可随机访问的容器，如数组， string、vector、deque等。

三、sort函数排序原理

​ sort()并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。

​ 所以无论元素初始时为何种状态，sort()的平均排序复杂度为均为O(N*log2(N)) ，具有不错的的性能，在刷算法题时，可以直接使用sort()来对数据进行排序，而不需手动编写排序函数。

四、sort函数使用案例

1.升序排列

sort函数如果不传入第三个参数，则默认是升序排列。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    // 方式一、使用数组
    int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(a, a + 10);  // 10为元素个数

    for (int i = 0; i < 10; i++) cout << a[i] << ' ';		// 输出排序后数组
    cout << endl;

    // 方式二、使用 vector
    vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(arr.begin(), arr.end());  // 10为元素个数
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';	// 输出排序后数组

    return 0;
}

2.降序排列

• 实现方式1

实现降序排列，需传入第三个参数–比较函数，greater<type>()，这里的元素为int 类型，即函数为 greater<int>(); 如果是其他基本数据类型如float、double、long等也是同理。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    // 方式一、使用数组
    int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(a, a + 10, greater<int>());  // 10为元素个数

    for (int i = 0; i < 10; i++) cout << a[i] << ' ';		// 输出排序后数组
    cout << endl;	// 输出 9 8 7 6 5 4 3 2 1 0 

    // 方式二、使用 vector
    vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(arr.begin(), arr.end(), greater<int>()); 
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';	// 输出排序后数组

    return 0;
}

• 实现方式2

我们也可以使用自定义的比较函数，函数的返回值为bool类型， 例如

bool cmp(int num1, int num2) {
    return num1 > num2;     // 可以简单理解为 > 降序排列;  <  升序排列
}

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(int num1, int num2) {
    return num1 > num2;     // 可以简单理解为 >： 降序排列;  < ： 升序排列
}

int main() {
    // 一、使用数组
    int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(a, a + 10, cmp);  // 使用自定义排序函数

    for (int i = 0; i < 10; i++) cout << a[i] << ' ';		// 输出排序后数组
    cout << endl;	// 输出 9 8 7 6 5 4 3 2 1 0 

    // 二、使用 vector
    vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
    sort(arr.begin(), arr.end(), cmp);   // 使用自定义排序函数
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';	// 输出排序后数组

    return 0;
}

3.结构体排序(自定义比较函数)

​ 要对元素进行排序，前提是元素之间可以进行比较，即谁大谁小。 基本数据类型可直接进行大小比较， 但结构体元素之间的大小关系需要我们自己指定，如果不指定，则结构体之间大小关系就不确定，则不能够排序。

结构体排序案例1: 对学生信息进行排序

学生有姓名，分数两个属性,

struct Student {    // 学生结构体
    string name;    // 学生姓名
    int grade;      // 学生分数
    Student();  // 无参数构造函数
    Student(string name, int grade) : name(name), grade(grade) {};  // 有参数构造函数
};

需求： 对一个班级内的学生成绩进行排序，首先按成绩进行排序降序排列，若成绩相同，则按照姓名字典顺序升序排列。

• 自定义排序函数

bool cmp(Student s1, Student s2) {  // 自定义排序
    if (s1.grade != s2.grade) {     // 如果学生成绩不相同
        return s1.grade > s2.grade; // 则按照成绩降序排列
    }
    return s1.name < s2.name;   // 否则按照姓名升序排列
}

• 排序代码

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Student {    // 学生结构体
    string name;    // 学生姓名
    int grade;      // 学生分数
    Student();  // 无参数构造函数
    Student(string name, int grade) : name(name), grade(grade) {};  // 有参数构造函数
};

bool cmp(Student s1, Student s2) {  // 自定义排序
    if (s1.grade != s2.grade) {     // 如果学生成绩不同
        return s1.grade > s2.grade; // 则按照成绩降序排列
    }
    return s1.name < s2.name;   // 否则按照姓名升序排列
}

int main() {
    vector<Student> studs;
    studs.emplace_back("Bob", 80);
    studs.emplace_back("Ali", 90);
    studs.emplace_back("Ann", 85);
    studs.emplace_back("Liming", 90);
    studs.emplace_back("Trump", 79);
    studs.emplace_back("Fury", 58);
    studs.emplace_back("Jam", 62);
    studs.emplace_back("Lucy", 89);

    sort(studs.begin(), studs.end(), cmp);  // 排序
    for (int i = 0; i < studs.size(); i++) {    // 输出结果
        cout << studs[i].name << "\t" << studs[i].grade << endl;
    }
    return 0;
}

五、自定义comp函数返回true或false作用

bool cmp(int num1, int num2) {	// 实现降序排列
    return num1 > num2;	// num1大于num2时返回true，否则返回false
}

自定义函数返回值为bool类型

• 若返回true，则表示num1 与num2应该交换顺序；
• 若返回false, 则num1 与num2 保持原有顺序；

下面举例说明自定义比较函数的执行过程。

对 2, 5, 1, 3, 4 降序排列
调用cmp函数时，将5赋值给num1, 2赋值给num2 (注意顺序)
5 > 2, 返回true，num1 与 num2需进行交换；即5应该在2的前面
数组变为  5, 2, 1, 3, 4

第二次 将3赋值给num1, 1赋值给num2，
3 > 1, 返回true，num1 与 num2需进行交换；即3应该在1的前面
数组变为  5, 2, 3, 1, 4

之后经过数次的比较与交换最终排序完成。
最终得到 5 4 3 2 1 

六、参考文章链接

https://www.cplusplus.com/reference/algorithm/sort/

https://blog.csdn.net/qq_41575507/article/details/105936466

胡凡算法笔记