快速排序和归并排序哪个快（详细解析）

在处理数据库中的大量记录时，排序算法的效率直接影响查询响应速度。比如你运营一个电商平台，用户按销量排序商品，后台需要快速返回结果。这时候，工程师常在快速排序和归并排序之间纠结：到底谁更快？

平均情况下的表现

从理论上看，快速排序的平均时间复杂度是 O(n log n)，归并排序也是 O(n log n)。但实际运行中，快速排序通常更胜一筹。因为它原地排序，不需要额外的存储空间，缓存命中率高，交换操作更少。

举个例子，你在写一个订单统计脚本，对十万条订单按金额排序。用快速排序可能耗时 12 毫秒，而归并排序因为要频繁分配临时数组，可能跑到 18 毫秒。虽然差距不大，但在高频调用场景下，积少成多。

最坏情况谁更扛得住

快速排序的软肋是极端情况。如果数据已经基本有序，而你又恰好选了个糟糕的基准点（pivot），它会退化到 O(n²)。就像你整理收件箱，按时间排序时数据本就有序，快排反而慢得像冒泡。

而归并排序不管数据长什么样，都能稳定在 O(n log n)。它的逻辑简单粗暴：拆到单个元素，再两两合并。这种“稳”在数据库索引构建这类关键任务中很吃香。

代码实现对比

下面是两种排序的简化实现：

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

void merge(int arr[], int l, int m, int r) {
    // 合并两个有序子数组
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0; j = 0; k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
}

可以看到，归并排序需要额外数组空间，代码逻辑也更繁琐。而快排的递归结构更简洁，适合手写调试。

数据库系统里的选择

现代数据库如 MySQL 或 PostgreSQL，并不会直接拿原始快排处理 ORDER BY。它们用的是优化版—— introsort（内省排序），开始用快排，一旦发现递归过深就切换到堆排序，兼顾速度与稳定性。

如果你在做报表导出功能，数据量小且要求稳定，归并排序更安心；如果是实时查询排序，快排或其变种通常是首选。