20. 排序算法(二)：快速排序、归并排序、堆排序、排序算法性能对比
好，咱们接着聊排序。上一章我把冒泡、选择、插入这几个基础排序讲透了。这一章，咱们要上硬菜了——快速排序、归并排序、堆排序。这三个家伙，是面试里的常客，也是实际工程中最常用的排序利器。
我个人习惯把这三兄弟称为「高级三剑客」。为什么高级？因为它们都用到了同一个思想——分治。说白了，就是把大问题拆成小问题，小问题解决了，大问题自然就解决了。你想想看，是不是这个理？
20.1 快速排序：分而治之的典范
快速排序，简称快排。我当年第一次学快排的时候，觉得这名字起得真随意——因为它确实快。平均时间复杂度 O(n log n)，而且常数系数小，实际跑起来比归并排序还快。
快排的核心思想就三步：
- 选基准：从数组中挑一个元素，叫 pivot。
- 分区：把比 pivot 小的放左边，比 pivot 大的放右边。
- 递归：对左右两个子数组重复上述过程。
嗯，这里要注意：基准选得好不好，直接影响性能。我曾经在项目里遇到过，数据几乎有序时，我傻傻地选了第一个元素做基准，结果快排退化成了 O(n²)，跑得比冒泡还慢。后来我学乖了，要么随机选，要么取三数中值。
核心要点：快排是不稳定的排序算法。什么意思？就是相等的元素，排序后相对位置可能变。这一点在有些场景下很要命。
来看代码实现：
// 快速排序 - 分区函数
int partition(int arr[], int low, int high) {
// 我习惯取中间元素作为基准，避免最坏情况
int pivot = arr[(low + high) / 2];
int i = low - 1;
int j = high + 1;
while (1) {
do { i++; } while (arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i >= j) return j;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}避坑指南：我曾经在递归深度上吃过亏。数据量一大，递归调用栈可能溢出。建议在工程中用迭代版本，或者限制递归深度。
20.2 归并排序：稳定可靠的排序
归并排序，说白了就是「先拆后合」。把数组拆成单个元素，再两两合并成有序序列。这个过程非常稳定——时间复杂度永远是 O(n log n)，不管数据长什么样。
我为什么说它可靠？因为它是稳定排序。我在做数据库索引排序时，就偏爱归并排序。为什么？因为稳定！相等元素的相对顺序不会变，这在多关键字排序时特别重要。
但归并排序有个硬伤——需要额外的 O(n) 空间。你想想看，如果你在嵌入式设备上跑，内存就那么几 KB，归并排序可能就玩不转了。
// 归并排序 - 合并两个有序子数组
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 mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}注意：归并排序的递归深度是 log n，比快排安全。但如果你用迭代版，要小心控制合并的步长。我见过有人把步长写错了，结果排序出来是乱的。
20.3 堆排序：利用堆结构的排序
堆排序，说白了就是「建堆 + 取顶」。先把数组建成一个大顶堆，然后反复把堆顶（最大值）取出来，放到数组末尾，再调整堆。
堆排序有个很有意思的特点：它不需要额外空间，是原地排序。而且时间复杂度稳定在 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) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(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 temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}小技巧：堆排序的 heapify 函数，我习惯写成迭代版本而不是递归。因为递归版本在堆很大时，函数调用开销不小。迭代版用 while 循环，性能更好。
20.4 排序算法性能对比
好了，三剑客都讲完了。咱们来做个对比，看看它们到底谁强谁弱。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 快速排序 | 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) | 不稳定 | 内存紧张，实时系统 |
你可能会问：「那我到底该用哪个？」
我的建议是：
- 如果数据随机，内存够用，快排是首选。C 标准库的 qsort 就是快排。
- 如果需要稳定排序，或者数据量超大但内存也大，归并排序更靠谱。
- 如果内存是瓶颈，或者你不想操心递归栈的问题，堆排序最省心。
下面这张图，是我整理的排序算法知识体系，帮你理清思路：
最后说一句：排序算法这东西，光看是学不会的。我建议你打开 IDE，把上面三个代码都敲一遍，跑一跑，看看不同数据量下的表现。只有亲手调过 bug，才能真正理解它们。
公众号:蓝海资料掘金营，微信deep3321