排序

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

algo_all

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

计数

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

算法1: std::count，数一数跟这个值相等的对象有多少个。
我们看一个例子，数数vector<int>中有几个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;

排序

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

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

sort_all

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

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

排序算法

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

sort_algo

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

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层的图：

tree

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

    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用于不想做排序只想获取最大最小值。