17、排序算法（上）：冒泡排序、选择排序、插入排序——原理与C语言实现
排序，是编程里最基础、也最绕不开的话题。我刚开始学C语言那会儿，觉得排序不就是把数字排个序嘛，有啥难的？后来真到项目里才发现，选错排序算法，数据量一上来，程序直接卡死。嗯，今天咱们就把三个最经典的入门排序讲透——冒泡、选择、插入。
这三个算法，说白了就是三种不同的“折腾数据”的方式。你想想看，给你一副打乱的扑克牌，你怎么把它理顺？有人一张张比，有人挑最小的放前面，有人像打牌一样插来插去。这三种思路，正好对应了今天要讲的三个算法。
核心要点：这三个排序算法的时间复杂度都是 O(n²)，适用于小规模数据（通常 n < 1000）。它们的主要区别在于“比较”和“交换”的次数不同。
17.1 冒泡排序——最直观的排序
冒泡排序的思路特别简单：从头到尾，相邻两个数比较，如果前面比后面大，就交换。一轮下来，最大的数就“冒”到最后面了。然后对剩下的数重复这个过程。
我个人习惯把冒泡排序当作教学第一课。为什么？因为它最符合人的直觉。你想想看，一堆乱序的数字，你一眼看过去，是不是先找最大的？冒泡就是这么干的。
小技巧：可以加一个标志位 swapped，如果某一轮没有发生任何交换，说明已经有序了，直接跳出循环。这个优化在数据接近有序时效果很明显。
// 冒泡排序（优化版）
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 temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (!swapped) break; // 没交换，提前结束
}
}我曾经在一个数据采集项目里用过冒泡排序。当时采集器每秒钟才产生几十个数据点，用冒泡完全够用。后来数据量涨到每秒几千个，我赶紧换成了快速排序。嗯，冒泡这东西，数据量一过千就开始吃力了。
避坑指南：我曾经见过有人在内层循环写成 j < n - 1，没有减 i。这样每一轮都会比较已经排好的尾部数据，白白浪费 CPU。记住：每轮冒泡后，尾部 i 个元素已经有序，不需要再碰它们。
17.2 选择排序——最省事的交换
选择排序的思路是：每一轮找到最小的元素，放到最前面。说白了就是“挑最小的放第一个，挑第二小的放第二个……”
这个算法有个特点：交换次数特别少。不管数据多乱，n 个元素最多交换 n-1 次。我在项目中遇到过一种情况——往 EEPROM 里写数据，每次写入都有寿命限制。这时候选择排序就派上用场了，因为它交换次数最少，能最大程度延长 EEPROM 的寿命。
// 选择排序
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 temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}注意：选择排序是不稳定的。举个例子，数组 [5a, 5b, 3]，第一轮会把 3 和 5a 交换，结果变成 [3, 5b, 5a]，两个 5 的相对顺序变了。如果你的数据需要保持相同元素的原始顺序，别用选择排序。
你可能会问：那什么时候用选择排序？我的经验是：当交换成本远高于比较成本时。比如上面说的 EEPROM 写入，或者对链表排序（交换节点比交换值复杂得多）。
17.3 插入排序——打牌高手的最爱
插入排序的思路，说白了就是打牌时理牌的手法。你摸到一张新牌，从右往左看，找到合适的位置插进去。数组排序也是一样：把当前元素插入到前面已经排好序的序列中。
我个人特别喜欢插入排序。为什么？因为它有一个很实用的特性——数据基本有序时，效率极高。近乎有序的数据，插入排序的时间复杂度可以降到 O(n)。这个特性后来被用在了高级排序算法里，比如希尔排序和 Timsort。
// 插入排序
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; // 插入到正确位置
}
}实战经验：我在做实时数据排序时，经常用插入排序。因为新数据往往是追加到末尾的，而前面的数据已经有序。这时候插入排序只需要把新数据往前插几下就行，比冒泡和选择都快得多。
插入排序还有一个好处——它是稳定的。相同元素不会交换位置。这在多关键字排序时特别有用。比如先按姓名排，再按年龄排，稳定的排序能保证第一轮排序的结果不被破坏。
17.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²)。但实际用起来差别不小：
- 冒泡排序：适合教学，实际项目里我基本不用。除非数据量极小（几十个），而且你特别在意代码可读性。
- 选择排序：适合交换成本高的场景。比如操作硬件寄存器、写入非易失存储器。我那个 EEPROM 项目就是典型例子。
- 插入排序：这三个里我最常用的。数据量小或者基本有序时，它表现最好。很多高级排序（比如快速排序）在数据量小的时候也会回退到插入排序。
最后提醒一句：别在嵌入式项目里用冒泡排序处理大量数据。我曾经接手过一个项目，前辈用冒泡排 5000 个数据点，结果系统每 3 秒卡死一次。换成快速排序后，问题瞬间解决。排序算法选对了，事半功倍；选错了，事倍功半。
好了，三个基础排序就讲到这里。代码不多，但背后的思路值得反复琢磨。下一节咱们继续聊更高级的排序算法——归并排序和快速排序，那才是真正能打硬仗的算法。
公众号:蓝海资料掘金营，微信deep3321