15、排序算法（上）：冒泡、选择、插入排序，时间复杂度与稳定性分析
排序算法，是嵌入式开发里绕不开的基本功。我刚开始做嵌入式那会儿，总觉得排序是上层应用的事，单片机资源那么紧张，能省则省。直到有一次做数据采集系统，需要把传感器数据按时间戳排好再上传——嗯，那次我硬是用冒泡排序把系统搞崩了。从那以后，我再也不敢小看排序算法的选型。
这一章，咱们先聊三个最基础的排序：冒泡排序、选择排序、插入排序。它们虽然简单，但背后藏着很多值得琢磨的东西。比如时间复杂度怎么算？稳定性到底有什么用？在资源受限的MCU上，哪个更靠谱？
15.1 冒泡排序：最直观，但最慢
冒泡排序的思路，说白了就是：相邻两个元素比较，如果顺序不对就交换。每一轮下来，最大的数就像气泡一样浮到末尾。
来看代码：
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 提前退出标志
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swapped = 1;
}
}
// 如果没有交换，说明已经有序
if (!swapped) break;
}
}
这里我加了一个 swapped 标志位。为什么？因为如果某一轮没有发生任何交换，说明数组已经有序了，可以提前退出。这个优化我在项目里用过，数据接近有序时，能省不少时间。
时间复杂度：
- 最好情况（已经有序）：O(n) —— 得益于提前退出
- 最坏情况（完全逆序）：O(n²)
- 平均情况：O(n²)
空间复杂度：O(1)，原地排序
稳定性：稳定。因为相邻元素相等时不交换，相对顺序不变。
我的经验：冒泡排序在数据量小于100时还能用，超过100就明显变慢。在STM32这类MCU上，我建议数据量超过50就换别的算法。
15.2 选择排序：简单粗暴，但不稳定
选择排序的思路更直接：每一轮找到最小的元素，放到最前面。它不像冒泡那样频繁交换，而是每轮只交换一次。
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) {
int tmp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = tmp;
}
}
}
你想想看，选择排序的交换次数是 O(n)，而冒泡是 O(n²)。所以在数据量较大时，选择排序的实际运行时间往往比冒泡短。但它的缺点也很明显——不稳定。
我曾经踩过的坑：有一次需要对结构体数组按多个字段排序，先按时间排，再按优先级排。用了选择排序后，优先级相同的记录顺序被打乱了。排查了半天才发现是排序不稳定导致的。从那以后，只要涉及多关键字排序，我都会优先考虑稳定排序。
时间复杂度：
- 最好情况：O(n²) —— 即使有序，也要扫描所有元素
- 最坏情况：O(n²)
- 平均情况：O(n²)
空间复杂度：O(1)
稳定性：不稳定。因为交换可能把相同元素的相对顺序打乱。
15.3 插入排序：小数据量的王者
插入排序的思路，就像你打扑克牌时整理手牌：把新抓到的牌插入到已经排好序的牌中。它从第二个元素开始，逐个往前插入到合适的位置。
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
我个人习惯在数据量小（比如几十个元素）或者数据基本有序时，用插入排序。为什么？因为它有很好的特性：
- 数据基本有序时，效率极高，接近 O(n)
- 稳定排序，不会打乱相同元素的顺序
- 实现简单，代码量少，不容易出错
时间复杂度：
- 最好情况（已经有序）：O(n) —— 只需比较 n-1 次
- 最坏情况（完全逆序）：O(n²)
- 平均情况：O(n²)
空间复杂度：O(1)
稳定性：稳定。因为插入时遇到相等元素就停止，不会往前插。
我建议：在嵌入式项目中，如果数据量小于50且需要稳定排序，直接用插入排序。它比冒泡快，比选择排序稳定，代码也简单。很多高级排序（比如希尔排序、快速排序）的底层优化，也会在数据量小时回退到插入排序。
15.4 三种排序的对比与选型
咱们把这三个算法放在一起看看：
| 算法 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 交换次数 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 多 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 少 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 中等 |
从表格里能看出什么？
- 三个算法的最坏情况都是 O(n²)，但实际表现差异很大
- 插入排序在数据基本有序时表现最好
- 选择排序虽然不稳定，但交换次数最少，适合交换代价高的场景（比如大结构体）
- 冒泡排序...说实话，除了教学，我很少在实际项目里用它
15.5 稳定性到底有什么用？
你可能会问：稳定性这个特性，在嵌入式开发里真的用得上吗？
当然用得上。我给你举个例子：
假设你有一个传感器数据数组，每个元素包含 timestamp 和 value。你先按 timestamp 排好序，然后想按 value 再排一次。如果排序是稳定的，那么 value 相同的记录，会保持原来的 timestamp 顺序。如果不稳定，时间顺序就乱了。
我在做多传感器融合时，经常需要这种多级排序。所以只要条件允许，我会优先选稳定排序。
15.6 知识体系总览
下面这张图，帮你理清这三个排序的核心逻辑：
15.7 避坑指南
最后，分享几个我踩过的坑：
- 不要在大数据量上用 O(n²) 算法。我在一个项目里用冒泡排了1000个数据，结果系统卡了3秒。后来换成快速排序，瞬间完成。
- 注意排序的稳定性需求。如果后续需要多级排序，一定要用稳定排序。我曾经因为用了选择排序，导致数据顺序错乱，排查了整整一天。
- 插入排序的 while 循环条件。注意
j >= 0要写在前面，防止数组越界。这个错误我犯过不止一次。 - 嵌入式环境下的交换操作。如果交换的是结构体，用
memcpy比直接赋值更高效，但要注意内存对齐。
总结一下：
冒泡、选择、插入这三个排序，是理解更高级排序算法的基础。它们虽然简单，但背后的时间复杂度分析、稳定性概念，是每个嵌入式工程师必须掌握的。下一章，我们会聊更快的排序算法——希尔排序、归并排序和快速排序。到时候你会看到，这些高级算法很多地方都用到了插入排序的思想。
公众号:蓝海资料掘金营，微信deep3321