C++ · 排序
冒泡、插入、选择排序及稳定性
对比选择排序与插入排序的操作、复杂度和稳定性，保留冒泡排序与 std::sort 示例，并用相同数组逐轮检查结果。
冒泡、插入、选择排序与标准库排序
排序就像整理书架：把高矮不一的书按顺序摆好。不同方法有不同效率：
- 冒泡排序：相邻两个比较，大的往后"冒泡"，时间复杂度 O(n²)。
- 选择排序：每轮找最小值放到前面，时间复杂度 O(n²)。
- 插入排序：像整理扑克牌，每次把新牌插入已排好的位置，时间复杂度 O(n²)。
- 标准库 sort：保证 O(n log n) 级别的比较次数，常见实现采用内省排序；不能把它等同于可能退化的手写快速排序。
复试中数据量小可用 O(n²) 算法，数据量大必须用 sort。
稳定性：相同关键字的记录排序后仍保持原先相对次序，才叫稳定。只在严格逆序时交换的冒泡排序、只移动严格大于新值元素的插入排序是稳定的；普通交换式选择排序通常不稳定，std::sort 也不保证稳定，需要时使用 stable_sort。
选择排序每轮在未排序部分找最小值，与当前位置交换；插入排序把当前位置暂存，再将已排序部分中比它大的元素右移，最后放入空位。插入排序在已排序输入上可为 O(n)，但最坏仍是 O(n²)。
选择排序与插入排序：同一数组逐轮比较
输入为 [3, 1, 2]。选择排序第一轮选出最小值并交换，得到 [1, 3, 2]；第二轮得到 [1, 2, 3]。插入排序先把 1 插入已排序前缀，得到 [1, 3, 2]，再把 2 插入，得到 [1, 2, 3]。中间数组相同，执行的比较和移动并不相同。
| 常见实现 | 选择排序 | 插入排序 |
|---|---|---|
| 主要操作 | 在后缀找最小值，再交换 | 向右移动较大元素，再插入 |
| 最好时间 | Θ(n²) | Θ(n)，输入已排序时 |
| 平均／最坏时间 | Θ(n²) | Θ(n²) |
| 额外空间 | O(1) | O(1) |
| 稳定性 | 通常不稳定 | 仅移动严格较大值时稳定 |
常见选择排序总要做 n(n−1)/2 次键比较，但至多 n−1 次交换；插入排序在已排序输入中只需 n−1 次键比较，逆序时移动次数可达 n(n−1)/2。交换和移动不是同一个计量，不应直接等同。
先自己判断：相等元素也向右移动的插入排序，还能保证稳定吗？
不能。原本靠后的相等元素可能被插到前面；只移动严格较大的元素才能保留原顺序。
排序过程、比较器与稳定性
例1：冒泡排序（理解排序过程）
#include <iostream>
using namespace std;
int main() {
int a[] = {5, 3, 8, 1, 4};
int n = 5;
// 冒泡：n-1 轮，每轮把最大值沉到末尾
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl; // 输出 1 3 4 5 8
return 0;
}第1轮：5和3交换→3,5,8,1,4；5和8不换；8和1交换→3,5,1,8,4；8和4交换→3,5,1,4,8（8沉底）。经过4轮后得到 1 3 4 5 8。
例2：使用 sort + 自定义比较函数
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
int a[] = {5, 3, 8, 1, 4};
int n = 5;
// 升序（默认）
sort(a, a + n);
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl; // 1 3 4 5 8
// 降序：使用 中的 greater 比较器
sort(a, a + n, greater<int>());
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl; // 8 5 4 3 1
return 0;
} sort(首地址, 尾地址+1) 对数组原地排序。默认升序；传入 greater<int>() 得降序。竞赛中首选 sort，速度远超冒泡。
例3：插入排序保持相等元素的顺序
#include <iostream>
using namespace std;
int main() {
int a[] = {3, 1, 2, 1};
for (int i = 1; i < 4; ++i) {
int value = a[i], j = i - 1;
while (j >= 0 && a[j] > value) { a[j + 1] = a[j]; --j; }
a[j + 1] = value;
}
for (int x : a) cout << x << " ";
cout << endl;
}输出 1 1 2 3。相等元素不向右移，新的同值项放在已有同值项后面，从而保持稳定。
例4：选择排序的交换可能破坏稳定性
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
pair<int,char> a[] = {{2,'A'}, {2,'B'}, {1,'C'}};
for (int i = 0; i < 3; ++i) {
int best = i;
for (int j = i + 1; j < 3; ++j) if (a[j].first < a[best].first) best = j;
swap(a[i], a[best]);
}
for (auto x : a) cout << x.first << x.second << " ";
cout << endl;
}输出 1C 2B 2A。首轮把 1C 与 2A 交换后，原本在 2B 前面的 2A 被移到后面，说明不稳定。
提示
- 冒泡/选择/插入排序时间复杂度都是 O(n²)，n 超过 10000 时很慢；数据量大一定用 sort（O(n log n)）。
- 用 sort 排序结构体时，写自定义 cmp 函数，注意 cmp 必须返回 bool 且严格满足"严格弱序"（相等时不能返回 true）。
- 冒泡排序内层循环要写 j < n-1-i，少写 -i 会多做无用比较。
- 理解每种排序的思想：冒泡——相邻比较交换；选择——找最小放前面；插入——插入已有序列。复试可能考手动模拟排序过程。
先修知识
技术参考
范围说明
本站讲解由 InfoCode 编写，不是官方考纲；参考级别是本站映射，不代表官方等级、认证或参赛资格。练习记录不等于掌握或资格。
参考级别：GESP 4 级（本站映射）