容器元素排序
- How to do it…
- How it works…

容器元素排序

排序是一项很常见的任务，并且可以通过各种各样的方式进行。每个计算机科学专业的学生，都学过很多排序算法(包括这些算法的性能和稳定性)。

因为这是个已解决的问题，所以开发者没必要浪费时间再次来解决排序问题，除非是出于学习的目的。

How to do it…

本节中，我们将展示如何使用std::sort和std::partial_sort。

首先，包含必要的头文件和声明所使用的命名空间。

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <random>
using namespace std;

我们将打印整数在vector出现的次数，为了缩短任务代码的长度，我们在这里写一个辅助函数：

static void print(const vector<int> &v)
{
    copy(begin(v), end(v), ostream_iterator<int>{cout, ", "});
    cout << '\n';
}

我们开始实例化一个vector：

int main()
{
    vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

因为我们将使用不同的排序函数将vector多次打乱，所以我们需要一个随机数生成器：
```
    random_device rd;
    mt19937 g {rd()};
```
std::is_sorted函数会告诉我们，容器内部的值是否已经经过排序。所以这行将打印到屏幕上：
```
    cout << is_sorted(begin(v), end(v)) << '\n';
```
std::shuffle将打乱vector中的内容，之后我们会再次对vector进行排序。前两个参数是容器的首尾迭代器，第三个参数是一个随机数生成器：
```
    shuffle(begin(v), end(v), g);
```
现在is_sorted函数将返回false，所以0将打印在屏幕上，vector的元素总量和具体数值都没有变，不过顺序发生了变化。我们会将函数的返回值再次打印在屏幕上：
```
    cout << is_sorted(begin(v), end(v)) << '\n';
    print(v);
```

现在，在通过std::sort对vector进行排序。然后打印是否排序的结果：

    sort(begin(v), end(v));
    cout << is_sorted(begin(v), end(v)) << '\n';
    print(v);

另一个比较有趣的函数是std::partition。有时候，并不需要对列表完全进行排序，只需要比它前面的某些值小就可以。所以，让使用partition将数值小于5的元素排到前面，并打印它们：
```
    shuffle(begin(v), end(v), g);
    partition(begin(v), end(v), [] (int i) { return i < 5; });
    print(v);
```
下一个与排序相关的函数是std::partial_sort。我们可以使用这个函数对容器的内容进行排序，不过只是在某种程度上的排序。其会将vector中最小的N个数，放在容器的前半部分。其余的留在vector的后半部分，不进行排序：
```
    shuffle(begin(v), end(v), g);
    auto middle (next(begin(v), int(v.size()) / 2));
    partial_sort(begin(v), middle, end(v));
    print(v);
```

当我们要对没做比较操作符的结构体进行比较，该怎么办呢？让我们来定义一个结构体，然后用这个结构体来实例化一个vector：

    struct mystruct {
    int a;
    int b;
    };
    vector<mystruct> mv { {5, 100}, {1, 50}, {-123, 1000},
                       {3, 70}, {-10, 20} };

std::sort函数可以将比较函数作为第三个参数进行传入。让我们来使用它，并且传递一个比较函数。为了展示其实如何工作的，我们会对其第二个成员b进行比较。这样，我们将按mystruct::b的顺序进行排序，而非mystruct::a的顺序：
```
    sort(begin(mv), end(mv),
    [] (const mystruct &lhs, const mystruct &rhs) {
        return lhs.b < rhs.b;
    });
```

最后一步则是打印已经排序的vector：

    for (const auto &[a, b] : mv) {
        cout << "{" << a << ", " << b << "} ";
    }
    cout << '\n';
}

编译运行程序。第一个1是由std::is_sorted所返回的。之后将vector进行打乱后，is_sorted就返回0。第三行是打乱后的vector。下一个1是使用sort之后进行打印的。然后，vector会被再次打乱，并且使用std::partition对部分元素进行排序。我们可以看到所有比5小的元素都在左边，比5大的都在右边。我们暂且将现在的顺序认为是乱序。倒数第二行展示了std::partial_sort的结果。前半部分的内容进行了严格的排序，而后半部分则没有。最后一样，我们将打印mystruct实例的结果。其结果是严格根据第二个成员变量的值进行排序的：
```
$ ./sorting_containers
1
0
7, 1, 4, 6, 8, 9, 5, 2, 3, 10,
1
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
1, 2, 4, 3, 5, 7, 8, 10, 9, 6,
1, 2, 3, 4, 5, 9, 8, 10, 7, 6,
{-10, 20} {1, 50} {3, 70} {5, 100} {-123, 1000}
```

How it works…

这里我们使用了很多与排序算法相关的函数：

算法函数	作用
std::sort	接受一定范围的元素，并对元素进行排序。
std::is_sorted	接受一定范围的元素，并判断该范围的元素是否经过排序。
std::shuffle	类似于反排序函数；其接受一定范围的元素，并打乱这些元素。
std::partial_sort	接受一定范围的元素和另一个迭代器，前两个参数决定排序的范围，后两个参数决定不排序的范围。
std::partition	能够接受谓词函数。所有元素都会在谓词函数返回true时，被移动到范围的前端。剩下的将放在范围的后方。

对于没有实现比较操作符的对象来说，想要排序就需要提供一个自定义的比较函数。其签名为bool function_name(const T &lhs, const T &rhs)，并且在执行过程中无副作用。

当然排序还有其他类似std::stable_sort的函数，其能保证排序后元素的原始顺序，std::stable_partition也有类似的功能。

Note:

std::sort对于排序有不同的实现。根据所提供的迭代器参数，其实现分为选择排序、插入排序、合并排序，对于元素数量较少的容器可以完全进行优化。在使用者的角度，我们通常都不需要了解这些。