C3第九部分：随心所欲的排序

📖 温故知新

前置知识点

基本语法和概念：

数组的基本使用方法
函数的用法
用 sort 函数排序的基本内容

例1：复习算法库函数

sort

将两个索引位置间的数组元素从小到大排序

sort 来自英文单词 sort，在英文中是"排序"的含义。

sort(开始位置, 结束位置);

reverse

将两个索引位置间的数组元素翻转

reverse 来自英文单词 reverse，在英文中是"颠倒、反过来"的含义。

reverse(开始位置, 结束位置);

swap

用于交换两个相同类型（长度）结构中取值的函数

swap 来自于英文单词 swap，在英文中是"交换"的含义。

swap(第一个变量, 第二个变量)

swap(第一个数组元素, 第二个数组元素)

🎯 本讲目标

知识与能力

1. 理解算法库中的 sort 函数允许使用自定义比较函数来指定排序规则
2. 掌握定义自定义比较函数的方式
3. 掌握涉及多个条件的自定义比较函数定义方式，并能理解各比较条件被使用的顺序

自定义排序依据

sort 函数的第三个秘密参数——cmp！

例2：从大到小的排序

很好！再运行一下程序看看输出的结果，是不是最终输出的元素已经是从大到小顺序的了？

想一想，为什么 cmp 里符号改变后输出的结果完全反过来了。

总结：

对于任意两个元素，cmp 对左右元素比较的返回结果为假，则它们的顺序关系会改变；
否则，它们的顺序关系不变。

蒜头君查阅资料后发现，sort 函数也可以用于由字符元素构成数组的排序，排序时的大小按照各字符的 ASCII 确定。根据前面所学的 sort 函数的相关知识，阅读下面代码，选出一个正确的选项。

#include <iostream> #include <algorithm> using namespace std; bool cmp(char zuo, char you) { return zuo > you; } int main() { char s[10] = {'a','b','c','d','e'}; sort(s, s + 5, cmp); for (int i = 0; i < 5; i++) cout << s[i]; return 0; }

A. 输出结果是 abcde

B. 输出结果是 edcba

C. 如果改写 sort(s, s + 5, cmp) 为 sort(s, s + 5)，则输出结果是 edcba

D. 如果初始化时，顺序如下，结果会改变。{'a', 'd', 'b', 'c', 'e'}

✅ 正确答案：B
cmp 中 zuo > you 表示按 ASCII 码降序排列，所以 'a','b','c','d','e' 排序后输出为 edcba。A 是升序结果；C 去掉 cmp 后使用默认升序，结果应为 abcba 而非 edcba；D sort 函数排序结果与初始顺序无关。

例3：奇偶分段

运行一下程序，看看结果中奇数是不是都排到左侧、偶数都排到右侧了？

蒜头君分析了一下：

zuo % 2 > you % 2 只有在左值是偶数、右值是奇数的情况下才会为 false，对应最终排序结果中任取两个值，应该不会出现左值是偶数右值是奇数的情况。

根据前面所学 sort 函数的知识，阅读下面代码片段，选择正确的一个选项。

#include <iostream> #include <algorithm> using namespace std; bool cmp(int zuo, int you) { return zuo % 2 < you % 2; } int main() { int a[5] = {2,6,3,8,1}; sort(a, a + 5, cmp); for (int i = 0; i < 5; i++) cout << a[i] << " "; return 0; }

A. 该代码的执行结果为 3 1 2 6 8

B. 如果要使输出为先偶数后奇数，要将第 10 代码改为 for (int i = 4; i >= 0; i--) {

C. 如果要使输出为先奇数后偶数，要将第 5 行代码改写为 zuo % 2 > you % 2;

D. 如果要是输出结果为 8 6 3 2 1，要将第 5 行代码改写为 zuo < you;

✅ 正确答案：C
当前 cmp 中 zuo%2 < you%2 表示偶数(0)排在奇数(1)前面。若要改为奇数在前，只需将 < 改为 >，即 zuo%2 > you%2。A 当前代码偶数在前，结果应为偶数在前而非 3 1 2 6 8；B 修改输出循环不会改变排序结果；D zuo < you 是升序，结果为 1 2 3 6 8 而非 8 6 3 2 1。

练一练：区间降序

对于包含 n 个元素的一个数组，给定整数 x 和 y，请把数组中从位置 x-1 到 y 的连续数组元素从大到小排序后输出。

输入格式：第一行整数 n；第二行 n 个整数；第三行 x、y（1≤x,y≤n）
输出格式：输出排序后数组所有元素（空格隔开）
样例输入：
6
9 6 1 13 7 4
1 4
样例输出：
13 9 6 1 7 4
解释：x=1,y=4，排序下标0到3的元素[9,6,1,13]降序为[13,9,6,1]

复杂条件的排序依据

多个排序条件怎么写？先看第一关键字，相同再看第二关键字！

如果将下面的 cmp 函数作为 sort 被调用时的第三个参数，请你选出会导致其返回为 true 的一对数组中的元素取值

bool cmp(int zuo, int you) { if (zuo % 2 != you % 2) { return zuo % 2 < you % 2; } return zuo < you; }

A. zuo 取值 5，you 取值 3

B. zuo 取值 3，you 取值 4

C. zuo 取值 4，you 取值 5

✅ 正确答案：C
C：zuo=4 是偶数(0)，you=5 是奇数(1)，奇偶不同，进入 if 判断 0 < 1 为 true。A：5 和 3 都是奇数，同奇偶进入 return 5<3 为 false；B：3 是奇数(1)，4 是偶数(0)，奇偶不同，1<0 为 false。

练一练：复杂排序的实现

将 n 个整数数组元素排成奇数在前偶数在后形式，并要求每部分内部升序。

输入格式：输入一个 n 和 n 个整数，表示待排序数组元素个数和所有元素。
输出格式：一行整数，表示排序后的数组内的所有元素。
提示：
if (zuo%2 != you%2) return zuo%2 > you%2; // 奇数(1)在前
return zuo < you; // 同组从小到大

例5：排序依据配对

根据前面学过的内容，将描述和对应的比较函数配对。

① 将数组分为左偶右奇两部分，前侧部分从大到小排序，后侧部分从小到大排序

if(x%2!=y%2) return x%2<y%2;
if(x%2==0) return x>y;
return x<y;

② 将数组分为左偶右奇两部分，每部分从小到大排序

if(x%2!=y%2) return x%2<y%2;
return x<y;

③ 将非零数组分为左负右正两部分，左侧从大到小，右侧从小到大

if(x*y<0) return x<0;
if(x<0) return x>y;
return x<y;

练一练：偶奇排序

所谓偶奇排序，就是将数组分为前偶后奇两部分，每部分从小到大排序。

例如，对于数组 2, 5, 3, 4, 1, 9, 10, 7, 8, 6，排序后的数组为 2 4 6 8 10 1 3 5 7 9。

输入格式：输入 2 行。第 1 行 n（1≤n≤1000），第 2 行 n 个数字。
输出格式：输出 1 行，为排序后的数字。
样例输入：
10
9 6 4 3 5 1 7 10 8 2
样例输出：
2 4 6 8 10 1 3 5 7 9
提示：偶数%2=0，奇数%2=1。zuo%2 < you%2 让偶数(0)在前。

📝 重点笔记

1. 自定义比较函数的函数名作为 sort 函数调用时的第三个参数，是提供给 sort 函数用于排序的依据

2. 任意两个数组中的元素，会以参数形式被自定义比较函数用于比较，返回 false 时，元素顺序会被改变

3. 涉及多个条件的时候，需要先判断靠前的条件是否不相等，按靠前的条件先决定返回值；再按照靠后的条件判断是否不相等，再按靠后的条件决定返回值

本讲巩固：排序与交换函数记忆

sort

将两个索引位置间的数组元素从小到大排序

sort 来自英文单词 sort，在英文中是"排序"的含义。

sort(开始位置, 结束位置);

swap

用于交换两个相同类型（长度）结构中取值的函数

swap 来自于英文单词 swap，在英文中是"交换"的含义。

swap(第一个变量, 第二个变量)

swap(第一个数组元素, 第二个数组元素)

algorithm

算法库的头文件名（不含 <>）

algorithm 是英文单词，表示"算法"。

加上第三个参数 cmp 即可自定义排序规则！

本讲巩固：正负分段

把 n 个整数数组元素排成负数在前，正数在后的序列。

输入格式：输入一个 n 和 n 个整数，表示待排序数组的长度和所有元素。
输出格式：一行整数，表示排序后的数组所有元素。
提示：两数一正一负时，zuo*y < 0。return zuo < 0 让负数在前。

本讲巩固：排序结果

根据前面所学的 sort 函数知识，阅读下面代码片段，将在 ① 处填入的代码与输出的结果进行配对。

#include <iostream> #include <algorithm> using namespace std; bool cmp1(double zuo, double you) { return zuo < you; } bool cmp2(double zuo, double you) { return zuo > you; } int main() { double a[10] = { 3.6, 5.0, -1.8, 2.7, -4.5, 4.8, 7.5, -3.0, 2.9, -3.7 }; /* ① */ for (int i = 0; i < 5; i++) cout << a[i] << " "; return 0; }

① 位置代码：
sort(a, a + 10, cmp1);

输出：-4.5 -3.7 -3.0 -1.8 2.7
（全数组升序，取前5个）

① 位置代码：
sort(a + 5, a + 9, cmp1);

输出：3.6 5.0 -1.8 2.7 -4.5
（仅排下标5~8，前5个不变）

① 位置代码：
sort(a + 3, a + 7, cmp2);

输出：3.6 5.0 -1.8 7.5 4.8
（下标3~6降序：7.5,4.8,2.7,-4.5）

综合巩固：买水果

蒜头君在水果店选水果，想找最甜的两种水果买回去吃。目前的程序已经用 n 存下了总水果数，并为你将水果甜度都读入到了 shuiguo 数组中，请你继续写程序，找出甜度最高的两个水果。

输入格式：输入包含多行，每行输入一个浮点数表示该水果的酸甜度。输入 0 时表示输入结束。(2≤水果数≤10000)
输出格式：输出店内最甜的两种水果对应的甜度（用空格隔开）。
样例输入：
4.27
-2.98
3.23
-0.23
3.24
0
样例输出：
4.27 3.24