C++中 Sort函数详细解析

目录
  • 前言
  • 一、sort函数调用的两种方式
  • 二、sort函数使用场景
  • 三、sort函数排序原理
  • 四、sort函数使用案例
    • 1.升序排列
    • 2.降序排列
      • 实现方式1
      • 实现方式2
    • 3.结构体排序(自定义比较函数)
  • 五、自定义comp函数返回true或false作用

前言

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>(); 如果是其他基本数据类型如floatdoublelong等也是同理。

#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,则表示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

到此这篇关于C++中 Sort函数详细解析的文章就介绍到这了,更多相关C++ Sort函数 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++回调函数实现计算器和qsort

    目录 前言 一.计算器 1.switch语句实现 2.回调函数实现 二.qsort 1.冒泡排序 2.qsort 3.qsort排序浮点数 4.qsort排序字符型 5.qsort排序结构体 6.自定义实现my_qsort 总结 前言 回调函数就是一个通过函数指针调用的函数.如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数.回调函数不是由该函数的实现方直接调用,而是在特定的事件或条件发生时由另外的一方调用的,用于对该事件或条件进行响应

  • 带你了解C++中的sort函数

    目录 sort( ) char型数组 char型数组 总结 sort( ) 使用方法: sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(非必填)) 必须加上头文件:#include< algorithm >和using namespace std; 举个栗子: #include<stdio.h> #include<algorithm> using namespace std; int main() { int book[5]={5, 4, 2,

  • C++中sort函数的基础入门使用教程

    前言 STL主要包含容器,迭代器,算法三块内容,用户可以对容器进行一系列的操作,比如遍历和计算,而STL提供的迭代器和容器完美地提供了这样的接口.其中std::vector是最常用的容器之一,vector是一个模板类,定义在命名空间namespace下,使用vector需要在包含相关头文件.今天主要讲解对vector的排序的使用. sort类函数: 函数名 功能描述 sort 对给定区间所有元素进行排序 stable_sort 对给定区间所有元素进行稳定排序 partial_sort 对给定区间

  • 详解C++ sort函数的cmp参数

    目录 1.升序排序 2.降序排序 3.结构体的排序实例 前言: 学算法的第一天你在学冒泡.桶排 在你还没搞明白快排和归并的时候 你已经学到了数据结构最后的堆排序和希尔排序 可以说排序是很多竞赛生的噩梦-- 于是它诞生了 void std::sort() Sort the elements of a sequence using a predicate for comparison. 参数: __first – An iterator. __last – Another iterator. __c

  • 浅析C/C++中sort函数的用法

    sort是STL中提供的算法,头文件为#include<algorithm>以及using namespace std; 函数原型如下: template <class RandomAccessIterator> void sort ( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void sor

  • 通过c++的sort函数实现成绩排序功能

    sort函数用于C++中,对给定区间所有元素进行排序,默认为升序,也可进行降序排序.sort函数进行排序的时间复杂度为n*log2n,比冒泡之类的排序算法效率要高,sort函数包含在头文件为#include<algorithm>的c++标准库中. 题目描述: 有N个学生的数据,将学生数据按成绩高低排序,如果成绩相同则按姓名字符的字母排序,如果姓名的字母序也相同,则按照学生的年龄排序,并输出N个学生排序后的信息. #include<stdio.h> #include<algor

  • C++标准模板库函数sort的那些事儿

    STL里面有个sort函数,可以直接对数组排序,复杂度为n*log2(n).sort()定义在在头文件<algorithm>中.sort函数是标准模板库的函数,已知开始和结束的地址即可进行排序,可以用于比较任何容器(必须满足随机迭代器),任何元素,任何条件,执行速度一般比qsort要快.另外,sort()是类属函数,可以用于比较任何容器,任何元素,任何条件. 具体事例如下:char ch[20]="sdasdacsdasdas";cout<<ch<<

  • C++ sort排序函数用法详解

    目录 用法 两个参数用法 三个参数 string 使用反向迭代器来完成逆序排列 最近在刷ACM经常用到排序,以前老是写冒泡,可把冒泡带到OJ里后发现经常超时,所以本想用快排,可是很多学长推荐用sort函数,因为自己写的快排写不好真的没有sort快,所以毅然决然选择sort函数 用法 1.sort函数可以三个参数也可以两个参数,必须的头文件#include < algorithm>和using namespace std;2.它使用的排序方法是类似于快排的方法,时间复杂度为n*log2(n) 3

  • C++中 Sort函数详细解析

    目录 前言 一.sort函数调用的两种方式 二.sort函数使用场景 三.sort函数排序原理 四.sort函数使用案例 1.升序排列 2.降序排列 实现方式1 实现方式2 3.结构体排序(自定义比较函数) 五.自定义comp函数返回true或false作用 前言 sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使用stable_sort函数,这里不过多介绍. 一.sort函数调用的

  • Python内置函数详细解析

    目录 1.abs 2.all 3.any 4.callable 5.dir 6.id 7.locals 和 globals 8.hash 9.sum 10.getattr.setattr.delattr 前言: Python 自带了很多的内置函数,极大地方便了我们的开发,下面就来挑几个内置函数,看看底层是怎么实现的.内置函数位于 Python/bitlinmodule.c 中. 1.abs abs 的功能是取一个整数的绝对值,或者取一个复数的模. static PyObject * builti

  • Python中enumerate函数代码解析

    enumerate函数用于遍历序列中的元素以及它们的下标. enumerate函数说明: 函数原型:enumerate(sequence, [start=0]) 功能:将可循环序列sequence以start开始分别列出序列数据和数据下标 即对一个可遍历的数据对象(如列表.元组或字符串),enumerate会将该数据对象组合为一个索引序列,同时列出数据和数据下标. 举例说明: 存在一个sequence,对其使用enumerate将会得到如下结果: start        sequence[0]

  • 详解Matlab中 sort 函数用法

    (1)B=sort(A) 对一维或二维数组进行升序排序,并返回排序后的数组,当A为二维时,对数组每一列进行排序. eg: A=[1,5,3],则sort(A)=[1,3,5] A=[1,5,3;2,4,1],则sort(A)=[1,4,1;2,5,3] (2)B=sort(A,dim),对数组按指定方向进行升序排序, dim =1,表示对每一列进行排序,,dim=2表示对每一行进行排序. (3)B=sort(A,dim,mode),mode为指定排序模式,mode为"ascend"时,

  • JS中sort函数排序用法实例分析

    本文实例讲述了JS中sort函数排序用法.分享给大家供大家参考,具体如下: 最近遇到了一个面试题目,关于排序的问题,为了完善自己的知识点,这里就写一下学习笔记 <html> <head> <TITLE>class_obj_js_class</TITLE> <script language=javaScript> //sort()方法默认是按照ASCII码大小排序,看下面两个例子 function sortDemo(){ var a, l; //

  • Es6 Generator函数详细解析

    ECMAScript 6 (简称 ES6 )作为下一代 JavaScript 语言,将 JavaScript 异步编程带入了一个全新的阶段. Generator函数跟普通函数的写法有非常大的区别: 一是,function关键字与函数名之间有一个星号: 二是,函数体内部使用yield语句,定义不同的内部状态(yield在英语里的意思就是"产出"). 本文重点给大家介绍Es6 Generator函数,具体内容如下所示: /* 一.generator函数的定义 1.Generator 函数是

  • php中sort函数排序知识点总结

    在我们进行排序的时候,难免要用到一些函数来执行.php中排序函数有很多种,就拿sort函数来说,在排序的作用发挥上是从低到高,这点是大家要注意的,也算是符合我们生活中的排序习惯.下面我们就php中sort函数的概念.语法.返回值.实例分别带来介绍,一起来体会下它的排序使用吧. 1.概念 用于对数组单元从低到高进行排序. 注意:本函数会为排序的数组中的单元赋予新的键名,这将删除原有的键名而不仅是重新排序. 2.语法 sort(array,sortingtype); 3.返回值 如果成功则返回 TR

  • python中sort()函数用法详解

    目录 1.函数sort()是对列表就地排序 2.函数sort()修改序列,不返回任何值 3.sorted()函数会返回一个排序列表,不改变原有序列 4.函数sort()是升序排序,如何降序排序,需要用到函数reverse() 5.函数sort()排序的高级用法 (1) key参数 (2) reverse参数 补充:python中sort的用法——对列表中的元素按关键字排序 总结 1.函数sort()是对列表就地排序 >>> x=[8,9,0,7,4,5,1,2,3,6] >>

  • C++中的friend函数详细解析

    为什么要使用友元函数 在实现类之间数据共享时,减少系统开销,提高效率.如果类A中的函数要访问类B中的成员(例如:智能指针类的实现),那么类A中该函数要是类B的友元函数.具体来说:为了使其他类的成员函数直接访问该类的私有变量.即:允许外面的类或函数去访问类的私有变量和保护变量,从而使两个类共享同一函数. 实际上具体大概有下面两种情况需要使用友元函数:(1)运算符重载的某些场合需要使用友元.(2)两个类要共享数据的时候. 使用友元函数的优缺点 优点:能够提高效率,表达简单.清晰. 缺点:友元函数破环

随机推荐