资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

信息学奥赛C++ 排序算法详解以及实战经典例题

创作时间:

作者:

@小白创作中心

信息学奥赛C++ 排序算法详解以及实战经典例题

引用

CSDN

https://m.blog.csdn.net/qq_52337463/article/details/144983069

在信息学奥赛的赛场上，C++语言凭借其强大的功能和高效的性能，成为了选手们手中最得力的武器。而在众多的C++知识点中，排序算法无疑是一块基石，它的重要性不言而喻。无论是处理海量的数据，还是为后续的复杂算法搭建基础，排序算法都起着关键的支撑作用。接下来，就让我们一同走进C++排序算法的奇妙世界，揭开它们神秘的面纱。

一、排序算法基础：基石之稳

排序算法，作为数据处理的基础操作，其重要性不言而喻。在信息学奥赛的舞台上，它更是扮演着举足轻重的角色。想象一下，面对海量的数据，若没有高效的排序算法，我们将如同在黑暗中摸索，难以快速找到所需的信息。

从本质上讲，排序算法是将一组数据按照特定规则进行排列的方法，使得数据呈现出有序的状态。这看似简单的操作，实则蕴含着深奥的智慧。无论是在搜索算法中，为了快速定位目标元素，还是在动态规划等复杂算法里，作为预处理步骤以优化后续计算，排序算法都犹如一位幕后英雄，默默支撑着整个程序的高效运行。

在信息学奥赛的题目中，排序常常是解题的关键第一步。例如，在处理一些与数据统计、最值求解相关的问题时，先对数据进行排序，能够让问题的结构更加清晰，进而轻松找到突破口。可以说，熟练掌握排序算法，就等于握住了开启信息学奥赛胜利之门的一把重要钥匙。

二、C++排序算法详解：智慧之光

（一）冒泡排序：简单的交换艺术

冒泡排序，作为入门级的排序算法，其原理简洁而直观。它就像一个个气泡在水中上浮，每次比较相邻的两个元素，如果顺序不对，就将它们交换位置。如此反复，每一轮比较都会让未排序部分的最大（或最小）元素像气泡一样“浮”到末尾。

假设我们有一个数组 [5, 3, 4, 6, 1]，第一轮比较，先比较 5 和 3，发现 5 大于 3，交换位置得到 [3, 5, 4, 6, 1]；接着比较 5 和 4，交换得 [3, 4, 5, 6, 1]；再比较 5 和 6，保持不变；最后比较 6 和 1，交换得 [3, 4, 5, 1, 6]，第一轮结束，最大元素 6 已在末尾。第二轮从开头开始重复，直到整个数组有序。

在时间复杂度方面，由于它需要进行多次两两比较，对于长度为 n 的数组，最坏情况要比较次，时间复杂度为 O (n²)。而空间复杂度上，它只需在原数组上进行交换操作，额外空间开销很小，空间复杂度为 O (1)。虽然冒泡排序在处理大规模数据时效率不高，但因其简单易懂，在小规模数据或对稳定性有要求（相同元素相对顺序不变）的场景下，仍有其用武之地。

（二）选择排序：精准的最值定位

选择排序的思路别具一格，它每一轮都从未排序的元素中精准地找出最小值（或最大值），然后将其与未排序部分的首位元素交换位置，逐步扩大已排序区域。

以数组 [4, 2, 7, 1, 9] 为例，第一轮先假定 4 为最小值，遍历后面元素，发现 1 更小，记录 1 的位置，遍历完后将 1 与 4 交换，得到 [1, 2, 7, 4, 9]；第二轮在剩余 [2, 7, 4, 9] 中重复，找到 2 为最小，由于 2 已在首位，无需交换；接着第三轮找到 4 与 7 交换，以此类推，直到数组有序。

选择排序的时间复杂度同样为 O (n²)，因为无论数据初始状态如何，都需进行次比较。不过，它的优势在于移动元素的次数较少，在一些对数据移动开销敏感的场景下有一定优势，且代码实现简单直观，易于理解。

（三）插入排序：有序序列的巧妙拓展

插入排序宛如我们整理扑克牌时的操作，将新抽到的牌插入已整理好的手牌中的合适位置。算法从第二个元素开始，把当前元素与前面已排序的元素逐一比较，若当前元素小于前面的元素，则将前面的元素后移一位，为当前元素腾出位置，直到找到合适位置插入。

比如有数组 [3, 1, 4, 2, 5]，初始认为 3 已排序，处理 1 时，因 1 小于 3，将 3 后移一位，把 1 插入到最前面，变为 [1, 3, 4, 2, 5]；接着处理 4，4 大于 3，位置不变；处理 2 时，2 小于 4，将 4 后移，再与 3 比较，3 后移，把 2 插入合适位置得 [1, 2, 3, 4, 5]。

插入排序的时间复杂度在最好情况下，即数组已经有序时，只需进行 n - 1 次比较，时间复杂度为 O (n)；而平均和最坏情况仍为 O (n²)。空间复杂度为 O (1)，是一种原地排序算法。它对于部分有序的数据效率颇高，在实际应用中，当数据规模较小或数据接近有序时，插入排序能展现出出色的性能。

（四）归并排序：分治的高效典范

归并排序是分治思想的卓越体现，它将一个大问题巧妙地分解为多个小问题，各个击破后再合并。具体而言，先把数组从中间一分为二，对左右两半分别递归地进行归并排序，直到子数组长度为 1（天然有序），然后将排好序的子数组合并成一个完整的有序数组。

假设要对数组 [8, 4, 5, 7, 1, 3, 6, 2] 排序，先分成 [8, 4, 5, 7] 和 [1, 3, 6, 2]，继续细分，直到 [8]、[4] 等单个元素。之后开始合并，比较 [8] 和 [4]，合并为 [4, 8]，同理合并其他子数组，最终得到有序数组。

归并排序的时间复杂度稳定在 O (nlogn)，这得益于其均匀的分治策略，每层合并操作的时间复杂度为 O (n)，共 logn 层。但它的空间复杂度为 O (n)，因为合并过程需要借助额外的临时数组来存储子数组元素。尽管有空间开销，可在处理大规模数据时，其高效稳定的特性使其成为不二之选。

（五）快速排序：敏捷的分区能手

快速排序恰似一位敏捷的舞者，在数据的舞台上轻盈穿梭。它先选取一个基准元素，通常是数组的首元素，然后通过双指针法，从数组两端开始“探测”，将数组分为两部分，左边部分元素都小于等于基准，右边部分元素都大于等于基准，基准元素最终处于正确的排序位置。接着对左右两部分递归地执行同样操作。

以数组 [6, 1, 2, 7, 9, 3, 4, 5] 为例，选 6 为基准，从右往左找小于 6 的数 5，从左往右找大于 6 的数 7，交换它们，继续操作，最终将数组分为 [1, 2, 5, 3, 4] 和 [7, 9]（6 已在正确位置），再分别对两部分递归排序。

快速排序平均时间复杂度为 O (nlogn)，在实践中表现卓越，是许多编程语言内置排序函数的核心算法。然而，在最坏情况下，如数组已经有序或逆序时，时间复杂度会退化为 O (n²)。空间复杂度方面，由于递归需要栈空间，平均为 O (logn)。它凭借出色的平均性能，成为应对大规模无序数据的利器。

三、经典奥赛题目实战：利剑出鞘

（一）题目 1：车厢重组

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 180 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

这道题的本质是经典的冒泡排序改编，只需要在冒泡升序交换位置的时候加一个元素计数即可。我们来看具体的代码实现：

#include <iostream>
using namespace std;
int main() {
    int n, t, sum = 0;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j + 1] < a[j]) {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                sum++;  // 每交换一次，计数加一
            }
        }
    }
    cout << sum;
    return 0;
}

在这段代码中，我们使用了两层嵌套的循环来实现冒泡排序的逻辑。外层循环控制排序的轮数，内层循环用于每一轮中相邻元素的比较和交换。当发现相邻的后一个元素小于前一个元素时，就进行交换，并将记录交换次数的 sum 变量加一。最终，sum 的值就是将车厢排序所需的最少旋转次数。

（二）题目 2：求逆序对

给定一个序列 a1, a2, …, an，如果存在 i < j 并且 ai > aj，那么我们称之为逆序对，求逆序对的数目。

这道题可以用归并排序来巧妙地解决。解题思路与归并排序的思路相近，将整数数列一分为二，它的逆序数可能出现在三个位置：1. 两个数都出现在左边的区域；2. 两个数都出现在右边的区域；3. 一个数出现在左边的区域，另外一个数出现在右边的区域。函数 merge_sort（l, r）能求出 l 到 r 逆序数的个数，中间分割数为 mid，mid = l + r >> 1。两个数都出现在左边区域的逆序数为 merge_sort（l, mid）；两个数都出现在右边区域的逆序数为 merge_sort（mid + 1, r）；一个数出现在左边，另外一个数出现在右边的逆序数为 mid - i + 1。mid - i + 1 得来是因为当归并两个有序的数列时，会判断 q[i] 是否大于 q[j]，如果 q[i] <= q[j] 说明这两个数不构成逆序数，当 q[i] > q[j] 时，说明构成逆序数，并且 i 后面这 mid - i + 1 个数也与 j 构成逆序数，因为两个区域都是有序的数列。这样就将三部分相加即可。

以下是代码实现：

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long int LL;
int q[N], tmp[N];
LL merge_sort(int q[], int l, int r) {
    if (l >= r) return 0;
    int mid = l + r >> 1;
    // 两个数都在左边和都在右边的逆序数
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); 
    int i = l, j = mid + 1, k = 0;
    // 归并两个有序的数列
    while (i <= mid && j <= r) { 
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            // 一个数在左边区域，另一个数在右边区域的情况，i指向的数大于j指向的数，说明i后面mid - i个数都大于j指向的数，构成逆序数。
            res += mid - i + 1; 
            tmp[k++] = q[j++];
        }
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> q[i];
    cout << merge_sort(q, 0, n - 1);
    return 0;
}

在代码中，merge_sort 函数通过递归地对左右子数组进行排序和合并，并在合并过程中统计逆序对的数量。当左右子数组都有序时，通过比较指针 i 和 j 所指向的元素大小，若 q[i] > q[j]，则意味着找到了逆序对，并且可以根据当前指针位置快速计算出这一阶段新增的逆序对数量，将其累加到结果 res 中。

（三）题目 3：谁考了第 k 名

在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第 k 名的学生的学号和成绩。

这道题我们可以用排序算法先对学生信息按照成绩从高到低排序，然后直接取出第 k 名学生的信息即可。具体代码如下：

#include <bits/stdc++.h>
using namespace std;
struct Student {
    int id;         // id表示学号
    double point;   // point表示分数
} a[1001];
int n, k;
bool cmp(Student a, Student b) {
    return a.point > b.point;  // 按照成绩从高到低排序
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i].id >> a[i].point;
    sort(a, a + n, cmp);
    printf("%d %.2lf\n", a[k - 1].id, a[k - 1].point);
    return 0;
}

在上述代码中，首先定义了一个结构体 Student 来存储学生的学号和成绩信息。然后，通过自定义的比较函数 cmp，使得 sort 函数能够按照成绩从高到低对学生结构体数组进行排序。最后，直接输出排序后数组中第 k - 1 个元素（因为数组下标从 0 开始）所对应的学生学号和成绩，即为第 k 名学生的信息。