排序算法（下）：堆排序、归并排序、快速排序

好，咱们接着聊排序。上一章我们把插入排序、选择排序、冒泡排序这些基础算法过了一遍。说实话，那些算法在数据量小的时候还能凑合用，一旦数据量上了万，性能就捉襟见肘了。今天我要讲的这三个——堆排序、归并排序、快速排序——才是真正能在生产环境里扛大梁的角色。

我个人习惯把这三兄弟称为「高级排序三剑客」。它们的时间复杂度都能做到 O(n log n)，但各自的脾气秉性完全不同。你想想看，同样是 O(n log n)，为什么有的场景用快排，有的场景用归并？这里面的门道，我今天一次给你讲透。

一、堆排序：利用堆结构玩转选择排序

堆排序，说白了就是把数组看成一颗完全二叉树，然后利用堆的性质来排序。我记得刚学这玩意儿的时候，总觉得它很玄乎——明明是个数组，怎么就成了堆了？

其实核心就两步：建堆和调整。

1. 什么是堆？

堆是一个完全二叉树，并且满足：
- 大顶堆：每个节点的值 ≥ 它的左右孩子
- 小顶堆：每个节点的值 ≤ 它的左右孩子

我们用数组来存储这个树。比如数组 [9, 5, 8, 2, 3] 对应的大顶堆，根节点 9 是最大值。

2. 堆排序的流程

1. 把无序数组构建成一个大顶堆
2. 把堆顶元素（最大值）和末尾元素交换
3. 堆的大小减 1，然后对新的堆顶做下沉调整
4. 重复步骤 2-3，直到堆为空

// 堆排序 - C语言实现
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 下沉调整：对以 i 为根的子树做堆化
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 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--) {
        swap(&arr[0], &arr[i]);   // 堆顶放到末尾
        heapify(arr, i, 0);       // 对剩余元素重新堆化
    }
}

二、归并排序：分治思想的典范

归并排序，我特别喜欢它的稳定性。什么意思？就是相等的元素在排序后，相对顺序不会变。这在很多实际场景里非常重要——比如按时间排序后，再按优先级排序，你希望相同优先级的记录依然按时间有序。

1. 核心思想

分而治之：
- 把数组从中间切成两半
- 分别对左右两半排序
- 把两个有序的子数组合并成一个

2. 合并操作是关键

合并两个有序数组时，需要额外的辅助空间。这也是归并排序唯一的「缺点」——空间复杂度 O(n)。

// 归并排序 - C语言实现
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);
    }
}

三、快速排序：实际应用中的王者

快排，说实话，是我用得最多的排序算法。没有之一。C 标准库里的 qsort 就是快排。为什么它这么受欢迎？因为平均情况下它最快，而且可以原地排序，不需要额外空间。

1. 核心思想

选一个基准值（pivot），把数组分成两部分：
- 左边都比 pivot 小
- 右边都比 pivot 大
然后递归地对左右两部分排序。

2. 分区函数（partition）

这是快排的灵魂。我习惯用 Lomuto 分区方案，简单好记。

// 快速排序 - C语言实现
int partition(int arr[], int low, int high) {
    int pivot = arr[high];   // 选最后一个元素做基准
    int i = low - 1;         // i 指向小于 pivot 的区域的末尾

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;  // 返回 pivot 的最终位置
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

我记得有一次在项目中，用户反馈某个排序操作特别慢。一查，原来数据是从数据库里按主键顺序取出来的，本身就是有序的。我用的是固定选最后一个元素做 pivot，结果快排变成了冒泡排序。后来改成随机 pivot，性能就正常了。

四、排序算法的比较与总结

好了，三个高级排序算法都讲完了。咱们来做个横向对比，这样你以后选型的时候心里有数。

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	需要原地排序、对稳定性无要求
归并排序	O(n log n)	O(n log n)	O(n)	稳定	需要稳定排序、数据量大但内存够
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	通用场景、内存敏感、数据随机

五、知识体系总览

下面这张图，我把本章的核心知识点串起来了。你一看就明白这三个算法之间的关系和区别。

嗯，到这里，排序算法的核心内容就讲完了。你可能会问：到底哪个排序最好？其实没有绝对的「最好」，只有「最合适」。我做了这么多年开发，见过有人用快排处理百万级数据，也见过有人用归并做外部排序。关键是你得理解每个算法的脾气，然后根据场景去选。

下次如果你在面试中被问到「排序算法怎么选」，你可以把今天讲的这些拿出来，从时间复杂度、空间复杂度、稳定性三个维度去分析。面试官一定会觉得你是个有经验的工程师。

---