排序算法（一）：冒泡排序、选择排序、插入排序、希尔排序

排序，是嵌入式开发里最基础也最常用的操作之一。你想想看，从传感器采集到的数据要排序，任务调度队列要排序，通信协议里的报文也要排序。我个人习惯把排序算法分成两类：简单排序和高级排序。今天咱们先聊四个简单但非常实用的——冒泡、选择、插入和希尔排序。

1. 冒泡排序：最直观的“泡”法

冒泡排序的思路特别简单：从头到尾，两两比较，把大的往后“冒”。每一轮下来，最大的数就像气泡一样浮到末尾。

我在项目中遇到过一个小问题：用冒泡排序处理一个256字节的数组，结果在8位MCU上跑了将近半秒。嗯，数据量小的时候还行，大了就扛不住了。

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;  // 没交换说明已经有序
    }
}

时间复杂度：最好 O(n)，最坏 O(n²)，平均 O(n²)。空间复杂度 O(1)。

2. 选择排序：每次挑最小的

选择排序的思路更直接：每一轮从剩余元素里挑出最小的，放到前面。说白了就是“矮子里拔将军”，一轮一个。

我曾经用选择排序给一个按键扫描的去抖数据排序，因为数据量只有10个左右，代码简单，不容易出错。但要注意，选择排序是不稳定的——相同值的元素可能会交换位置。

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;
        }
    }
}

时间复杂度：最好/最坏/平均都是 O(n²)。空间复杂度 O(1)。

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²)，平均 O(n²)。空间复杂度 O(1)。

4. 希尔排序：插入排序的“升级版”

希尔排序，说白了就是给插入排序加了一个“预处理”步骤。它先把数组按一定间隔分组，对每组进行插入排序，然后逐步缩小间隔，直到间隔为1时做一次完整的插入排序。

为什么这样能快？因为插入排序在数据“基本有序”时效率很高。希尔排序通过前期的大间隔排序，让数据快速接近有序状态。

我记得有一次在ARM Cortex-M3上做数据采集，数据量大概500个，用插入排序要跑好几毫秒，换成希尔排序后直接降到不到1毫秒。嗯，差距就是这么明显。

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 temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

5. 四种排序对比

6. 知识体系图

下面这张图帮你理清这四种排序的关系和选择思路：

7. 避坑指南

最后，分享几个我踩过的坑：

• 冒泡排序的优化陷阱：我曾经以为加了 swapped 标志就万事大吉，结果忘了在每轮开始时重置它。嗯，bug 找了一下午。
• 选择排序的不稳定性：有一次给结构体数组排序，按某个字段排序后，相同字段的原始顺序被打乱了。如果你需要稳定排序，别用选择排序。
• 希尔排序的增量选择：增量序列选不好，性能可能还不如插入排序。我一般用 gap = n/2 开始，简单够用。
• 嵌入式环境下的栈空间：递归排序（比如快速排序）在栈小的 MCU 上容易爆栈。希尔排序是迭代的，没有这个问题，所以我经常用它。

这四种排序是基础中的基础。你想想看，掌握了它们，再学快速排序、归并排序就会轻松很多。下一节咱们继续聊更高级的排序算法。