【重发】三种基础排序专题讲解
2026-08-23 21:18:10
发布于：江苏
三种基础排序专题
题单分为三组，建议按以下顺序学习，以符合思维递进过程：
第一组：冒泡排序 / 相邻交换
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;
}
关键点与易错点
1、稳定性：必须使用 stable_sort，因为当值相同时，需要保持原始下标的顺序，题目要求的“位置”是基于稳定排序的。
2、修改后的处理：直接对整个数组重新排序是思路最清晰且对本题数据范围可行的做法。
3、查询的是“原始下标”：这一点需要特别留意，不能直接查值。
全部评论 4
- 置顶
顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶 顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶2天前 来自 江苏
1
有帮助，赞一个