3.5.6. C++算法库排序函数

前面学习了八种常用的经典排序算法，这些排序算法中蕴藏着许多算法思维的精髓，需要认真学习的领会。但是在实际编程时，如果每次遇到排序需求的时候都要手工写排序的代码就太累人了。计算机界有一句格言：“不要重复造轮子”。C++语言在它的算法库 algorithm 中已经提供了五个非常好用的排序函数，这些就是已经造好的轮子，在实际编程中拿来用就可以了，不用自己动手做编写排序函数这样的重复造轮子的工作。

本节我们将介绍怎样使用C++算法库中的三个排序函数，以及怎样让自己定义的复杂数据结构支持大小比较运算。首先让我们来了解一下C++的算法库。

3.5.6.1. C++算法库（algorithm）简介

C++的算法库是C++标准模板库STL中的一个通用功能函数库，其中包含一些常用的模板函数，用于执行基本的算法，比如遍历、查找、排序、二分查找等，是STL的三大核心组件之一。要使用算法库中的函数，首先要引入 algorithm 库，并声明使用命名空间 std。

#include <algorithm>

using namespace std;

如果不声明使用 std 命名空间，那么库中所有函数在调用的时候要在函数名前面加上前缀 std::。所以这两句语句是标准配置，在后面的示例代码中就不重复写了。

C++98标准下的算法库函数分为9类共66个函数：

  1. 无修改序列操作（Non-modifying sequence operations），共12个函数，主要包括查找、对比等功能；

  2. 有修改序列操作（Modifying sequence operations），共25个函数，主要包括填充、移动、交换、删除、唯一化、反转、旋转、随机打乱等功能；

  3. 分区（Partitions），共2个函数，分别提供不稳定的分区和稳定的分区两种操作；

  4. 排序（Sorting），共5个函数，分别为不稳定排序、稳定排序、部分排序、复制并部分排序和k位数算法，这是本节要介绍的内容；

  5. 二分查找（Binary search），共4个函数，提供二分查找和边界二分查找的功能；

  6. 归并（Merge），共7个函数，提供有序序列归并、集合交、并、差等功能；

  7. 堆（Heap），共4个函数，提供堆这种数据结构的实现与操作功能；

  8. 最小/最大（Min/max），共4个函数，提供在序列中或单独给出的函数参数中寻找最小值或最大值的功能；

  9. 其他（Other），共3个函数，提供字典序比较、生成排列的功能。

上面这些函数都是在算法编程中经常要使用的基本算法功能，可以说都是复杂算法的基石，都很实用也很重要。一般情况下我们都建议尽量使用这些函数，有三大好处：一是能让代码变得简洁清晰易读，比如用 max(a, b) 来代替 a > b ? a : b；二是这些库函数久经考验，可以担保没有bug存在；三是它们的运行速度都非常快，比如不稳定排序函数 sort() 是优化的快速排序，实际运行速度快于手写的标准快排。

但是有得必有失，要熟练掌握所有这些函数是有点难的，它们往往还都有不止一种用法，所以要分步骤地去逐渐学习掌握。有些功能自己手写很麻烦，比如堆操作、排序等，这些就首先去学习掌握；有些函数自己写一下也很简单，比如最大最小值函数等，这些就慢慢来，有机会的时候试试看，多试几次可能就自然记住了；有些功能自己写一下不算太麻烦，要记住对应的函数反而麻烦，比如一些查找替换类的操作，这些可以根据自己的情况选择不学或者以后再学。

3.5.6.2. 容器、迭代器和范围

C++语言中有一个叫做容器（container）的概念，指可以用来容纳多个同类型数据的数据结构类型。前面我们说过，C++的STL库有三大核心组件，一个是算法库，第二个就是容器库。STL的容器库提供了很多已经实现好的常用数据结构，比如顺序表、链表、集合等等。同一种容器类的不同容器对象（类相当于传统的数据类型，对象类似于传统的变量）可以用来存放不同类型的元素，比如我们可以定义一个 int 型的集合对象，集合元素都是 int 型的整数，也可以再定义一个 char 型的集合对象，里面的集合元素都是 char 型的字符。这些知识在下一章数据结构中会详细讲解，现在只要对容器的概念有个了解即可。

算法库中的所有算法函数都是针对容器中的元素进行操作的，好消息是这里所说的容器，不仅仅是指STL容器库提供的高级容器类，也包括传统的数组。数组是最简单的一种容器！

算法库函数都是比较灵活的，比如用 sort() 对一个数组进行排序，它不是简单地对数组里所有元素排序，而是要提供一头一尾两个位置参数，对这个头尾范围内的元素进行排序。算法函数通过这种方式实现对容器中任意指定的一段元素进行操作。这就引出了一个新的概念：迭代器。

迭代器（iterator）是STL三大核心组件之三，它其实是一个包装过的指针，可以用来指示容器中元素的位置，前后两个迭代器组合起来就可以组成表示容器中一段连续元素的范围（range）。我们知道，指针是有数据类型的，比如有指向 int 的指针，也有指向 char 的指针，它们是不同的类型。STL则把简单的指针包装起来，加了一件名为迭代器的外衣，于是指向不同数据类型元素的迭代器就都具有了相同的类型：iterator 型。对于最简单的数组容器，就直接使用传统的指针，C++会自动在需要的时候给这个指针加上迭代器的外衣包装起来。通过这种方式，就使得算法库中的算法函数可以对任意容器对象中任意数据类型的元素进行操作了。

最后简单说明一下范围（range）这个概念。用一头一尾两个迭代器（或数组元素指针）就可以组成一个范围，范围总是遵守“含头不含尾”的左闭右开原则。

下面以数组为例说明迭代器和范围的用法。假设有一个 int 型数组 d[]，里面已经读入了n个数，从头开始存放。通常，我们会使用一个整数来指示数组中某个特定的位置，称为下标。那么用迭代器，对数组来说就是指针，怎么表示位置和范围呢？

int d[100];
// 定义指针 begin，它指向 d[0] 这个元素，相当于 &d[0]，这就是数组 d 的头迭代器
int *begin = d;
// 定义指针 end，它指向 d[0] 后面第100个元素的位置，相当于 &d[100]，这就是数组 d 的尾迭代器
int *end = begin + 100;
// 但是要注意，end 指向的是 d[99] 后面那个位置，那里实际上已经不在数据 d 的有效范围内了
// 如果要向 end 指向的位置进行读写，就会出现数组越界的段错误
int *p = begin + 10;  // 指针 p 指向 begin 后面第10个元素，即 d[10] 的位置
int *q = p + 10;      // 指针 q 指向 p 后面第10个元素，即 d[20] 的位置
int *r = end - 5;     // 指针 r 指向 end 前面第5个元素，即 d[95] 的位置
// 指针作为数组的迭代器，可以用来循环遍历数组中的全部或部分元素
for (int *s = begin; s < end; ++s) {
        // 从头到尾遍历数组 d 中所有位置，用 *s 表示对应位置的具体元素
        printf("%d\n", *s);
}
for (int *t = end - 1; t >= begin; --t) {
        // 从尾部到头逆向遍历后所有元素
        printf("%d\n", *t);
}
for (int *pt = begin + 50; pt < begin + 60; ++pt) {
        // 从 d[50] 到 d[59] 顺序遍历10个元素
        printf("%d\n", *pt);
}

同一个数组里的前后两个指针可以表示一个范围，规则为左闭右开，即含头不含尾。例如上面的示例代码中，begin 和 end 就可以组成一个范围，包含了整个数组 d[] 中的所有100个元素。这里也可以看出含头不含尾规则下，end 指针其实指向的是一个虚拟的 d[100] 的位置，它在数组最后一个元素 d[99] 的后面，这一点千万记清，不能直接使用 *end，会导致数组越界错误。总之，一段范围的尾迭代器，指向的是不含在范围内的位置。

含头不含尾这个规则能引出一个便利的运算规则：对于任意一对头尾迭代器（指针）所表示的范围，其长度等于尾迭代器减去头迭代器的差。例如上面的示例中，end - begin 等于100，q - p 则会等于10。如果头尾迭代器相等，其差必然为0，表示该范围为空，长度为0，这也是一目了然的结果。

3.5.6.3. C++结构类型的大小比较

C++算法库提供的排序类函数都是基于元素比较的，最低限度来说，它们要求待排序元素的数据类型至少支持“小于”这一种比较运算。

对于 char, int, long long, double 这些C++内置数据类型，它们本身支持所有六种大小比较运算，是不存在任何问题的。但是实际编程时经常会有一些复杂的数据类型，通常是用C++结构来自己构造出来的所谓“派生数据类型”。例如我们有这样一份学生成绩表，每一位学生有学号（整数）、姓名（字符串）、语文数学两门课的期末考试成绩（均为整数）四个字段，通常我们会定义一个结构类型来紧凑地表示这些数据：

struct Student {
        int stu_no;      // 学号
        string name;     // 姓名
        int chn;         // 语文成绩
        int math;        // 数学成绩
};

Student stu[100];        // 存放100名学生数据的成绩表

这样的自定义结构类型，C++天生不知道应该怎么比较大小，所以算法库中的排序函数不能直接对数组 stu[] 中的元素进行排序。我们需要让C++知道怎么对 Student 结构类型的变量进行相互比较，至少要会“小于”比较。这个其实很好办，我们可以利用C++结构体的两个特技，成员函数和运算符重载。听起来很高大上的样子，其实做起来并不难。

以前学习基本的C语言结构类型的时候我们说过，一个结构类型就是把多个不同数据类型的变量组合起来形成一个复杂数据类型，定义在结构类型里的各种变量就叫做这个结构的成员变量。stu_no, name, chn, math 就是 Student 结构的四个成员变量。我们用 . 符号来访问一个具体的结构变量中的成员变量，比如 stu[0].name 就是结构变量 stu[0] 的成员变量 name；用 -> 符号来访问一个指针所指向的结构变量里的成员变量，比如 stu->stu_no 就是 stu[0] 的成员变量 stu_no，(stu+10)->chn 就是学生 stu[10] 的语文成绩。

C++不但完全继承了C语言的结构语法，而且为其增加了一个新技能，C++结构类型不仅可以有自己的成员变量用来保存数据，而且可以为它定义成员函数用来定义操作。比如我们的学生结构中，目前只存放了语文成绩和数学成绩，但是我们有时候想看总分或者平均分怎么办？在以往传统的C语言里，我们只能另外定义两个函数用来计算总分和平均分，像下面这样：

// 在传统C语言里，为了减少传递参数的开销，向函数传递结构建议使用指针方式
// 对于不改变成员变量值的函数，用常数型指针
int total_score(const Student *s) { return s->chn + s->math; }
double avg_score(const Student *s) { return (s->chn + s->math) / 2.0; }

// 调用方式如下：
int t = total_score(&stu[0]);        // 计算学生 stu[0] 的总分
double a = avg_score(stu + 5);       // 计算学生 stu[5] 的平均分

这种方式会让程序变得比较凌乱，所以C++允许把这样的针对某一种结构类型的特定操作函数变成结构的成员函数。成员函数在结构内部声明，在结构代码以外的地方写函数定义，函数定义的头部要加上“结构名::”形式的前缀。对于一些函数体特别短的成员函数也可以直接定义在结构代码内部。比如上面的两个函数现在可以这样写：

struct Student {
        int stu_no;      // 学号
        string name;     // 姓名
        int chn;         // 语文成绩
        int math;        // 数学成绩

        int total() const;  // 声明计算总分的成员函数，后缀const表示此函数不改变成员变量的值
        double avg() const { return (chn + math) / 2.0; } // 直接定义计算平均分的成员函数
};

int Student::total() const
{
        return this->chn + this->math; // this 是一个C++预定义的特殊指针，指向调用者“自己”
}

在上面的示例中分别展示了“内部声明外部定义”和“内部直接定义”两种成员函数的代码书写方法，二者从功能上来说是完全一样的。但是直接定义在结构内部的成员函数会被自动实现为内联函数，因此它们的运行速度会加快，但是不支持递归调用，而且代码要尽量简短，一般不要超过三行，最好是顺序结构。另外，内部声明外部定义的成员函数也可以设定为内联函数，只要在函数定义处给函数头加上 inline 修饰即可。

成员函数的调用方法和访问成员变量的方法是一致的，都是用 . 或者 -> 这两个符号，例如：

int t = stu[0].total();      // 计算学生 stu[0] 的总分
double a = (stu+10)->avg();  // 计算学生 stu[10] 的平均分

注意，成员函数只能凭借一个具体的结构类型变量来发起调用，不能凭借结构类型名称来调用，例如 Student.total() 这样的调用是错误的。在一次成员函数调用中，这个具体的结构变量就叫做调用者。

从上面的示例中我们可以看到，成员函数不需要用参数来指定调用者。调用成员函数时默认就是对调用者进行操作的，我们可以简单地认为是对“自己”进行操作。在成员函数内部，不需要任何特殊的指定，可以自由使用“自己”的所有成员变量，直接使用成员变量的名字即可。就如 Student::avg() 函数所示，直接使用成员变量名 chn 和 math。调用 stu[0].avg() 时，函数中的 chn 和 math 就是 stu[0] 的成员变量 stu[0].chn 和 stu[0].math。

但是在 Student::total() 的函数体内，我们看到了一个奇怪的 this 指针。this 是一个预定义的特殊指针，专用于结构的成员函数，它永远指向调用者，也就是“自己”。例如调用 stu[99].total() 时，this 指针就指向 stu[99]，调用 x.total() 时它自然就指向 x。其实写不写 this-> 都是完全一样的，Student::total() 函数完全可以这样写：

int Student::total() const { return chn + math; }

一点问题都没有！写不写 this-> 大多数时候只是为了让程序的代码易读性更好一点。另外，它最重要的一个目的是让成员函数可以使用和成员变量同名的形参。例如我们要增加一个改写语文成绩的成员函数：

struct Student {
        // 与上面示例中相同的部分略过
        void set_chn(int chn)
        {
                this->chn = chn;
        }
};

这里就必须使用 this-> 来区分是“自己”的成员变量 chn 呢还是函数的参数 chn 了。对于一些复杂的结构编程，这是很重要的。另外还可以看到一个不同点，这次的成员函数 Student::set_chn() 是要改变“自己”的成员变量的，所以函数名不能加 const 后缀。

好，知道怎么为结构类型添加成员函数之后，我们就要来学习怎么让结构类型学会大小比较。这就需要为它定义一种特殊的成员函数，叫做运算符重载函数。说得简单点，所谓运算符重载，就是为结构类型定义一些它原本不支持的运算，让它可以像内置数据类型一样使用这些的运算符。比如我们已经见过的C++ string，它就重载了加法 + 运算符，使得两个C++ string可以像做加法一样进行字符串连接运算：

std::string a = "hello", b = "world";
cout << a + " " + b << endl;  // 输出 "hello world"

所以现在我们要做的就是给 Student 结构重载 < 运算符，这就是C++的运算符重载。运算符重载本质上也是一种成员函数，但是它有特殊的格式规定。不同的运算符，其函数名、返回类型、参数表都有自己的规定，这些是要记住的。说实话一般记不住所有运算符重载的格式，临时查资料总是需要的。但是几个常用的必须记住，包括六种比较运算、赋值运算、加减乘除余五种算术运算。好在每一类运算符的格式规定都是相同的，有一定规律可循，光上面这几种要记住也不难。下面我们就来看怎么给 Student 结构重载小于运算符，实现按学号的大小进行比较：

struct Student {
        // 与上面示例中相同的部分略过
        bool operator<(const Student &s) const;
};

bool Student::operator<(const Student &s) const { return stu_no < s.stu_no; }

首先，所有的运算符重载成员函数的函数名都是 operator 后跟上运算符，比如这里的 operator< 就表示这是一个重载 < 运算符的成员函数。

第二，所有六种比较运算符的返回类型都是逻辑型 bool。

第三，所有六种比较运算符，以及赋值 =、算术运算 +-*/%，都是所谓的二元运算符，即在运算符左右两边各有一个变量。这样的二元运算符的重载函数，都只有一个参数，就是运算符右边的那个变量。例如运算 a < b 时，形参 s 得到的实参就是运算符右边的 b，而运算符左边的 a 就是调用者“自己”。

第四，函数的参数，如果是结构类型，那么参数要使用传引用的方式，例如这里的 &s，这是C++对C语言使用指针传递结构变量的改进；如果是内置数据类型，那就直接传值就好。

第五，如果这个运算不会改变右操作数，也就是参数的值，那么就给参数加上 const 修饰，这很重要！非常重要！如果这个运算不会改变左操作数，也就是调用者“自己”的值，那就给函数自身加上 const 后缀用以确保安全。

最后，就是比较大小的过程，这就根据实际需要来写了。因为我们这里重载的小于运算是要根据学号来比较大小，所以我们直接返回左右两个操作数的 stu_no 成员变量的大小比较结果就可以了，谁的学号小就认为谁更小。

有了这样一个实现小于运算重载的成员函数之后，我们就说 Student 结构已经重载了 < 运算符，可以进行 stu[0] < stu[1] 这样的比较了。而C++算法库的所有排序函数都只利用小于比较来进行排序，因此现在就可以调用排序函数来对 Student 结构变量的容器（包括数组）进行排序了。

这里隐藏了一个小小的技巧，因为C++的排序函数都是基于小于比较来进行的，默认的排序是从小到大排。如果我们需要排逆序，即从大到小来排怎么办？很好办，我们只要认为学号越大，元素值越小就可以了，因此我们只要这样来写小于运算重载：

bool Student::operator<(const Student &s) const { return stu_no > s.stu_no; }

那么为什么算法库排序函数只需要数据类型支持小于运算就可以排序了呢？因为有了小于运算，其他五种比较运算都可以通过小于比较来实现。

  1. 大于：大于运算就是比较双方互换位置之后的小于运算，a > b 就是 b < a；

  2. 大于等于：大于等于就是不小于，所以 a >= b 就是 !(a < b)；

  3. 小于等于：小于等于就是不大于，所以 a <= b 就是 b >= a，也就是 !(b < a)；

  4. 等于：等于就是既不大于也不小于，所以 a == b 就是 !(a < b || b < a)；

  5. 不等于：不等于就是不“等于”，也就是要么大于要么小于，所以 a != b 就是 a < b || b < a。

但是请注意，这只是说明排序库函数内部会自动这样实现其他五种比较，并不是说我们只需要重载一个 < 运算符就可以直接使用其他五种比较运算符了。如果我们需要在自己的程序里进行 a >= b 这样的判断，那还是需要我们再重载掉 >= 运算符的。当然了，有了上面的说明，其他几种运算符的重载就变得很简单了对不对？例如我们可以这样重载 Student 结构的 >= 运算符：

struct Student {
        // 与上面示例中相同的部分略过
        bool operator>=(const Student &s) const { return !(*this < s); }
};

this 指针永远指向自己，所以 *this 当然就是自己了，直接调用已经重载好的 < 运算就完事了。但是，我们发现用小于来构造等于和不等于是很不划算的，尤其是如果小于比较本身就比较复杂的话，这样来实现等于和不等于太不划算了。一般来说等于比较只要依次比较每一个成员变量的值就可以了，发现一处不同就返回 false，全部相同返回 true，而不等于比较可以直接用等于的结果取反来实现。这往往比两次调用小于要划算，所以在实际编程中还是要根据实际需要判断一下，选择一种速度更快的实现方式，有可能的话还是自己单独实现一下等于和不等于运算。

练习

请把 Student 的六种比较运算全部重载完整，其中等于和不等于两个运算不利用小于来实现。

3.5.6.4. C++排序函数的使用

单纯的排序函数

C++算法库提供的排序类函数一共有五个，都非常简单易用。首先介绍最常用的不稳定排序 sort() 和稳定排序 stable_sort()。它们是算法编程中使用最为广泛的，必须熟练掌握它们的用法（但是放心，它们的用法实在是太简单了）。

以对数组排序为例（对STL容器排序也是一样的，无非是把指针改成迭代器而已），我们只要向函数提供头尾两个指针，指出数组中要排序部分的范围就可以了。假如我们要对上面示例中的学生数组 stu[] 按学号进行不稳定排序：

sort(stu, stu + 100);      // 对 stu 数组中所有100个元素进行排序
sort(stu, stu + 37);       // 对 stu 数组中前37个元素进行排序
sort(stu + 50, stu + 100); // 对 stu 数组中后50个元素进行排序

int n;
scanf("%d", &n);           // 输入一个数量 n
sort(stu, stu + n);        // 对 stu 数组中前 n 个元素进行排序
sort(stu + 100 - n, stu + 100); // 对 stu 数组中后 n 个元素进行排序

if (n > 50) n = 50;        // 把 n 限制为不超过50
Student *left = stu + n, *right = stu + 100 - n;  // 定义范围的左右端点指针
sort(left, right);         // 对从 stu[n]（含）到 stu[100-n]（不含）范围内的一段排序

简直太简单了对不对？稳定排序函数 stable_sort() 的用法和 sort() 一模一样，只是函数名不同而已。另外，稳定排序的速度是略微慢一点的，但比手写的归并或者堆排还是要快。

部分排序函数

排序类函数的第二种是部分排序，有两个函数，partial_sort() 和 partial_sort_copy()，二者的区别是前者在容器内原地完成部分排序，原来容器里元素的顺序会发生改变，后者则不改变原容器，它复制原容器内的元素到外部另一个容器里进行部分排序并把结果放置在那里。

partial_sort() 函数需要三个迭代器参数，依次为 first, middel, last，它们应该是同一个容器的迭代器。函数将该容器中范围 [first, last) 内的元素进行部分排序，排完后在范围 [first, middel) 内是前 middle - first 个最小的元素，而且已经有序排放，后面的范围 [middle, last) 内是剩余的元素，它们的顺序是不确定的，也不保证能保持原来的相对顺序。

例如，我们可以这样对 stu[] 数组进行部分排序：

// 将整个数组中学号最小的前10名学生按顺序排在 stu[0] 开始的10个元素中
partial_sort(stu, stu + 10, stu + 100);
// 将从 stu[10] 到 stu[49] 的40名学生中学号最小的10名学生部分排序在从 stu[10] 开始的10个元素中
partial_sort(stu + 10, stu + 20, stu + 50);

使用部分排序要注意，如果范围 [first, last) 不是整个容器，那么参与部分排序的元素就仅限于此范围之内，容器中不在这个范围内的元素不会参与排序，最后得到的部分结果也是从 first 指向的位置开始存放，不会从容器开头开始存放。

partial_sort_copy() 函数依次需要提供 first, last, result_first, result_last 四个迭代器参数。它们构成两个范围。函数对范围 [first, last) 中的元素进行部分排序，部分排序的长度为 result_last - result_first。排序结果将被有序地复制到范围 [result_first, result_last) 中，而范围 [first, last) 中的元素不会发生任何变化。这两个范围应该是属于两个不同的容器的。例如：

// 将整个数组中学号最小的前10名学生按顺序复制到 topten[] 数组中，从头开始存放
Student topten[10];
partial_sort_copy(stu, stu + 100, topten, topten + 10);

k位数算法

nth_element() 函数用于在一个指定的范围内寻找假如排完序之后应该位于某个特定位置的元素。它依次接收三个迭代器参数，分别为 first, nth, last，然后在范围 [first, last) 内的元素中寻找排完序之后应该处于 nth 所指向的位置的元素，并将其放在这个位置上，其余位置的元素将变得不确定，不能保证就在原来的位置上。

请仔细理解上面的描述，这个算法实质上是一个k位数算法，如果 first 指向容器的首元素，nth = first + n 就指向容器的第 n 个元素 first[n]，所以最终在那里放置的就是容器元素中的n+1位数，即第n+1小的那个元素。例如：

nth_element(stu, stu + 9, stu + 100); // 找到 stu 数组中学号第10小的学生并将其放在 stu[9]

使用这个算法函数最需要小心的是容器也好数组也好，C++里一切成串放置元素的东西，其元素位置都是从0号开始计数。因此位置 nth = first + n 里放的是第n+1小的元素，当 nth 等于 first 时就是找最小的那个元素。

这些排序相关的函数都还有另一个版本的用法，我们在下一节介绍各种复杂排序规则的时候再学习。