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

好，咱们接着聊排序。上一章讲了冒泡、选择、插入这些基础排序，说实话，那些在实际项目中用得不算多。今天要聊的这四个——快速排序、归并排序、堆排序、计数排序——才是真正上战场的东西。我在嵌入式项目里，但凡涉及到数据量稍大一点的排序，基本就是从这几位里挑。

你可能会问：「那到底用哪个？」别急，咱们一个一个拆开看。每个算法我都会讲清楚它的原理、代码实现，还有稳定性分析。嗯，稳定性这个点，很多教材一笔带过，但实际开发中踩过坑的人才知道它有多重要。

一、快速排序：实战中的王牌

快速排序，简称「快排」。说实话，这是我用得最多的排序算法，没有之一。为什么？因为它平均性能确实好，在大多数实际场景下，它比别的 O(n log n) 排序都要快那么一截。

原理其实不复杂：选一个基准值（pivot），把比它小的放左边，比它大的放右边，然后左右两边各自递归。就这么简单。但细节决定成败——基准怎么选？我见过不少新手直接取第一个元素，结果遇到有序数组直接退化成 O(n²)。

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

int partition(int arr[], int low, int high) {
    // 三数取中选基准
    int mid = low + (high - low) / 2;
    if (arr[mid] < arr[low]) swap(&arr[low], &arr[mid]);
    if (arr[high] < arr[low]) swap(&arr[low], &arr[high]);
    if (arr[high] < arr[mid]) swap(&arr[mid], &arr[high]);
    
    int pivot = arr[mid];
    swap(&arr[mid], &arr[high]);  // 把基准放到末尾
    
    int i = low - 1;
    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;
}

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

稳定性分析：快速排序是不稳定的。为什么？因为分区时交换操作可能打乱相等元素的相对顺序。举个例子，两个相等的数，如果其中一个被交换到另一边，它们的先后顺序就变了。我在处理带有时间戳的数据时吃过这个亏，后来改用归并排序才解决。

二、归并排序：稳定可靠的「老黄牛」

归并排序，说白了就是「先拆后合」。把数组不断对半拆，拆到只剩一个元素，然后再两两合并。合并的时候，谁小谁先上，这样就能保证稳定性。

我记得有一次做嵌入式数据采集系统，需要把多个传感器节点的数据按时间排序后上传。数据量不大，但要求稳定排序——时间戳相同的记录要保持采集顺序。我当时二话不说就选了归并排序。

// 归并排序 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);
    }
}

稳定性分析：归并排序是稳定的。关键就在合并时那个 if (L[i] <= R[j])——当左右相等时，优先取左边的元素，这样相等元素的相对顺序就不会变。你想想看，这个细节是不是很巧妙？

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

堆排序，说白了就是「先建堆，再取顶」。把数组看成一颗完全二叉树，先调整成大顶堆（父节点比子节点大），然后每次把堆顶（最大值）和末尾交换，再调整剩下的部分。

这个算法我第一次学的时候觉得挺绕的，但写多了就发现其实套路很固定。我个人习惯把堆排序用在那些「不需要稳定、但内存很紧张」的场景——因为它不需要额外空间。

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

稳定性分析：堆排序是不稳定的。原因在于堆调整过程中，父子节点的交换可能打乱相等元素的顺序。举个例子，如果有两个相等的数，一个在堆顶附近，一个在堆底，堆顶那个被交换到末尾后，堆底那个可能被调整到前面，顺序就乱了。

四、计数排序：非比较排序的「黑马」

计数排序和前面三个完全不同。它不是通过比较来排序，而是「数数」。原理很简单：统计每个值出现的次数，然后按顺序输出。

但有个前提——数据范围不能太大。比如你要排序 100 万个 0~255 之间的数，计数排序只需要 256 个计数器，快得飞起。但如果你要排序 100 万个 0~10 亿之间的数，那还是老老实实用快排吧。

// 计数排序 C 语言实现
void countingSort(int arr[], int n) {
    // 先找最大值
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
    
    // 分配计数数组
    int *count = (int *)calloc(max + 1, sizeof(int));
    
    // 统计每个值出现次数
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
    
    // 累加，用于稳定排序
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];
    
    // 回填到输出数组（从后往前，保证稳定）
    int *output = (int *)malloc(n * sizeof(int));
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
    
    free(count);
    free(output);
}

稳定性分析：计数排序是稳定的。关键在回填时从后往前遍历——后出现的相同元素会被放到后面，保持了原来的相对顺序。你想想看，这个「从后往前」是不是很巧妙？

五、四种排序算法对比总结

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
快速排序	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)	不稳定	内存受限、实时系统
计数排序	O(n + k)	O(n + k)	O(k)	稳定	数据范围小、整数排序

最后说一句：没有银弹。每种排序算法都有自己的脾气，选型时要结合数据规模、内存限制、稳定性要求来权衡。我个人在项目中一般是这么选的：数据量小且要求稳定 → 归并排序；数据量大且不要求稳定 → 快速排序；内存紧张 → 堆排序；数据范围小 → 计数排序。

好了，这四种排序算法就讲到这里。代码我都贴出来了，建议你亲手敲一遍，调试一下。有些坑，只有自己踩过才能真正记住。

---