#创作计划#题单总览与讲解顺序建议

CRH380AM-0204

2026-07-22 23:15:19

发布于：江苏

24阅读

0回复

0点赞

三种基础排序专题
题单分为三组，建议按以下顺序学习，以符合思维递进过程：

第一组：冒泡排序 / 相邻交换
a30923 排序
a538 冒泡排队
a30610 【结构体】【排序】成绩排序
a30635 【结构体】【排序】年龄排序
第二组：选择排序 / 选中目标位置并交换
a29970 【PY】选择排序
第三组：插入排序 / 动态维护有序序列
a29733 【PY】插入排序
a49995 [CSP-J 2021] 插入排序

第一组：冒泡排序 / 相邻交换

a30923 排序
思路简介
本题目的不是让你输出排序后的数组，而是让你模拟冒泡排序的完整过程，并统计其核心代价——交换次数。冒泡排序通过不断交换相邻的逆序对来达到有序。每交换一次，就消除一个“逆序对”。因此，本题的答案就是数组中逆序对的总数，这也是冒泡排序时间复杂度为O(n²)的直接体现。

算法步骤拆解

1、读入数据：读取数组长度n和所有元素。
2、外层循环：控制排序的“趟数”，共进行 n-1 趟。每趟将当前未排序部分的最大值“冒泡”到最后。
3、内层循环：在每一趟中，从数组开头到未排序部分的末尾，依次比较相邻元素 a[j] 和 a[j+1]。
4、判断与交换：如果 a[j] > a[j+1]，则交换它们，并使交换计数器 ans 加1。
5、输出结果：所有趟数结束后，输出 ans。

带注释代码

#include<bits/stdc++.h>
using namespace std;
int a[100010], n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int ans = 0; // 用于记录交换次数
    // 外层循环：控制比较的趟数，共 n-1 趟
    for(int i = 1; i <= n - 1; i++){
        // 内层循环：在未排序部分 [1, n-i] 中进行相邻比较
        // 因为每趟结束后，末尾的 i 个元素已经排好
        for(int j = 1; j <= n - i; j++){
            // 如果左边元素大于右边元素，说明是逆序，需要交换
            if(a[j] > a[j + 1]){
                swap(a[j], a[j + 1]); // 交换相邻元素
                ans++; // 记录一次交换
            }
        }
    }
    // 冒泡排序的总交换次数，即为逆序对数量
    cout << ans;
    return 0;
}

a538 冒泡排队
思路简介
本题要求你可视化冒泡排序的每一步。它不关心最终结果，而是考察你是否理解“每一趟排序后，最大元素被确定在末尾”这一过程。你需要输出每一趟排序结束后的数组状态。

算法步骤拆解

1、读入数据：读取数组长度n和所有元素。
2、外层循环：控制排序的“趟数”，从第1趟到第n-1趟。
3、内层循环：在当前趟中，遍历未排序部分，进行相邻元素比较。
4、交换操作：若顺序错误则交换。
5、输出状态：这是本题核心。在每一趟内层循环完全结束后（即一个最大值已归位），立即遍历并输出整个数组的当前状态。
注意格式：输出时，元素之间用空格分隔，每趟结果占一行。

带注释代码

#include<bits/stdc++.h>
using namespace std;
int a[1010], n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    // 外层循环：控制趟数
    for(int i = 1; i <= n - 1; i++){
        // 内层循环：相邻比较并交换
        for(int j = 1; j <= n - i; j++){
            if(a[j] > a[j + 1]){
                swap(a[j], a[j + 1]);
            }
        }
        // ----- 关键步骤：输出第 i 趟结束后的数组 -----
        for(int k = 1; k <= n; k++){
            cout << a[k] << " ";
        }
        cout << endl; // 每趟输出换行
    }
    return 0;
}

a30610 【结构体】【排序】成绩排序
思路简介
本题将冒泡排序应用于结构体数组，并涉及多关键字排序。你需要先按成绩降序排列，成绩相同则按学号升序排列。排序的逻辑需要你自定义比较规则，但交换操作依然是冒泡排序的相邻交换。

算法步骤拆解

1、定义结构体：Student 包含 id（学号）和 score（成绩）。
2、定义比较规则：编写一个cpp bool cmp(Student a, Student b) 函数。当 a 排在 b 前面时返回 true。
3、如果成绩不同，成绩高的（a.score > b.score）排在前面。
4、如果成绩相同，学号小的（a.id < b.id）排在前面。
5、冒泡排序主体：双重循环结构与之前相同，但判断条件不再是简单的 a[j] > a[j+1]，而是调用 !cmp(a[j], a[j+1])。意思是“如果a[j] 不满足排在 a[j+1] 前面的条件，则交换它们”。
6、输出结果：按排序后的顺序输出所有学生的信息。

带注释代码

#include<bits/stdc++.h>
using namespace std;
struct Student{
    int id, score;
}stu[110];
int n;

// 定义排序规则：先按成绩降序，成绩相同按学号升序
bool cmp(Student a, Student b){
    if(a.score != b.score) return a.score > b.score; // 成绩高的优先
    return a.id < b.id; // 成绩相同，学号小的优先
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> stu[i].id >> stu[i].score;

    // 冒泡排序主体
    for(int i = 1; i <= n - 1; i++){
        for(int j = 1; j <= n - i; j++){
            // 如果 stu[j] 不满足排在 stu[j+1] 前的规则，则交换
            if(!cmp(stu[j], stu[j+1])){
                swap(stu[j], stu[j+1]);
            }
        }
    }

    // 输出排序后的结果
    for(int i = 1; i <= n; i++){
        cout << stu[i].id << " " << stu[i].score << endl;
    }
    return 0;
}

易错点

比较函数逻辑：务必保证 cmp 函数返回值的正确性。
结构体交换：swap 可以直接交换两个结构体变量。

a30635 【结构体】【排序】年龄排序
思路简介
这是上一题的变种，核心都是对结构体数组进行冒泡排序。此处按年龄从小到大排序，年龄相同则按姓名字典序排序。练习目的完全一样，但比较的字段和规则发生了变化。

算法步骤拆解

1、定义结构体：Person 包含 name（字符串）和 age（整数）。
2、定义比较规则：
首先按年龄升序：a.age < b.age。
若年龄相同，按姓名字典序升序：a.name < b.name（C++ 字符串可直接比较）。
3、冒泡排序：与上一题完全相同的双重循环和判断逻辑。
4、输出：按序输出。

带注释代码

#include<bits/stdc++.h>
using namespace std;
struct Person{
    string name;
    int age;
}p[110];
int n;

// 定义排序规则：先按年龄升序，年龄相同按姓名升序
bool cmp(Person a, Person b){
    if(a.age != b.age) return a.age < b.age;
    return a.name < b.name; // 字符串可直接比较字典序
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> p[i].name >> p[i].age;

    // 冒泡排序
    for(int i = 1; i <= n - 1; i++){
        for(int j = 1; j <= n - i; j++){
            if(!cmp(p[j], p[j+1])){
                swap(p[j], p[j+1]);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        cout << p[i].name << " " << p[i].age << endl;
    }
    return 0;
}

第二组：选择排序 / 选中目标位置并交换

a29970 【PY】选择排序
思路简介
选择排序的核心是“选择-交换”。每一趟，你要在未排序部分中找到最小（或最大）的元素，然后把它放到未排序部分的起始位置。本题要求你模拟这个过程，你需要展示每一趟“选择并交换”后的结果，而不是直接用 sort。

算法步骤拆解

1、读入数据。
2、外层循环：控制趟数i 从1 到 n-1。i也是当前未排序部分的起始位置。
3、初始化最小值位置：假设 a[i] 就是未排序部分的最小值，用 min_pos = i 记录。
4、内层循环（选择）：从 j = i + 1 到 n 遍历未排序部分，如果发现 a[j] < a[min_pos]，则更新 min_pos = j。循环结束后，min_pos 就是未排序部分真正最小元素的位置。
5、交换（放置）：将找到的最小元素 a[min_pos] 与 a[i] 交换。这样，位置 i 就被放上了正确的最小元素。
6、输出状态：每一趟交换完成后，输出整个数组。

注意：选择排序是不稳定的（因为远距离交换可能打乱相等元素的相对顺序），但本题不涉及。

带注释代码

#include<bits/stdc++.h>
using namespace std;
int a[1010], n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    // 外层循环：i 既是趟数，也是未排序部分的起始下标
    for(int i = 1; i <= n - 1; i++){
        int min_pos = i; // 1. 先假设当前位置的元素是最小的
        // 2. 在未排序部分 [i+1, n] 中查找真正的最小值位置
        for(int j = i + 1; j <= n; j++){
            if(a[j] < a[min_pos]){
                min_pos = j; // 找到更小的，更新位置
            }
        }
        // 3. 将找到的最小元素交换到未排序部分的起始位置 i
        swap(a[i], a[min_pos]);

        // 4. 输出第 i 趟排序后的状态
        for(int k = 1; k <= n; k++) cout << a[k] << " ";
        cout << endl;
    }
    return 0;
}

关键点

选择排序与冒泡排序的区别：冒泡排序是相邻比较并立即交换；选择排序是“先找，再交换”，每趟最多只交换一次，但比较次数不变。

第三组：插入排序 / 动态维护有序序列

a29733 【PY】插入排序
思路简介
插入排序维护一个已排序的前缀。每一步，它将未排序部分的第一个元素取出来，插入到已排序前缀中的正确位置。这个“插入”操作在数组中是通过元素后移来实现的。本题要求模拟这个“插入”的动态过程。

算法步骤拆解

1、读入数据。
2、外层循环：从i = 2 到 n，表示准备将 a[i] 插入到已排序的前缀 a[1...i-1] 中。
3、暂存待插入元素：用 key = a[i] 保存当前值，因为后续移动元素会覆盖它。
4、寻找插入位置并后移：初始化 j = i - 1。当 j >= 1 且 a[j] > key 时，说明 a[j] 应该在 key 的后面，所以将 a[j] 向后移动一位：a[j+1] = a[j]，然后 j--。
5、插入：循环结束时，j 是最后一个不大于 key 的元素位置，key 应插入到 j+1 的位置：a[j+1] = key。
6、输出状态：每次插入完成后，输出整个数组。

稳定性：判断条件使用 > 而不是 >=，使得插入排序是稳定的（相等元素不交换）。

带注释代码

#include<bits/stdc++.h>
using namespace std;
int a[1010], n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    // 从第二个元素开始，将其插入到前面已排序的序列中
    for(int i = 2; i <= n; i++){
        int key = a[i]; // 1. 暂存当前要插入的值
        int j = i - 1;

        // 2. 将已排序部分中大于 key 的元素整体向后移动一位
        while(j >= 1 && a[j] > key){
            a[j + 1] = a[j];
            j--;
        }

        // 3. 将 key 插入到正确的位置 (j+1)
        a[j + 1] = key;

        // 4. 输出第 i-1 次插入后的数组状态
        for(int k = 1; k <= n; k++) cout << a[k] << " ";
        cout << endl;
    }
    return 0;
}

a49995 [CSP-J 2021] 插入排序
思路简介
这是CSP-J的真题，是插入排序的高阶应用。题目要求对一个数组进行两类操作：修改某个位置的值，或查询某个原始下标的元素在当前排序后的位置。核心难点在于：

修改后需要重新维护有序状态。
查询的是“原始下标”，而不是值。
插入排序是稳定排序，这为处理相同值的元素提供了依据。

算法步骤拆解

1、定义结构体：Node 包含 val（值）和 id（原始下标）。
2、初始排序：读入数据后，对结构体数组用 stable_sort（稳定排序）按 val 升序，val 相同按 id 升序排序。
3、处理操作：
修改操作 (op=1)：
3、输入位置 x 和新值 y。
2、在已排序的结构体数组中找到 id == x 的那个元素，将其 val 改为 y。
1、因为只有一个值改变，为了重新保持有序，可以简单地对整个数组再次使用 stable_sort（数据范围8000，nlog n 可接受）。
查询操作 (op=2)：
1、输入原始下标 x。
2、在已排序的结构体数组中遍历，找到 id == x 的元素，输出其在数组中的位置（下标）。

带注释代码

#include<bits/stdc++.h>
using namespace std;
const int N = 8010;
struct Node{
    int val, id; // 值 和 原始下标
}a[N];
int n, q;

// 排序规则：先按值升序，值相同按原始下标升序（保证稳定性）
bool cmp(Node x, Node y){
    if(x.val != y.val) return x.val < y.val;
    return x.id < y.id;
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i].val;
        a[i].id = i; // 记录原始下标
    }
    // 使用稳定排序进行初始排序
    stable_sort(a + 1, a + n + 1, cmp);

    while(q--){
        int op, x, y;
        cin >> op;
        if(op == 1){ // 修改操作
            cin >> x >> y; // 将原始下标为 x 的元素值改为 y
            // 在排序后的数组中找到该元素并修改其值
            for(int i = 1; i <= n; i++){
                if(a[i].id == x){
                    a[i].val = y;
                    break;
                }
            }
            // 修改后，重新对整个数组进行稳定排序以维持有序
            stable_sort(a + 1, a + n + 1, cmp);
        }else{ // 查询操作
            cin >> x; // 输出原始下标为 x 的元素在排序后的位置
            for(int i = 1; i <= n; i++){
                if(a[i].id == x){
                    cout << i << endl; // 输出当前位置
                    break;
                }
            }
        }
    }
    return 0;
}