3.5.7. 复杂规则的排序技巧¶
在实际应用和复杂的算法问题中，排序往往是作为一种基本操作出现的，排序的元素经常是复杂的结构类型，而且排序的规则往往会比较复杂。本节将针对一些复杂排序规则介绍几种常用的排序技巧，我们将继续使用上一节中的学生成绩结构 Student。
3.5.7.1. 多种排序规则¶
有时候我们不得不对一种数据类型的元素进行多种不同规则的排序。比如对上节的 Student stu[100] 数组，我们现在不仅要按照学号进行排序，还要按照姓名的字典序、按照语文数学两门课的总成绩由高到低进行排序，总共需要进行三种类型的排序。那么像上一节那样给 Student 结构重载一个 < 运算符就不够用了。
另外，对于 int, char 这样的基本数据类型，虽然它们天生支持比较运算，但是万一我们非要用一种特殊的方式来进行排序呢？比如我们要对整数排逆序，那么我们当然希望排序函数能够用大于比较来进行排序，这时候又该怎么办？
这时候就要用到算法库排序类函数的第二种用法，提供一个特定的比较函数。这第二种用法就是在上一节所介绍的第一种用法基础上，在参数表最后再新增一个参数，那是一个用于元素比较的函数。这里有一个新的知识点，在C++语言中，函数也是可以作为别的函数的参数的。对于有这样的参数要求的函数，我们在调用的时候可以把另一个函数的函数名作为参数传递给它，然后在它的函数体代码中就可以调用我们传给它的那个函数了。
注解
这种模式是面向对象程序设计的一种设计模式，通常叫做“代理模式”或者“委托模式”。意思是我不知道某件事情具体该怎么做，我只知道我必须要做这件事情，那么就请给我一个能做这件事情的函数，我委托它作为我的代理来完成这件事情。
算法库函数也并非只有排序类函数有提供元素比较函数的版本，许多其他类别的库函数，只要运行时需要进行元素比较的，都会同时提供使用 < 运算符和使用特定比较函数两个版本的，比如分区、二分查找。所有这些函数的第二种用法都是在第一种普通用法的基础上，在参数表末尾增加一个比较函数的参数。而需要提供的这个特定的比较函数都有一个统一的函数格式要求，即：接收两个要进行比较的元素作为参数，前一个为比较的左操作数，后一个为右操作数，返回类型为一个可以转换为逻辑型的类型，一般就用逻辑型作为返回类型，返回值为 true 表示左操作数小于右操作数，为 false 表示左操作数大于等于右操作数。如果元素不是基本数据类型那么通常我们要传引用以提高函数调用效率，由于比较过程一般都不允许破坏元素的值，所以非基本数据类型的参数一定要用 const 引用方式。
因此，我们可以定义下面这样的一个函数来作为比较函数：
bool comp(T a, T b); // 比较数据类型为 T 的两个变量 a 和 b 的大小，相当于运算 a < b
bool desc(int a, int b) // 这个比较函数可以用来对 int 型数据进行逆序排序
{
return a > b; // 假装自己是一个小于比较，实际干的是大于比较，明修栈道暗度陈仓
}
int a[100];
sort(a, a + 100, desc); // 利用上面这个比较函数 desc 对 int 型数组 a 进行逆序排序
所以现在我们就知道应该怎样实现学生成绩单的三种不同排序规则了。我们在上一节已经为 Student 结构重载了 < 运算符，直接用第一种方式调用排序函数就可以实现按学号排序。现在要为后两种排序规则定义各自特定的比较函数，然后用第二种方式调用排序函数来实现排序（当然了，不重载小于运算，所有的排序规则都用第二种方式来实现也是可以的）。
// Student 结构定义等重复的代码不再显示
bool comp_by_name(const Student &s1, const Student &s2) // 按学生姓名字典序进行比较
{
return s1.name < s2.name; // C++ string 类型本身已经重载了小于运算符实现字典序比较
}
bool comp_by_total(const Student &s1, const Student &s2) // 按学生语文数学总分进行比较
{
return s1.total() > s2.total(); // 分数要从高到低逆序排序，所以实际要进行大于比较
}
这里有三点要进行说明。第一，比较函数不是结构的成员函数，所以声明也好定义也好都要和普通的函数一样，不能写在结构的定义内部；第二，正因为不是成员函数，所以比较函数没有什么“自己”的概念，左右两个运算数都要作为参数传递给它，左前右后；第三，还是因为不是成员函数，所以不能在函数名后面加 const 后缀，成员函数的 const 后缀其实是用来修饰那个隐藏的“自己”的。
好，现在我们已经定义好了两个元素比较的特定规则，接下来就可以用第二种方式来进行特定规则的排序了，如下所示：
sort(stu, stu + 100, comp_by_name); // 对所有100个学生按姓名字典序排序
// 在所有100个学生中部分排序出总分前10名的学生并放置在数组最前10个位置
partial_sort(stu, stu + 10, stu + 100, comp_by_total);
前面说过，不仅是五个排序类函数，凡是所有提供了此类用法的算法库函数，用法都是一样的，所以我们就举例说明到此，其他函数就不再举例了。
3.5.7.2. 多关键字排序¶
更加复杂的规则是多关键字排序，这种情况就比较多，技巧也比较多。
先从简单的看起，例如我们现在要对学生成绩单进行这样的排序，首先按语文成绩由高到低排序，语文成绩相同的按照数学成绩由高到低排，数学成绩也一样的按学号从小到大排。这是比较简单的多关键字情况，语文关键字称作主关键字，数学成绩称作第二关键字，学号当然就叫第三关键字了。关键字可以有任意多个，只要他们相互不交叉复合就是简单的情况。这种简单情况的处理方法有许多种，下面一一介绍。
依次排序法
第一种方法可以叫做“依次排序法”。也就是进行多次单关键字排序，顺序是从最后一个关键字开始，倒着向前直到最后一轮进行按主关键字的排序，之后整个多关键字排序就完成了。
依次排序法需要使用稳定排序，代码如下所示：
// 按语文成绩比较，逆序
bool comp_by_chn(const Student &s1, const Student &s2) { return s1.chn > s2.chn; }
// 按数学成绩比较，逆序
bool comp_by_math(const Student &s1, const Student &s2) { return s1.math > s2.math; }
// 按学号比较已经通过重载小于运算符实现
// 下面进行依次排序
stable_sort(stu, stu + 100); // 先按第三关键字学号进行排序
stable_sort(stu, stu + 100, comp_by_math); // 然后按第二关键字数学成绩排序
stable_sort(stu, stu + 100, comp_by_chn); // 最后按主关键字语文成绩排序
这样就完成了所需要的多关键字比较。想得明白为什么吗？我们看一个简单的例子，假设有四个学生Alice、Bob、Carol、David，学号分别是1、2、3、4号，数学成绩分别是90、100、100、90，语文成绩分别是100、100、100、90。第一轮按照学号排序后，成为下面这样的顺序：
stu_no name chn math
1 Alice 100 90
2 Bob 100 100
3 Carol 100 100
4 David 90 90
5 Eric 90 100
第二轮按数学成绩排逆序后：
stu_no name chn math
2 Bob 100 100
3 Carol 100 100
5 Eric 90 100
1 Alice 100 90
4 David 90 90
由于采用稳定排序，所以第二轮排序不会破坏数学成绩相同的学生之间已有的相对顺序，即第一轮排序生成的学号顺序不会发生变化，数学成绩相同的学生仍然能保持学号小的在前。
接下来最后一轮按主关键字语文成绩排序，结果如下：
stu_no name chn math
2 Bob 100 100
3 Carol 100 100
1 Alice 100 90
5 Eric 90 100
4 David 90 90
可以看出，由于采用稳定排序，第三轮按语文成绩排序时，数学成绩100的Alice不会被放到原本在她前面的Carol前面去，这就继续保持了已经排好的数学成绩逆序和学号顺序。至此整个排序过程正确结束。
提示
有没有一点似曾相识的感觉？对了，前面讲过的基数排序，其实就是把整数各个数位上的数看成多个关键字，最高位为主关键字，个位为最后一个关键字的多关键字排序！
比较运算合并
上面这种多次排序法虽然管用，但是代码显得很笨拙，而且要多轮调用速度较慢的不稳定排序。哪怕实际问题可能并不需要排序的稳定性，也必须使用稳定排序。可见多次排序法并不是非常好，下面我们介绍的方法可以叫做“比较运算合并”法。
既然是多个关键字按照一定规则依次比较，我们何不直接提供一个满足整个排序规则的比较函数呢？或者如果问题没有其他排序规则，我们何不干脆把这种比较规则直接集成到小于运算符的重载函数里去呢？这就是比较运算合并的方法。
例如这里我们可以直接写这样一个比较函数：
bool new_comp(const Student &s1, const Student &s2)
{
if (s1.chn != s2.chn) return s1.chn > s2.chn; // 先看主关键字语文成绩
if (s1.math != s2.math) return s1.math > s2.math; // 语文一样的再看第二关键字数学成绩
return s1.stu_no < s2.stu_no; // 主关键字和第二关键字都一样的，直接比较学号
}
sort(stu, stu + 100, new_comp);
这样，用一次不稳定排序就能搞定了。除非三个关键字都一样，否则虽然用不稳定排序，结果还是和依次排序法一样的。而且事实上大多数问题的排序都并不需要稳定，所以这个方法显然比依次排序法更胜一筹。
要注意的是，采用依次排序法，要从最后的关键字先开始排，依次向前直到最后再排主关键字。采用比较运算合并的方法，则顺序颠倒过来，先比较主关键字，然后依次比较第二、第三、直到最后一个关键字。
另外，还有一种多关键字排序的场景是依次排序法难以胜任的，那就是多个关键字之间有交叉关联的复合关系。例如我们现在要这样对成绩单排序：先按语文数学两门课的总分进行由高到低排序，如果有学生总分相同，那么语文分数较高的排在前面，如果语文分数也一样则说明数学分数也一样，这时候按照学号排，学号小的在前。
现在，主关键字“总分”是由第二关键字和第三关键字相加复合而成的。这种情况下有时候可以用依次排序法，有时候不可以，往往很难一下子进行判断，在考场上遇到这样的情况可不是一件好事情。但是用比较运算合并的方法就一定可以轻松搞定的。
练习
请编写一个自定义的比较函数，实现 Student 对象之间的上述比较规则，并用上面的五个学生的数据进行排序测试。
3.5.7.3. 其他元素比较技巧¶
除了上面提到的几个复杂排序规则下的元素比较技巧外，还有一些常见的特殊场景，有一些特殊的元素比较技巧。
第一种，有时候虽然是多关键字比较，但是这些关键字可以合并。
在算法编程题里经常会遇到对一个整数对进行排序的情况，例如对一些平面格点坐标 \((x, y)\) 进行排序，其中 \(0\lt x,y \lt 10^4\)，要求先按横坐标 \(x\) 从小到大排序，横坐标相等的时候按纵坐标 \(y\) 的值进行排序。对于这样的整数对，通常的做法是定义一个结构来保存两个坐标值，然后排序的时候就要用到多关键字排序。这样代码写起来就比较麻烦，也影响排序速度。
遇到这种整数对排序的场景，两个整数都为正数、最大值不是太大、两个数的排序方向相同，我们可以把两个整数拼接成一个大整数，从而简化为普通的整数排序。例如我们刚才所说的平面格点坐标排序，我们可以用把横纵两个坐标值按照主关键字在前副关键字在后的方式拼接起来，因为它们都小于10000，所以我们可以这样拼：\(z = 10000 x + y\)，满足 \(0\lt z\lt 10^8\)，在 int 型的数值范围内。根据 \(z\) 的值可以还原出 \(x = z / 10000, y = z \bmod 10000\)。在读入数据的时候，我们就直接拼接并保存 \(z\) 的值到一个 int 型数组里，要使用坐标值的时候再还原出来即可。可以编写三个简单的内联函数：
inline int get_z(int x, int y) { return x * 10000 + y; }
inline int get_x(int z) { return z / 10000; }
inline int get_y(int z) { return z % 10000; }
这样就可以让程序变得易读易写，简洁清晰。排序也就变成了最为普通的整数排序。如果坐标值的最大值变大使得拼接出来的整数超过 int 范围，那么就拼接成 long long，如果大到 long long 也不够用那就不适合用这个方法了，为了这个去写高精度是不划算的，还是回到定义结构吧。
这种方法在数据取值范围许可的情况下当然也适用于更多个整数关键字的情形。事实上对于多个字符串关键字也是可行的，拼接字符串的时候做到每一个关键字占用固定的一块区域，不够长的右对齐左边填满空格，但是实际上遇到字符串多关键字我们不会用这种方法，因为字符串拼接拆分填充的工作开销太大，不划算。
第二种，有一些场景会用到分数比较大小，或者比例比较大小。
这时候怎么办？通分比分子？计算成 double 型进行小数比较？这些办法都不好，通分比大小很麻烦，要找最小公倍数还要做乘法，计算成小数会带来 double 型浮点数精度误差。这时候其实很简单，利用一点数学规律就好，当两个分数都非负的时候：
所以我们的比较函数或者小于运算重载函数里只要按照上面这个公式来比较交叉相乘的积就可以了。
最后再介绍一种，数值的逆序排序。
这里的数值可以是整数也可以是浮点小数，只要是基本数据类型的就可以。我们前面说过，可以提供一个特殊的比较函数来实现逆序排序。但是某些场景下我们也可以这么干，读进来的数保存成它们的相反数。这样直接用普通的方法排序就相当于进行了逆序排序。当我们要使用这些数据的时候，用它们的相反数就好了。
其实特殊场景下的特殊比较技巧还有很多，这些都是一些编程的小技巧，一些特殊情况下的方便法门。随着编程练习量的增加，编程经验逐渐积累，会慢慢积累出许多这样的小技巧来。