@Yezi.press
三大基础排序算法详解
汇总一下三大基础排序算法的写法以及时间空间复杂度、稳定性
Markdown发布于 2026/08/20编辑于 2026/10/29#排序
在学习信息学竞赛的路上,选择排序、插入排序、冒泡排序是逃不开的三座大山。它们的时间复杂度都是 O(n²),背后的思路和应用场景截然不同,这里和同学们一起汇总一下写法:
约定:本文所有代码均采用信奥常见写法,数组下标从 1 开始,有效数据存储在
a[1] ~ a[n],a[0]仅作为占位不使用。使用swap()进行交换,需包含<algorithm>头文件。
冒泡排序
原理
冒泡排序的核心思想是:相邻两两比较,大的元素像泡泡一样往后"冒"。
每一轮都会把当前未排序部分的最大值"冒"到最后面。
代码
这里加入了 flag 优化:如果某一轮没有发生任何交换,说明数组已经有序,可以提前退出。
C++void bubble_sort(int a[], int n) { for (int i = 1; i < n; i++) { bool flag = true; // 假设本轮已有序 for (int j = 1; j <= n - i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); // 大的往后冒 flag = false; // 发生交换,说明还没排好 } } if (flag) break; // 整轮无交换,提前结束 } }
特点
| 项目 | 说明 |
|---|---|
| 平均时间复杂度 | O(n²) |
| 最坏时间复杂度 | O(n²) |
| 最好时间复杂度 | O(n)(配合 flag 优化,数据已有序时一轮即停) |
| 空间复杂度 | O(1),原地排序 |
| 稳定性 | ✅ 稳定(相邻交换,不改变相等元素的相对顺序) |
适用场景:数据量小,或数据基本有序。代码逻辑最直观,非常适合作为排序算法的入门学习。
插入排序
原理
插入排序的核心思想是:将当前元素插入到前面已经排好序的序列中的正确位置。
就像打扑克牌时整理手牌一样,每摸到一张新牌,就把它插到手中已有牌的正确位置上。
代码
插入排序有两种常见写法:
- 后移法:交换次数更少,效率略高,但代码稍长。
C++void insert_sort(int a[], int n) { for (int i = 2; i <= n; i++) { // 从第2个元素开始,依次插入前面有序序列 int key = a[i]; // 记录当前要插入的值 int j = i - 1; // 从已排序部分的最后一个位置往前找 // 将比 key 大的元素往后移动一位 while (j >= 1 && a[j] > key) { a[j + 1] = a[j]; j--; } // 找到插入位置,将 key 放进去 a[j + 1] = key; } }
- 相邻交换法:使用
swap交换,代码更简洁。
C++void insert_sort(int a[], int n) { for (int i = 2; i <= n; i++) { // 将 a[i] 向左交换到正确位置 for (int j = i; j >= 2 && a[j] < a[j - 1]; j--) { swap(a[j], a[j - 1]); } } }
特点
| 项目 | 说明 |
|---|---|
| 平均时间复杂度 | O(n²) |
| 最坏时间复杂度 | O(n²) |
| 最好时间复杂度 | O(n)(数据已有序时,只比较不交换) |
| 空间复杂度 | O(1),原地排序 |
| 稳定性 | ✅ 稳定(相邻交换,不改变相等元素的相对顺序) |
适用场景:数据量小,或数据基本有序时效率极高(接近 O(n)),是三大排序中在部分有序数据下表现最好的。
选择排序
原理
选择排序的核心思想是:每一轮从未排序的部分中选出最小的元素,放到已排序部分的末尾。
用一句话记忆:"每轮选最小的放前面"。
代码
C++void select_sort(int a[], int n) { for (int i = 1; i < n; i++) { int idx = i; // 假设当前位置最小 for (int j = i + 1; j <= n; j++) { if (a[j] < a[idx]) idx = j; // 找到更小的,更新下标 } if (idx != i) swap(a[i], a[idx]); // 将最小元素交换到前面 } }
特点
| 项目 | 说明 |
|---|---|
| 平均时间复杂度 | O(n²) |
| 最坏时间复杂度 | O(n²) |
| 最好时间复杂度 | O(n²) |
| 空间复杂度 | O(1),原地排序 |
| 稳定性 | ❌ 不稳定(远距离交换可能改变相等元素的相对顺序) |
| 交换次数 | 最少(最多 n-1 次),当交换操作代价高时优先考虑 |
适用场景:数据量小,且对稳定性没有要求时适用。
三大排序横向对比总结
| 对比项 | 选择排序 | 插入排序 | 冒泡排序 |
|---|---|---|---|
| 平均时间复杂度 | O(n²) | O(n²) | O(n²) |
| 最坏时间复杂度 | O(n²) | O(n²) | O(n²) |
| 最好时间复杂度 | O(n²) | O(n) | O(n)(优化后) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 稳定性 | ❌ 不稳定 | ✅ 稳定 | ✅ 稳定 |
| 交换次数 | 最少(≤ n-1次) | 较多(平均 n²/4 次) | 较多(平均 n²/2 次) |
| 数据基本有序时 | 仍为 O(n²) | 效率最高 | 效率较高 |
| 核心记忆 | 选最小放前面 | 像打牌理牌 | 大的往后冒 |
写在最后
三大基础排序虽然在实际竞赛中很少直接使用(因为 sort() 更高效),但它们是理解更复杂排序算法(如快速排序、归并排序)的基石。
当你彻底理解了这三兄弟,就可以向 快速排序、归并排序、堆排序 等更高效的算法发起挑战了!🚀