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

上一章我们聊了冒泡、选择、插入这些基础排序。说实话，那些算法在实际项目中用得不多——数据量一上去，性能就扛不住了。今天要讲的这四种，才是真正能在生产环境里撑场面的家伙。

快速排序、归并排序、堆排序，都是 O(n log n) 级别的比较排序。计数排序呢，路子不一样，它是非比较排序，在某些场景下快得离谱。我一个个说。

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

快速排序的核心思想很简单：选一个基准值，把比它小的放左边，比它大的放右边，然后递归处理左右两边。说白了就是「找个标杆，两边站队」。

我在项目中遇到过一个问题：数据基本有序的时候，快速排序反而慢得像蜗牛。为什么会这样？因为如果每次选的基准都是最大或最小值，递归树就退化成链表了，时间复杂度直接掉到 O(n²)。

我个人习惯用「三数取中法」选基准——取左端、右端、中间三个元素的中位数。这样基本能避免最坏情况。当然，如果你实在不放心，可以随机选基准，效果也不错。

// 快速排序实现
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]);
    
    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);
    }
}

归并排序：稳定可靠的选手

归并排序的思路也简单：先把数组拆成两半，分别排好，再合并起来。你想想看，这就像整理两堆已经排好序的扑克牌，每次从两堆顶部取最小的那张。

归并排序最大的优点是稳定——相等元素的相对顺序不会变。这在某些场景下很重要，比如按时间排序后再按优先级排序，你希望相同优先级的记录仍然按时间有序。

但缺点也很明显：需要 O(n) 的额外空间。我记得有一次在内存只有 64KB 的单片机上做数据排序，归并排序直接把我干趴下了——空间不够。后来换成了堆排序才解决问题。

// 归并排序实现
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(1)——原地排序，不需要额外空间。而且时间复杂度稳定在 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 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);
    }
}

计数排序：非比较排序的利器

前面三种都是比较排序，时间复杂度下界是 O(n log n)。但计数排序不走寻常路——它不比较元素大小，而是统计每个值出现的次数。

具体做法是：先找出数组中的最大值和最小值，然后创建一个计数数组，统计每个元素出现的次数。最后根据计数数组，把元素按顺序放回原数组。

你想想看，如果数据范围很小（比如 0 到 100 之间的整数），计数排序的时间复杂度是 O(n + k)，其中 k 是数据范围。这比 O(n log n) 快多了！

// 计数排序实现
void countingSort(int arr[], int n) {
    if (n <= 1) return;
    
    // 找最大值和最小值
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    
    int range = max - min + 1;
    int count[range];
    memset(count, 0, sizeof(count));
    
    // 统计每个元素出现次数
    for (int i = 0; i < n; i++)
        count[arr[i] - min]++;
    
    // 根据计数数组重建排序后的数组
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
}

四种排序算法对比

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
快速排序	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)	稳定	整数排序，数据范围小

知识体系总览

下面这张图把四种排序算法的核心逻辑串起来了。你看一眼就能明白它们各自的特点和适用场景。

嗯，这四种排序算法各有千秋。快速排序是「万金油」，归并排序是「稳定器」，堆排序是「省内存」，计数排序是「快枪手」。实际项目中怎么选？我建议你根据数据特点来：数据量大且随机，用快排；需要稳定，用归并；内存紧张，用堆排；整数且范围小，用计数排序。

最后说一句：别死记硬背代码。理解每种排序的核心思想，知道它为什么快、为什么慢，比背代码重要一百倍。我在面试中经常遇到能把代码默写出来，但一问「为什么这里用 while 不用 for」就卡壳的候选人——这不行。