7.2 排序的应用

“排序不仅仅是把数字排列整齐，”我继续说道，”它还可以帮助我们解决很多实际问题，比如找出前几名的成绩，或者确定某个人的排名。”

7.2.1 寻找第K大数

题目描述： N 个小朋友在一起做游戏。每个小朋友在自己的硬纸板上写一个数，然后同时举起来。接着，小 y 老师提一个问题，看哪个小朋友先抢答出来。问题是，在这 N 个数中，第 K 大的是哪个数？

输入格式： 输入文件的第一行为 2 个整数，依次为 N 和 K ( K≤N≤1000 )；下面 N 行，每行为一个整数，表示从第 1 个小朋友到第 N 个朋友分别写的数（假设这些小朋友只知道 −32768∼32767 之间的数）。

输出格式： 输出文件只有一行，就一个数，为第 K 大的那个数。

样例输入：

4 3
1
2
2
4

样例输出：

2

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[1010], n, k;
    cin >> n >> k;
    
    for(int i = 1; i <= n; i++) 
        cin >> a[i];  // 输入所有数字
    
    // 使用冒泡排序按从大到小排序
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n-i; j++){
            if(a[j] < a[j+1])  // 注意：这里是小于号，实现降序排列
                swap(a[j], a[j+1]);  // 交换位置
        }
    }
    
    cout << a[k];  // 输出第k大的数
    return 0;
}

算法解析：

1. 读入所有数字和要查找的k值
2. 使用冒泡排序将数组按降序排列（从大到小）
3. 排序后，第k个位置就是第k大的数

7.2.2 优秀成绩的平均分

题目描述： 期中考试结束了，老师想知道这次语文考试前 5 名同学的平均分是多少，请你编程来帮老师计算一下！

输入格式： 第一行，一个整数 n ，代表本次考试的总人数（ 5≤n≤100 ）；第二行 n 个整数，代表 n 个人的语文成绩（这 n 个人的分数是无序的）。

输出格式： 语文成绩前 5 名同学的平均分（结果保留 1 位小数）。

样例输入：

10
98 98 100 96 99 90 91 87 80 100

样例输出：

99.0

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[110], n;
    cin >> n;
    
    for(int i = 1; i <= n; i++) 
        cin >> a[i];  // 输入所有成绩
    
    // 冒泡排序，按降序排列
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n-i; j++){
            if(a[j] < a[j+1])  // 从大到小排序
                swap(a[j], a[j+1]);
        }
    }
    
    int sum = 0;
    for(int i = 1; i <= 5; i++) 
        sum += a[i];  // 计算前5名的总分
    
    double average = sum / 5.0;  // 计算平均分
    printf("%.1lf", average);  // 保留1位小数输出
    return 0;
}

算法解析：

1. 将所有成绩按降序排列
2. 取前5名的成绩并求和
3. 计算平均分并保留1位小数输出