第 23 课：选择排序

排序在生活中有着广泛的应用，比如学校会对学生的成绩进行排名，购物软件会按销量或价格等对商品进行排序，跑步比赛时会按时间对运动员进行排序。排序帮助我们在各种场景下对事物进行合理的安排，以提高效率。

在信息学奥赛中，许多基础问题都涉及排序知识，比如给定一组数据，对这组数据进行排序，还有可能让你找出排名第几的元素，等等。

如何将一组数据从小到大或从大到小进行排序呢？我们跟着氪町博士一起来学习一下本章的四个排序算法吧！

23.1 选择排序的概念及步骤

选择排序（selection sort）是一种简单、直观的比较排序算法，我们先来了解它的概念。

概念

选择排序的基本思想是：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

步骤

1. 初始状态：无序区为 a[1,…,n]，有序区为空。

2. 第 i 轮排序（i = 1,2,3,…,n - 1）开始时，当前有序区和无序区分别为 a[1,…,i - 1] 和 a[i,…,n]。该轮排序从当前无序区中选出最小的元素 a[k]，将它与无序区的第 1 个元素（即下标为 i 的元素）交换，使 a[1,…,i] 和 a[i + 1,…,n] 分别变为元素个数增加 1 个的新有序区和元素个数减少 1 个的新无序区。

3. n - 1 轮结束，数组就变有序了。

23.2 演示及实现

演示

假设有一个无序数组 arr = [5, 3, 8, 6, 2]，使用选择排序对其进行升序排列的过程如下。

1. 第一轮排序。在整个数组 [5, 3, 8, 6, 2] 中找到最小的元素 2，将其与数组的第一个元素 5 交换位置，得到数组 [2, 3, 8, 6, 5]。此时，已排序部分为 [2]，未排序部分为 [3, 8, 6, 5]。

2. 第二轮排序。在未排序部分 [3, 8, 6, 5] 中找到最小的元素 3，由于 3 已经在未排序部分的开头，无须交换。已排序部分变为 [2, 3]，未排序部分为 [8, 6, 5]。

3. 第三轮排序。在未排序部分 [8, 6, 5] 中找到最小的元素 5，将其与未排序部分的第一个元素 8 交换位置，得到数组 [2, 3, 5, 6, 8]。已排序部分变为 [2, 3, 5]，未排序部分为 [6, 8]。

4. 第四轮排序。在未排序部分 [6, 8] 中找到最小的元素 6，由于 6 已经在未排序部分的开头，无须交换。已排序部分变为 [2, 3, 5, 6]，未排序部分为 [8]。

5. 第五轮排序。此时未排序部分只有一个元素 8，整个数组已经有序，排序完成，最终得到有序数组 [2, 3, 5, 6, 8]。

代码实现

#include <iostream>
using namespace std;
int main()
{
    int arr[] = {5, 3, 8, 6, 2};
    int n = 5;
    // 选择排序的核心代码
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex]) // 找无序区的最小值
            {
                minIndex = j;
            }
        }
        // 交换元素
        if (minIndex != i)
        {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    // 输出排序后的数组
    cout << "排序后的数组： ";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

运行结果：

排序后的数组： 2 3 5 6 8

23.3 实例讲解

例 1：成绩排名

期末考试结束以后，语文老师想把班级中 n 位学生的成绩按照从高到低的顺序进行排列，并公布排名，请写程序帮助老师完成这个步骤。（一个班最多有 50 人。）

【输入格式】输入两行。第 1 行输入一个正整数 n，表示班级总人数（2 ≤ n ≤ 50）。

第 2 行共输入 n 个整数，表示每个人的分数。

【输出格式】输出一行，用空格隔开的 n 个数表示按照从高到低顺序排列的分数。

【输入样例】

5
95 92 94 90 97

【输出样例】

97 95 94 92 90

解析

前面的代码实现是给定一个无序数组，把这个数组从小到大排序，而本题要求从大到小排序，只需将每次找最小值改为找最大值即可，这样就可以按照从大到小排序。

参考代码

#include <iostream>
using namespace std;
int arr[55];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    // 选择排序的核心代码
    for (int i = 0; i < n - 1; i++)
    {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] > arr[maxIndex]) // 找无序区的最大值
            {
                maxIndex = j;
            }
        }
        // 交换元素
        if (maxIndex != i)
        {
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

例 2：同时找最大值和最小值

我们刚刚学习了从一组数中找出最大值或者最小值的方法，如果一道题目既要求找出最大值，又要求找出最小值，该怎么办呢？

其实，遇到这类题目时，只需对数据进行排序即可。无论是将数据按照从小到大排序，还是按照从大到小排序，一旦排序完成，我们所需要的最大值和最小值就会出现在数组的两端。

具体来说，若按从小到大排序，最小值就在数组的第一个位置，最大值则在最后一个位置；若按从大到小排序，则最大值在数组的第一个位置，最小值在最后一个位置。通过排序，我们可以轻松地获取这两个关键元素，从而解决问题。

蛙蛙已经独立完成这个程序了，你可以将最大值和最小值同时输出吗？

参考代码

#include <iostream>
using namespace std;
int arr[55];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    // 选择排序的核心代码，从大到小排序
    for (int i = 0; i < n - 1; i++)
    {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] > arr[maxIndex]) // 找无序区的最大值
            {
                maxIndex = j;
            }
        }
        // 交换元素
        if (maxIndex != i)
        {
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }
    cout << arr[0] << " " << arr[n - 1]; // 分别输出了最大值和最小值
    return 0;
}