快速排序和归并排序哪个快

在写一个电商后台的订单排序功能时，我碰上了选择排序算法的难题：到底是用快速排序还是归并排序？表面上看，它们时间复杂度都是 O(n log n)，但实际跑起来差别不小。

快排：大多数情况下的速度王者

快速排序的核心思路是“分而治之”。它选一个基准值，把数组分成两部分，左边都比它小，右边都比它大，然后递归处理。这种方式在内存中操作连续，缓存命中率高，交换次数也少。

比如处理10万条用户评分数据，快排往往比归并排序快10%到20%。尤其是在数组基本无序的情况下，它的优势特别明显。这也是为什么像 C++ 的 std::sort 和 Java 的 Arrays.sort()（对基本类型）默认都用了快排的变种。

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

归并排序：稳定发挥的靠谱选手

归并排序不管数据怎么分布，都能保持 O(n log n) 的稳定性能。它先把数组不断拆成两半，直到只剩一个元素，再逐层合并。这个过程需要额外的存储空间，但好处是排序结果绝对稳定——相同值的元素相对位置不会变。

有一次我们做学生成绩排名系统，要求相同分数的学生按录入顺序排列。这时候归并排序就派上用场了。虽然它多花了点内存，但保证了结果的可预期性，避免了客户投诉“为啥我和别人分数一样却排后面”。

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

真实场景中的取舍

如果你处理的是用户实时搜索结果排序，追求响应速度，那快排更合适。但如果是金融交易日志这类对稳定性要求极高的数据，归并排序更能让人安心。

还有个细节：快排最坏情况下会退化到 O(n²)，比如数组已经有序时，每次选的基准都是最小或最大值。为了避免这种情况，现代实现通常会随机选基准或者用三数取中法。

归并排序的短板是需要 O(n) 的额外空间。在嵌入式设备或内存紧张的场景下，这可能成为硬伤。而快排可以原地排序，节省资源。