C++11时代的标准库快餐教程(3) - 排序
发布日期:2021-08-26 15:47:08 浏览次数:4 分类:技术文章

本文共 5475 字,大约阅读时间需要 18 分钟。

排序

讲完容器之后,我们迅速进入到算法部分。

首先看一下,我们这讲在整个算法大图的中位置:

_

在进入排序相关之前,我们把虽然与排序无关,但是也有关联的计数和最大值最小值部分先看一下。算是对算法部分作个预热,将来会广泛出场的lambda表达式也先借机会亮亮相。

计数

计数的目的,是数一数,在容器里,符合某一条件的元素有多少个。

算法1: std::count,数一数跟这个值相等的对象有多少个。

我们看一个例子,数数vector中有几个1:

std::vector
bit_container; int nums; bit_container.push_back(1); bit_container.push_back(1); bit_container.push_back(0); bit_container.push_back(1); nums = std::count(bit_container.cbegin(),bit_container.cend(),1); std::cout<<"Number of 1 is:"<
<

算法2: std::count_if,count升级版,可以提供一个条件判断的函数来进行判断。

我们看一个例子,判断是奇偶还是偶数:

std::vector
odd_even; for(int i=0;i<100;i++){ odd_even.push_back(i+1); } nums = std::count_if(odd_even.cbegin(),odd_even.cend(), [](int elem){ return elem%2==0; }); std::cout<<"Odds from 1 to 100 is:"<
<

count_if的第三个参数,是一个可调用对象,它可以是函数,仿函数(函数对象)和lambda表达式。

lambda表达式是一种匿名函数,特别适合用于STL的算法中。这是C++11带给算法的礼物。
lambda表达式的形式为:

[ 变量捕获列表 ]( 形式参数列表 ) -> 返回值类型 { 函数体 }

如果返回值类型可以像auto一样被推断出来,就不用写了。变量捕获用不到可以为空,参数没有也可以为空。只有函数体是必要的。

我们看看上例中的这个lambda表达式:

[](int elem){                             return elem%2==0;                         });
  • 不需要捕获变量
  • 参数是int elem
  • 返回值类型因为只可能是bool,就让编译器自己推断去
  • 函数体里就跟普通函数一样,就不多说了

关于function, functor和lambda表达式,我们后面会详细再讲,目前快餐教程,大家先学会能看懂,能用。

最大值和最小值

算法3: std::max_element算法求最大值

算法4: std::min_element算法求最小值

例,求1〜100中的最大值和最小值:

auto max = std::max_element(odd_even.cbegin(), odd_even.cend());    std::cout << "max of odd_even is:"<<*max<

排序

在《数据结构》课中,讲完各种数据结构了之后,重头戏就变成了排序和查找。

我们上一讲主要是线性表、链表和二叉排序树。这一讲就重点说说排序和查找。

我们先来一张排序相关的总图,然后再去看每一部分的细图:

_

从上图中可以看到,排序相关的主要由三部分构成:

  • 排序算法:真正做排序的算法
  • 检查算法:确定是否是排序的,如果不是,是从哪里开始无序的
  • 在已排序区间上的操作:排好序了,有什么用处,这些算法是消费排序带来的好处的。最重要的就是二分法查找了。

排序算法

我们再聚一下焦,看看排序算法都包括哪些内容:

_

在STL的排序算法中,主要有三种算法会被用到:快速排序,归并排序和堆排序。

算法 sort partial_sort stable_sort
默认算法 快速排序 堆排序 归并排序
优点 很好的平均效率 在任何情况下都保持n*log(n)的复杂度 保持相等元素的相对顺序
不足 最差情况下效率较差 实际情况中比快速排序慢2~5倍 内存不足时复杂度提高log(n)倍
额外好处 可以只做前n个排序就停止

sort - 快速排序

快速排序在不是最差情况下的平均速度最快,所以它是默认的算法:

从小到大是默认的行为:

std::sort(odd_even.begin(),odd_even.end());

从大到小可以通过第三个参数,传入一个比较函数来实现:

std::sort(odd_even.begin(),odd_even.end(),std::greater
());

有一点需要注意,因为是要改变内容的,所以迭代器不能用常量的cbegin和cend.

stable_sort 归并排序

stable_sort的参数与sort完全一致。可以无缝替换使用,视内存和需求决定。

例:

std::stable_sort(odd_even.begin(), odd_even.end());

partial_sort 部分排序,堆排序

部分排序除了指定起点和终点之外,还需要一个参数指定排序的终点。

比如下面的例子是:只排出前三大的,后面就不管了。

std::partial_sort(odd_even.begin(), odd_even.begin()+3, odd_even.end(), std::greater
());

排序后是这样的:

100 99 98 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

堆排序

堆有两种用法,一种是随时更新堆,就像set和map一样。后面我们会介绍priority_queue容器,就是这方面的专用容器;另一种就是将线性结构一次性建个堆,不一定随时维护。这样就只有一次性的成本。

std::make_heap建堆

比如把上例中的vector来建个堆:

std::make_heap(odd_even.begin(), odd_even.end());

堆中的组织结构是这样的:

100 92 99 76 91 98 60 68 75 84 90 97 52 56 59 64 67 72 74 80 83 88 89 95 96 50 51 54 55 58 28 62 63 66 32 70 71 73 36 78 79 82 40 86 87 47 46 93 41 22 94 49 23 10 24 53 25 11 26 57 27 12 7 61 29 13 30 65 31 17 8 69 33 18 34 4 35 20 15 77 37 19 38 81 39 21 16 85 44 42 45 5 2 43 14 3 48 1 6 9

100是树根,左子树是92,右子树是99.

然后92的左子树是76,右子树是91. 99的左子树是98, 右子树是60. 以此类推,我们画一下前4层的图:

100

如果这么看起来实在太费劲了,我们可以将堆重新变成排序好的结果:

std::sort_heap(odd_even.begin(), odd_even.end());

打印出来就又变成有序的了。不过,堆的结构也被破坏了,还需要重新建堆。

二分法查找

排好序了,最常见的应用之一就是二分法查找。

我们看一个例子:

if(std::binary_search(odd_even.cbegin(), odd_even.cend(), 97))    {        std::cout<<"found 97!"<

输出当然是“found 97!”了。

因为二分查找不修改迭代器的值,所以又可以使用只读的迭代器cbegin和cend了。

划分

按第n个元素分成两部分

比如,在上面排序的基础上,我们想把比4小的排在4前面,比4大的排在后面:

std::nth_element(odd_even.begin(), odd_even.begin()+4, odd_even.end());

排序后的结果如下:

1 2 3 4 5 6 7 8 15 16 14 9 10 11 12 13 17 18 20 19 21 42 43 41 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 44 45 47 46 48 95 96 94 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 97 98 99 100

从上面的结果可以看到,排序的结果中,并不是完全有序的。在满足要求的情况下,并没有对4以后的数做更进一步的有序化。这样会带来性能的提升。

按照一定条件划分成两部分

前面的nth_element是根据某个值分成两部分,而partition算法可以有更多的玩法。

比如下面,我们按奇偶性,把偶数排到前面:

std::partition(odd_even.begin(), odd_even.end(),                   [](int elem){return elem %2 == 0;});

重新排列之后变成这样:

100 2 98 4 96 6 94 8 92 10 90 12 88 14 86 16 84 18 82 20 80 22 78 24 76 26 74 28 72 30 70 32 68 34 66 36 64 38 62 40 60 42 58 44 56 46 54 48 52 50 51 49 53 47 55 45 57 43 59 41 61 39 63 37 65 35 67 33 69 31 71 29 73 27 75 25 77 23 79 21 81 19 83 17 85 15 87 13 89 11 91 9 93 7 95 5 97 3 99 1

正如排序有稳定排序一样,std::partition把顺序排乱了,我们不喜欢。这时有内部排序稳定的std::stable_partition算法出马:

std::stable_partition(odd_even.begin(), odd_even.end(), [](int elem){return elem %2 == 0;});

排序结果如下:

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99

小结

这节我们学习了排序算法的主要框架:快速排序sort,稳定的归并排序stable_sort,可以部分排序的堆排序算法partial_sort.

我们可以显式建堆make_heap,也可以将堆转化成排序sort_heap。
二分查找binary_search用在有序结构上,速度比线性查找要快得多。
nth_element可以按某个值划分成两部分,partition可以应用更复杂的条件,但是不稳定。保持内部排序稳定需要用stable_partition.
count和count_if用来计数。
max_element和min_element用于不想做排序只想获取最大最小值。

转载地址:https://blog.csdn.net/weixin_33890499/article/details/90585655 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:码栈开发手册(五)---可视化方式开发(模块详解--数据视图)
下一篇:【知云】第一期:云计算和传统的IDC究竟有什么不同?

发表评论

最新留言

很好
[***.229.124.182]2024年03月15日 12时10分33秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java jdk win10 1335_win10下安装java jdk,tomcat 2019-04-21
java list二分查找_java中的ArrayList和LinkedList的二分查找速度比 | 学步园 2019-04-21
php中的变量名称用什么表示,PHP变量,方法,类等名称中的有效字符是什么? 2019-04-21
pic32mx是什么cpu_PIC32MX单片机外设库使用(Ⅰ)- 系统时钟及I/O口基本设置 2019-04-21
用c 在mysql上存图片_C 批量保存图片进 mysql 利用MYSQL_BIND插入longblob 2019-04-21
mysql 1045 28000_mysql报关于用户密码1045(28000),几种处理方法 (zhuan) 2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳 2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2019-04-21
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳 2019-04-21
java对象去重复_JAVA中List对象去除重复值的方法 2019-04-21
java bss_[转] .bss段和.data段的区别 2019-04-21
java上传图片损坏_大神求助 上传图片后 图片损坏 2019-04-21
java socket唯一标识符_Java Socket编程之常识网络基础知识 2019-04-21
java给xyz大小排序_java递归实现string xyz排序 2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置 2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用 2019-04-21
java cache 有效期_springboot cache 自定义过期时间及自定义缓存key前缀 2019-04-21
java实验一目的_Java实验报告(实验一) 2019-04-21
java+native+字段_+Java中的native关键字浅析(Java+Native+Interface)++ 2019-04-21
php 内存泄露检测工具,php - 诊断内存泄漏 - 允许#bytes的内存大小耗尽 2019-04-21