C++中 Sort函数详细解析

 更新时间:2022年8月18日 19:21  点击:63 作者:zhangbw~

前言 

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函数 内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!

原文出处:https://blog.csdn.net/VariatioZbw/article/details/125155432

相关文章

  • php正确禁用eval函数与误区介绍

    eval函数在php中是一个函数并不是系统组件函数,我们在php.ini中的disable_functions是无法禁止它的,因这他不是一个php_function哦。 eval()针对php安全来说具有很...2016-11-25
  • Python astype(np.float)函数使用方法解析

    这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08
  • Python中的imread()函数用法说明

    这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
  • PHP用strstr()函数阻止垃圾评论(通过判断a标记)

    strstr() 函数搜索一个字符串在另一个字符串中的第一次出现。该函数返回字符串的其余部分(从匹配点)。如果未找到所搜索的字符串,则返回 false。语法:strstr(string,search)参数string,必需。规定被搜索的字符串。 参数sea...2013-10-04
  • C++中取余运算的实现

    这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
  • PHP函数分享之curl方式取得数据、模拟登陆、POST数据

    废话不多说直接上代码复制代码 代码如下:/********************** curl 系列 ***********************///直接通过curl方式取得数据(包含POST、HEADER等)/* * $url: 如果非数组,则为http;如是数组,则为https * $header:...2014-06-07
  • php中的foreach函数的2种用法

    Foreach 函数(PHP4/PHP5)foreach 语法结构提供了遍历数组的简单方式。foreach 仅能够应用于数组和对象,如果尝试应用于其他数据类型的变量,或者未初始化的变量将发出错误信息。...2013-09-28
  • PHP函数strip_tags的一个bug浅析

    PHP 函数 strip_tags 提供了从字符串中去除 HTML 和 PHP 标记的功能,该函数尝试返回给定的字符串 str 去除空字符、HTML 和 PHP 标记后的结果。由于 strip_tags() 无法实际验证 HTML,不完整或者破损标签将导致更多的数...2014-05-31
  • PHP编码转换函数mb_convert_encoding与iconv用法

    文章来实现一个PHP编码转换函数mb_convert_encoding与iconv用法,希望例子能帮助到各位。 将一个短信接口代码从apache迁移到nginx+php-fpm后,发现无法发出短信了,查...2016-11-25
  • php的mail函数发送UTF-8编码中文邮件时标题乱码的解决办法

    最近遇到一个问题,就是在使用php的mail函数发送utf-8编码的中文邮件时标题出现乱码现象,而邮件正文却是正确的。最初以为是页面编码的问题,发现页面编码utf-8没有问题啊,找了半天原因,最后找到了问题所在。 1.使用 PEAR 的...2015-10-21
  • C++万能库头文件在vs中的安装步骤(图文)

    这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
  • php数字每三位加逗号的功能函数

    php实现数字格式化,数字每三位加逗号的功能函数,具体代码如下: function num_format($num){ if(!is_numeric($num)){ return false; } $num = explode('.',$num);//把整数和小数分开 $rl = $num[1];//小数部分的值...2015-10-23
  • 一组PHP加密解密函数分享

    复制代码 代码如下:<?php/***功能:对字符串进行加密处理*参数一:需要加密的内容*参数二:密钥*/function passport_encrypt($str,$key){ //加密函数srand((double)microtime() * 1000000);$encrypt_key=md5(rand(0, 32000...2014-06-07
  • PHP is_subclass_of函数的一个BUG和解决方法

    is_subclass_of的作用:复制代码 代码如下:bool is_subclass_of ( object object, string class_name )如果对象 object 所属类是类 class_name 的子类,则返回 TRUE,否则返回 FALSE。注: 自 PHP 5.0.3 起也可以用一个字符...2014-06-07
  • PHP生成不同颜色、不同大小的tag标签函数

    复制代码 代码如下:function getTagStyle(){ $minFontSize=8; //最小字体大小,可根据需要自行更改 $maxFontSize=18; //最大字体大小,可根据需要自行更改 return 'font-size:'.($minFontSize+lcg_value()*(abs($maxFo...2013-10-04
  • PHP加密解密函数详解

    分享一个PHP加密解密的函数,此函数实现了对部分变量值的加密的功能。 加密代码如下: /* *功能:对字符串进行加密处理 *参数一:需要加密的内容 *参数二:密钥 */ function passport_encrypt($str,$key){ //加密函数 srand(...2015-10-30
  • 详解C++ bitset用法

    这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
  • php中利用str_pad函数生成数字递增形式的产品编号

    解决办法:$str=”QB”.str_pad(($maxid[0]["max(id)"]+1),5,”0″,STR_PAD_LEFT ); 其中$maxid[0]["max(id)"]+1) 是利用max函数从数据库中找也ID最大的一个值, ID为主键,不会重复。 str_pad() 函数把字符串填充为指...2013-10-04
  • php简单日历函数

    本文实例讲述了php实现的日历程序。分享给大家供大家参考。具体如下:<&#63;php /* * php 输出日历程序 */ header("Content-type: text/html;charset=utf-8"); $year=(!isset($_GET['year'])||$_GET['year']=="")&#63;...2015-10-30
  • PHP中header()函数有什么用?常见header 状态

    在php中header()函数是很大的作用可以发送各种状态代码,也可以实现一些输出下载,下面我们一起来看看一些相关实例吧。 什么是头信息? 这里只作简单解释,详细的自己看...2016-11-25