排序算法：从冒泡到堆排，我这些年用过的排序“兵器”
排序，是嵌入式开发里躲不开的基本功。你写个菜单排序、传感器数据整理、或者通信协议里的优先级队列，都离不开它。我这些年带项目，见过不少同事一上来就写冒泡，结果数据量一大，系统直接卡死。说白了，排序算法选不对，后面全是坑。
今天咱们就把七种经典排序算法捋一遍。我会结合自己的实战经验，告诉你每种算法什么时候该用，什么时候千万别碰。
核心观点：没有最好的排序，只有最合适的排序。理解每种算法的“脾气”，比死记硬背代码重要一百倍。
1. 冒泡排序——最直观，但也最“笨”
冒泡排序的思路很简单：从头到尾，两两比较，大的往后“冒”。每轮下来，最大的数就沉到末尾了。
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; // 没交换，说明已经有序
}
}我的经验：我曾在某款低端MCU上调试一个菜单排序功能，数据量只有20个左右。当时同事用了冒泡，结果每次按键排序都要等几百毫秒。后来我加了个标志位——就是上面代码里的 swapped——如果某一轮没发生交换，直接跳出。效果立竿见影，响应时间降到几十毫秒。
冒泡的优点是稳定、好理解。缺点是慢——O(n²)。数据量超过100，我建议你直接换别的。
2. 选择排序——简单直接，但不稳定
选择排序的思路：每轮找到最小的元素，放到最前面。说白了就是“挑柿子，捡软的捏”。
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;
}
}
}注意：选择排序是不稳定的。举个例子，两个相同值的元素，排序后它们的相对顺序可能会变。如果你需要保持原始顺序（比如按成绩排序，成绩相同按学号排），就别用选择排序。
选择排序的优点是交换次数少——最多n-1次。缺点是无论数据是否有序，都得老老实实跑完O(n²)。
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)。我做过一个实时数据采集系统，传感器数据基本是递增的，偶尔有几个乱序。用插入排序，几乎感觉不到延迟。
插入排序是稳定的，而且实现简单。数据量小（比如50以内）时，它甚至比快速排序还快——因为快排有递归开销。
4. 希尔排序——插入排序的“升级版”
希尔排序是插入排序的改进。它先让数据“基本有序”，然后再做一次完整的插入排序。核心在于“增量序列”的选择。
void shell_sort(int arr[], int n) {
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;
}
}
}我的建议：希尔排序的增量序列有很多种选择。我习惯用 gap = n/2 开始，每次除以2。虽然这不是最优的，但胜在简单，而且大多数场景下性能已经够用。如果你追求极致性能，可以研究一下Hibbard增量或Sedgewick增量。
希尔排序的时间复杂度大约在O(n^1.3)到O(n^1.5)之间，比O(n²)快不少。但它是不稳定的。
5. 快速排序——实战中最常用的排序
快速排序，简称快排。它的核心是“分治”：选一个基准值，把比它小的放左边，比它大的放右边，然后递归处理左右两边。
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
int tmp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = tmp;
return i + 1;
}
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}避坑指南：我曾经在嵌入式项目里直接用快排，结果数据量一大就栈溢出。为什么？因为递归深度太深了。后来我改成了“尾递归优化”或者干脆用迭代版本。另外，如果数据已经有序，快排会退化到O(n²)——这时候可以随机选基准值来避免。
快排的平均时间复杂度是O(n log n)，而且它是原地排序（不需要额外空间）。但要注意，它是不稳定的。
6. 归并排序——稳定，但吃内存
归并排序也是分治思想：先把数组分成两半，分别排序，然后合并。它的核心在于“合并”这一步。
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}适用场景：归并排序是稳定的，而且时间复杂度稳定在O(n log n)。但它需要O(n)的额外空间。我在处理链表排序时特别喜欢用归并——因为链表不需要额外空间就能实现合并。但在嵌入式环境里，如果内存紧张，我一般不用它。
7. 堆排序——利用堆结构，空间省
堆排序利用的是“最大堆”或“最小堆”的性质。每次把堆顶元素（最大或最小）取出来，放到数组末尾，然后调整堆。
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int tmp = arr[i];
arr[i] = arr[largest];
arr[largest] = tmp;
heapify(arr, n, largest);
}
}
void heap_sort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
heapify(arr, i, 0);
}
}我的经验：堆排序是原地排序，空间复杂度O(1)，这一点在嵌入式里很吃香。但它是不稳定的，而且实际运行速度通常比快排慢一点——因为CPU缓存不友好。不过，如果你需要“随时取最大/最小元素”，堆结构本身比排序更有用。
8. 排序算法的比较与选择
好了，七种算法都过了一遍。你可能会问：到底该用哪个？
我个人的选择原则是这样的：
- 数据量小（<50）：插入排序。简单、稳定、近乎有序时飞快。
- 数据量中等（50~1000）：希尔排序或快排。希尔实现简单，快排更快但要注意递归深度。
- 数据量大（>1000）：快速排序（平均最快）或归并排序（需要稳定时）。
- 内存受限：堆排序。原地排序，不占额外空间。
- 需要稳定性：归并排序或插入排序。
- 数据近乎有序：插入排序。时间复杂度接近O(n)。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学、小数据量 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 交换次数少的场景 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小数据量、近乎有序 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 | 中等数据量 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 大数据量、通用 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大数据量、需要稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存受限、优先级队列 |
最后提醒一句：别在嵌入式里用递归太深的算法。我曾经在一个只有2KB RAM的MCU上跑快排，递归深度一上来，栈直接爆了。后来改成迭代版堆排序，问题解决。你想想看，系统都崩了，算法再快有什么用？
排序算法这东西，光看不行，得动手写。我建议你把这七种算法都自己实现一遍，然后跑几个测试用例对比一下。等你真正遇到性能瓶颈时，脑子里自然就知道该选哪个了。