嵌入式开发中的排序与查找算法优化实践

1. 排序与查找：嵌入式开发的基石能力

在嵌入式开发领域，排序和查找算法就像厨师的刀工一样基础而重要。我至今记得第一次在STM32上实现传感器数据排序时的场景——当500组温度数据在128KB内存的MCU上完成实时排序时，那种成就感至今难忘。这些看似简单的算法，在资源受限的嵌入式环境中往往需要精心优化才能发挥最佳性能。

选择排序、冒泡排序和插入排序作为最经典的O(n²)算法，虽然在通用计算领域已被更高效的算法取代，但在嵌入式场景中依然保持着旺盛的生命力。它们代码量小（通常不超过20行）、内存占用低（多数情况只需1-2个临时变量）、对硬件无特殊要求，特别适合在8/16位MCU上处理小规模数据集。配合二分查找这类高效查询方法，能解决大多数嵌入式场景下的数据处理需求。

2. 算法核心原理与嵌入式适配

2.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 temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

在资源受限环境中，我通常会做这些优化：

1. 使用寄存器关键字修饰循环变量：register int i
2. 关闭数组越界检查编译选项以提升速度
3. 对于8位MCU，将int改为byte/char节省空间

实测数据：在STM32F103（72MHz）上排序100个int数据，