C++11时代的标准库快餐教程(3) - 排序

简介: 讲完容器之后,我们迅速进入到算法部分。首先我们就切入到传统认为算法中最重要的排序算法

排序

讲完容器之后,我们迅速进入到算法部分。
首先看一下,我们这讲在整个算法大图的中位置:

_

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

计数

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

算法1: std::count,数一数跟这个值相等的对象有多少个。
我们看一个例子,数数vector中有几个1:

    std::vector<int> 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:"<<nums<<std::endl;

算法2: std::count_if,count升级版,可以提供一个条件判断的函数来进行判断。
我们看一个例子,判断是奇偶还是偶数:

    std::vector<int> 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:"<<nums<<std::endl;

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<<std::endl;
    auto min = std::min_element(odd_even.cbegin(), odd_even.cend());
    std::cout << "min of odd_even is:"<<*min<<std::endl;

排序

在《数据结构》课中,讲完各种数据结构了之后,重头戏就变成了排序和查找。
我们上一讲主要是线性表、链表和二叉排序树。这一讲就重点说说排序和查找。

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

_

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

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

排序算法

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

_

在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<int>());

有一点需要注意,因为是要改变内容的,所以迭代器不能用常量的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<int>());

排序后是这样的:

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!"<<std::endl;
    }else{
        std::cout<<"cannot find 97..."<<std::endl;
    }

输出当然是“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用于不想做排序只想获取最大最小值。

目录
相关文章
|
2月前
|
算法 C++ 容器
C++标准库(速查)总结
C++标准库(速查)总结
74 6
|
2月前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
108 10
|
2月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
74 5
|
2月前
|
算法 数据挖掘 Shell
「毅硕|生信教程」 micromamba:mamba的C++实现,超越conda
还在为生信软件的安装配置而烦恼?micromamba(micromamba是mamba包管理器的小型版本,采用C++实现,具有mamba的核心功能,且体积更小,可以脱离conda独立运行,更易于部署)帮你解决!
70 1
|
2月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
67 1
|
2月前
|
存储 C++
c++的指针完整教程
本文提供了一个全面的C++指针教程,包括指针的声明与初始化、访问指针指向的值、指针运算、指针与函数的关系、动态内存分配,以及不同类型指针(如一级指针、二级指针、整型指针、字符指针、数组指针、函数指针、成员指针、void指针)的介绍,还提到了不同位数机器上指针大小的差异。
55 1
|
2月前
|
Linux C语言 C++
vsCode远程执行c和c++代码并操控linux服务器完整教程
这篇文章提供了一个完整的教程,介绍如何在Visual Studio Code中配置和使用插件来远程执行C和C++代码,并操控Linux服务器,包括安装VSCode、安装插件、配置插件、配置编译工具、升级glibc和编写代码进行调试的步骤。
321 0
vsCode远程执行c和c++代码并操控linux服务器完整教程
|
3月前
|
编译器 API C语言
超级好用的C++实用库之跨平台实用方法
超级好用的C++实用库之跨平台实用方法
42 6
|
16天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
26 2
|
22天前
|
存储 编译器 C++
【c++】类和对象(下)(取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象)
本文介绍了C++中类和对象的高级特性,包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项,帮助读者深入了解C++面向对象编程的核心机制。
55 5