16、排序算法（下）：快速排序、归并排序、堆排序，分治思想与递归实现
排序算法这个话题，咱们上次聊了冒泡、选择和插入。说实话，那些属于「入门级」的功夫。今天要讲的这三个——快速排序、归并排序、堆排序，才是真正能在项目里扛大梁的角色。
它们有一个共同的思想内核：分治。说白了，就是把大问题拆成小问题，小问题再拆成更小的问题，直到拆不动了，再逐层合并回来。这个思想在嵌入式里太常用了——你想想看，处理一个大数据包，是不是也经常拆成小块来处理？
核心观点：分治思想 + 递归实现 = 高效排序的基石。理解了这个组合，你就能写出 O(n log n) 级别的排序代码。
快速排序：选个「老大」来分家
快速排序的思路很直白：从数组里挑一个元素当「基准」，然后把比它小的放左边，比它大的放右边。左右两边各自再重复这个过程。
我个人习惯选中间元素当基准，这样在大多数情况下分区比较均衡。不过要注意，如果数组已经有序，选第一个或最后一个当基准，性能会退化到 O(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) {
swap(&arr[i], &arr[j]);
i++;
j--;
}
}
// 递归处理左右两部分
quick_sort(arr, left, j);
quick_sort(arr, i, right);
}小技巧：当数据量较小时（比如少于10个元素），快排的递归开销反而比插入排序大。我一般会在递归函数里加个判断：如果区间长度小于阈值，直接调用插入排序。这叫「混合排序」，性能能再提升10%-15%。
归并排序：先拆后合，稳扎稳打
归并排序的思路更「规整」：把数组从中间一分为二，左右各自排好序，然后再合并起来。这个过程递归下去，直到每个子数组只有一个元素——单个元素当然是有序的。
归并排序最大的优点是稳定。什么意思？就是相等的元素在排序后，相对顺序不变。这在某些场景下很重要。比如你按时间排序后，再按优先级排序，稳定排序能保证时间顺序不被破坏。
但归并排序有个「硬伤」：它需要额外的 O(n) 空间来存储临时数组。在嵌入式系统里，内存可是金贵的。我曾经在一个只有 64KB RAM 的 MCU 上做数据排序，归并排序直接撑爆了内存，最后换成了原地排序的堆排序才解决问题。
// 归并排序的合并操作
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);
}
}避坑指南：我曾经在递归实现归并排序时，忘记检查 left 和 right 的边界条件，导致栈溢出。递归深度是 log n，但每次递归都会压栈。如果数组有 10 万个元素，递归深度大约 17 层，没问题。但如果数据量上千万，递归深度到 24 层以上，就要小心栈空间了。
堆排序：用二叉树的思想排序
堆排序的思路稍微绕一点，但理解了就很简单。它把数组看作一棵完全二叉树，然后构建一个「大顶堆」——父节点比子节点都大。建好堆之后，根节点就是最大值，把它和最后一个元素交换，然后对剩下的元素重新调整堆。
堆排序的好处是：不需要额外空间，而且时间复杂度稳定在 O(n log n)，不会像快排那样退化。坏处是：它不稳定，而且实际运行速度通常比快排慢一点——因为堆排序的缓存局部性不如快排好。
// 堆排序实现
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) {
swap(&arr[i], &arr[largest]);
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--) {
swap(&arr[0], &arr[i]); // 把最大值放到末尾
heapify(arr, i, 0); // 调整剩余堆
}
}我的经验：堆排序特别适合「实时系统」中的优先级调度。比如一个任务队列，你需要不断取出最高优先级的任务，同时还要插入新任务。用堆来实现优先级队列，插入和删除都是 O(log n)，比线性查找快得多。
三种排序的对比与选择
说了这么多，到底该用哪个？我整理了一个表格，方便你对照选择：
| 特性 | 快速排序 | 归并排序 | 堆排序 |
|---|---|---|---|
| 平均时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 最坏时间复杂度 | O(n²) | O(n log n) | O(n log n) |
| 空间复杂度 | O(log n) 栈空间 | O(n) 额外数组 | O(1) 原地排序 |
| 稳定性 | 不稳定 | 稳定 | 不稳定 |
| 适用场景 | 通用排序，数据随机 | 需要稳定排序，内存充足 | 内存受限，需要稳定性能 |
嗯，这里要注意：没有「最好」的排序算法，只有「最合适」的。在嵌入式项目里，我通常会这样选：
- 内存充足、数据随机：用快速排序，速度最快
- 需要稳定排序：用归并排序，但要注意内存开销
- 内存紧张、实时性要求高：用堆排序，性能稳定不退化
递归的「代价」与优化
这三种排序都用了递归。递归写起来确实优雅，但递归是有代价的——每次函数调用都要压栈、传参、返回。在嵌入式系统里，栈空间通常只有几 KB，递归深度太深会直接导致栈溢出。
我建议你养成一个习惯：预估递归深度。对于 n 个元素的排序，快排和归并的递归深度大约是 log₂n，堆排序的递归深度也是 log₂n。如果 n=1024，深度就是 10，没问题。但如果 n=1,000,000，深度就是 20，也还好。但如果你在递归函数里用了大量局部变量，那就要小心了。
优化建议：对于快排，可以手动实现「尾递归优化」——只递归处理较短的那一半，较长的用循环处理。这样能把最坏情况下的栈深度从 O(n) 降到 O(log n)。代码改动不大，但效果很明显。
好了，排序算法这块儿就聊到这儿。分治思想不仅在排序里用，在二分查找、归并、FFT 等很多算法里都能看到它的影子。理解了分治，你就掌握了一把解决复杂问题的钥匙。
公众号:蓝海资料掘金营，微信deep3321