大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

C++Sort函数详解-创新互联

C++ Sort函数详解

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

成都创新互联主营椒江网站建设的网络公司,主营网站建设方案,成都APP应用开发,椒江h5成都微信小程序搭建,椒江网站营销推广欢迎椒江等地区企业咨询
一、sort函数调用的两种方式
方式一(默认)void sort (RandomAccessIterator first, RandomAccessIterator last);
方式二(自定义)void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  • 默认: 两个参数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#include#include

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
    vectorarr = {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(),这里的元素为int类型,即函数为greater(); 如果是其他基本数据类型如floatdoublelong等也是同理。

#include#include#include

using namespace std;

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

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

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

    return 0;
}
  • 实现方式2

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

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

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
    vectorarr = {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#include#include

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() {vectorstuds;
    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,则表示num1num2应该交换顺序;
  • 若返回false, 则num1num2保持原有顺序;

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

对 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

胡凡算法笔记

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页名称:C++Sort函数详解-创新互联
本文网址:http://dzwzjz.com/article/cdodse.html
在线咨询
服务热线
服务热线:028-86922220
TOP