剑指信奥 | C++ 之 STL - 算法 sort

剑指信奥｜C++ 之 STL 算法 sort

先来后到，无处不在

排序

排序 sort 系列算法是 C++ STL 算法中的一大分类。

排序是算法中十分常见以及非常重要的一种操作，这个操作的主要过程是把一系列的数据按照我们指定的顺序排列好。

排序到底在做什么？在开始学习算法之前，我们先做一下直观的了解。

最为常见的顺序就是升序和降序，比如以一组数：

1, 3, 5, 7, 2, 4, 6, 8

按数值大小进行排序，那么 —

升序：1，2，3，4，5，6，7，8

降序：8，7，6，5，4，3，2，1

这就是排序。

sort

在 STL 的排序算法中，sort() 是最为常用的一个。

sort() 默认按照升序排列指定范围内的元素，需要注意的是，sort() 只能应用于随机访问迭代器，并且不保证维持相等元素顺序。

基本的 sort() 函数接收 2 个参数：

表示范围起点的随机访问迭代器 first
表示范围终点的随机访问迭代器 last

代码示例：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {

    vector<int> vi = {1, 3, 5, 7, 2, 4, 6, 8};

    // 声明迭代器
    vector<int>::iterator first, last;

    // 区间范围是 [first, last)
    first = vi.begin();
    last = vi.end();

    // 调用 sort 函数排序
    sort(first, last);

    // 输出 vi
    for (auto i = first; i != last; ++i) {
        cout << *i << "\t";
    }

    return 0;
}

/*
 output
    1	 2	3	4	5	6	7	8	
 */

排序也是可变序列的算法，经过排序，序列元素的数量没有变化，但是相互顺序往往会发生变化。

需要注意，默认的排序是升序。

sort 的重载

sort() 有一个重载的函数，相对于上一个而言，多了一个参数，这个参数是一个二元比较函数 comp。

compare 比较，就是字面的含义，按某种方式比较大小，在排序中，它是特指一个二元函数。

重载的 sort() 函数接收 3 个参数：

表示范围起点的随机访问迭代器 first
表示范围终点的随机访问迭代器 last
比较函数对象 comp

代码示例：

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional> // 使用仿函数需引入

using namespace std;

int main() {

    vector<int> vi = {1, 3, 5, 7, 2, 4, 6, 8};

    // 声明迭代器
    vector<int>::iterator first, last;

    // 区间范围是 [first, last)
    first = vi.begin();
    last = vi.end();

    // 调用重载的 sort 函数排序
    sort(first, last, greater<>()); // 仿函数 greater

    // 输出 vi
    for (auto i = first; i != last; ++i) {
        cout << *i << "\t";
    }

    return 0;
}

/*
 output
    8	 7	6	5	4	3	2	1
 */

这段代码中的序列与上一段示例是一样的，从输出结果上看，已经实现了降序。

关键就在于我们的 sort() 函数有了第三个参数 greater<>()，注意这个比较函数并不是我们自定义的，它来自头文件 functional。

functional 中包含一系列的 仿函数 functor，其中运算类的仿函数都可以用于排序算法，作为比较函数使用，这些仿函数有：

equal_to 相等
not_equal_to 不等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于

含义非常明确。

当然除了使用系统的仿函数，我们还可以使用自定义的比较函数。

最后，我们使用自定义的比较函数做一份示例代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

// 比较函数
inline bool comp(string x, string y) {
    return x.length() < y.length();
}

int main() {

    vector<string> vi = {"raspberry", "arbutus", "orange", "haw"};

    // 声明迭代器
    vector<string>::iterator first, last;

    // 区间范围是 [first, last)
    first = vi.begin();
    last = vi.end();

    // 调用 sort 函数排序
    sort(first, last);

    // 输出 vi
    cout << "默认降序：" << endl;
    for (auto i = first; i != last; ++i) {
        cout << *i << "\t";
    }
    // 调用重载 sort 函数排序
    sort(first, last, comp);

    // 输出 vi
    cout << endl << "比较函数：" << endl;
    for (auto i = first; i != last; ++i) {
        cout << *i << "\t";
    }

    return 0;
}

/*
 output
    默认降序：
    arbutus	haw	orange	raspberry	
    比较函数：
    haw	  orange    arbutus	raspberry	
 */

这段代码中，我们首先使用默认的 sort() 函数，是按照字母序的升序输出。

然后，使用定的比较函数 comp 进行排序，比较函数是按照元素字符串的长度降序输出，结果也是正确的。

信奥竞赛

系列