排序算法（上）：冒泡、选择、插入、希尔
排序，是嵌入式开发里躲不开的基本功。
我刚开始写单片机程序时，总觉得排序是“上层的事”。直到有一次做数据采集系统，传感器一口气吐了200个乱序的采样值，我得在中断里快速把它们排好，再送出去显示。那时候我才意识到——排序算法选不对，系统响应时间直接崩掉。
今天咱们就把四种基础排序算法讲透。它们虽然简单，但理解透了，后面学快排、堆排序才会顺手。
1. 冒泡排序：最直观，但最慢
冒泡排序的思路，说白了就是“大的往后沉”。
每一轮从头到尾比较相邻两个元素，如果前一个比后一个大，就交换。一轮下来，最大的数就“冒”到了最后。然后下一轮忽略最后一个，继续。
C语言实现
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; // 没交换，说明已经有序
}
}复杂度分析
| 情况 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 最好（已有序） | O(n) | O(1) |
| 最坏（逆序） | O(n²) | O(1) |
| 平均 | O(n²) | O(1) |
2. 选择排序：简单直接，但不稳定
选择排序的思路更“暴力”——每一轮找到未排序部分的最小值，直接放到最前面。
你想想看，它不像冒泡那样频繁交换，而是每轮只交换一次。但代价是，它没法提前结束，不管数据多有序，都得跑完 n-1 轮。
C语言实现
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(1) |
| 最坏 | O(n²) | O(1) |
| 平均 | O(n²) | O(1) |
嗯，这里要注意：选择排序的时间复杂度是“铁板一块”，不管数据长什么样，都是 O(n²)。所以它只适合数据量极小、且不要求稳定性的场景。
3. 插入排序：小数据量的王者
插入排序的思路，很像你打扑克牌时整理手牌——每次摸一张新牌，插入到已经排好序的手牌中正确的位置。
我个人非常喜欢插入排序。为什么？因为它在数据基本有序时，效率高得吓人。而且它是稳定排序，实现也简单。
C语言实现
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(1) |
| 最坏（逆序） | O(n²) | O(1) |
| 平均 | O(n²) | O(1) |
4. 希尔排序：插入排序的“升级版”
希尔排序，说白了就是“分组插入排序”。
它先把数组按一定间隔（gap）分成若干子序列，对每个子序列做插入排序。然后缩小 gap，重复这个过程，直到 gap=1 时做一次完整的插入排序。
为什么要这么做？因为插入排序在数据基本有序时效率很高。希尔排序通过“大步跳跃”的方式，让数据快速接近有序状态。
C语言实现
void shell_sort(int arr[], int n) {
// 使用 Hibbard 增量序列：1, 3, 7, 15, ...
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > key) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
}复杂度分析
| 增量序列 | 时间复杂度（平均） | 空间复杂度 |
|---|---|---|
| n/2 递减 | O(n²)（最坏） | O(1) |
| Hibbard 增量 | O(n^(3/2)) | O(1) |
| Sedgewick 增量 | O(n^(4/3)) | O(1) |
5. 四种排序对比总结
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 数据量极小（<50） |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 数据量小，不要求稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 数据量小或基本有序 |
| 希尔排序 | O(n log n) | O(n²)~O(n^(4/3)) | 取决于增量 | O(1) | 不稳定 | 中等规模数据（<5000） |
我个人建议：
- 数据量 < 50：用插入排序，简单稳定。
- 数据量 50~5000：用希尔排序，选好增量序列。
- 数据量 > 5000：别用这四种了，后面会讲快速排序和归并排序。
6. 知识体系图
下面这张图帮你理清这四种排序的关系和选择逻辑：
好了，这四种排序算法就讲到这里。它们虽然基础，但理解透了，后面学高级排序会轻松很多。记住：没有最好的算法，只有最适合场景的算法。下次写排序代码前，先问问自己——数据有多大？是否基本有序？要不要稳定？想清楚再动手。
公众号:蓝海资料掘金营，微信deep3321