18、排序算法（下）：快速排序、归并排序、堆排序——原理与C语言实现

上一章我们聊了冒泡、选择、插入这些基础排序。说实话，那些算法在数据量小的时候还能凑合用。但一旦数据量上了万级，甚至十万级，你就会发现程序像卡住了一样。这时候，就该请出我们今天的主角了——快速排序、归并排序、堆排序。

这三种排序，平均时间复杂度都是 O(n log n)。它们代表了不同的设计思想：分治、归并、堆结构。我个人在实际项目中，这三种都用过，各有各的适用场景。今天我就把它们的原理、实现、以及我踩过的坑，一次性讲清楚。

一、快速排序：分而治之的典范

快速排序的核心思想很简单：选一个基准值，把比它小的放左边，比它大的放右边。然后左右两边递归处理。嗯，说起来简单，但实现起来有几个关键点要注意。

我在项目中用过很多次快速排序。有一次处理传感器采集的时间序列数据，数据量大概几十万条，用冒泡排序跑了半天没出结果，换成快排后秒出。那一刻我真是感慨——选对算法太重要了。

1. 基准元素的选择

基准选得好不好，直接影响性能。最理想的情况是每次都能把数组分成两半。但如果你每次都选第一个元素，而数据恰好是逆序的，那快排就退化成了 O(n²)。

我个人习惯用「三数取中法」——取左端、中间、右端三个元素的中位数作为基准。这样能有效避免最坏情况。

2. 分区函数实现

分区是快排的核心。我见过很多新手写分区时搞出死循环。这里给一个我常用的实现：

// 分区函数：返回基准元素的最终位置
int partition(int arr[], int low, int high) {
    // 三数取中：选中间值作为基准
    int mid = low + (high - low) / 2;
    if (arr[mid] < arr[low]) swap(&arr[mid], &arr[low]);
    if (arr[high] < arr[low]) swap(&arr[high], &arr[low]);
    if (arr[high] < arr[mid]) swap(&arr[high], &arr[mid]);
    
    // 把基准放到倒数第二个位置
    swap(&arr[mid], &arr[high - 1]);
    int pivot = arr[high - 1];
    
    int i = low, j = high - 1;
    while (1) {
        while (arr[++i] < pivot);  // 从左找大于等于基准的
        while (arr[--j] > pivot);  // 从右找小于等于基准的
        if (i >= j) break;
        swap(&arr[i], &arr[j]);
    }
    swap(&arr[i], &arr[high - 1]);  // 把基准放回正确位置
    return i;
}

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

二、归并排序：稳定可靠的排序

归并排序的思路更直观：先把数组分成两半，分别排序，然后合并。你想想看，合并两个有序数组是不是很简单？这就是归并排序的精髓。

归并排序最大的优点是稳定。什么叫稳定？就是相等的元素在排序后保持原来的相对顺序。这在某些场景下很重要。比如你按时间排序后，再按优先级排序，稳定排序能保证时间顺序不被破坏。

1. 合并过程

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

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

三、堆排序：利用堆结构的排序

堆排序的思路有点不一样。它先把数组建成一个最大堆，然后反复把堆顶（最大值）和堆尾交换，再调整堆。说白了，就是利用堆这种数据结构来快速找到最大值。

堆排序的好处是：最坏情况也是 O(n log n)，而且不需要额外空间。但它的缺点也很明显——不稳定，而且实际运行速度通常比快排慢一点。

1. 堆的调整

堆排序的核心是「堆化」操作。给定一个节点，保证它和它的子树满足堆的性质。

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);        // 调整剩余堆
    }
}

四、三种排序的对比

说实话，这三种排序没有绝对的好坏。我在实际项目中是这样选的：

• 如果数据量不大，或者对稳定性有要求，用归并排序
• 如果内存很紧张，用堆排序
• 其他情况，默认用快速排序

我记得有一次做嵌入式项目，MCU的RAM只有64KB，要排序几万个数据点。堆排序就成了唯一的选择——因为它不需要额外空间。那次经历让我深刻体会到：没有最好的算法，只有最合适的算法。