54、排序算法：冒泡、选择、插入、快速排序的实现与比较

排序算法，可以说是嵌入式开发里的基本功了。说实话，我入行头三年，一直觉得排序嘛，能用就行。直到有一次在一个实时控制项目里，因为排序慢了那么几毫秒，导致整个控制周期超时，电机直接抖了起来……嗯，从那以后，我对排序算法的选择就再也不敢马虎了。

今天咱们就把冒泡、选择、插入、快速这四种排序算法掰开揉碎了讲。我会结合代码实现和实际场景，帮你搞清楚：什么时候该用谁，为什么。

一、先看一张图：四种排序的核心逻辑

我习惯先把整体框架画出来，这样你心里有个谱。下面这张图展示了四种排序的核心思路：

二、冒泡排序——最直观，但效率最低

冒泡排序的思路很简单：从头到尾，相邻两个元素比较，如果顺序不对就交换。每一轮下来，最大的元素就像气泡一样“浮”到最后面。

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²)，数据量一大就扛不住了。

三、选择排序——交换次数最少

选择排序的思路是：每一轮找到未排序部分的最小元素，放到已排序部分的末尾。它最大的特点是交换次数少——最多只交换n-1次。

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

我曾经在一个EEPROM写入项目里用过选择排序。因为EEPROM写入次数有限，每次写入都很宝贵。选择排序的交换次数最少，能最大程度减少写入操作。说白了，选它不是因为快，而是因为“省”。

四、插入排序——小数据量的王者

插入排序的思路，就像你打牌时理牌：把新摸到的牌插入到手中已经排好序的牌里。它对于基本有序的数据，效率极高，甚至能达到O(n)。

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 把比key大的元素往后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

嗯，这里要注意：插入排序是稳定的。而且它是原地排序，不需要额外内存。在嵌入式环境里，这两个特性非常讨喜。

五、快速排序——大数据的首选

快速排序用的是分治思想：选一个基准值，把小于基准的放左边，大于基准的放右边，然后递归处理左右两边。平均时间复杂度O(n log n)，是目前应用最广的通用排序算法。

void quick_sort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int i = left, j = right;
    int pivot = arr[(left + right) / 2];  // 取中间值做基准
    
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    
    quick_sort(arr, left, j);
    quick_sort(arr, i, right);
}

快速排序是不稳定的。而且它是递归实现，需要额外的栈空间（平均O(log n)，最坏O(n)）。

六、四种排序对比总结

好了，四种排序算法就讲到这里。每种算法都有它的脾气，没有绝对的好坏，只有合不合适的场景。下次写排序代码前，先问问自己：数据有多大？内存够不够？要不要稳定？想清楚了再动手，比上来就写要靠谱得多。

公众号:蓝海资料掘金营，微信deep3321