快速排序 Vs. 归并排序 性能分析

Question

归并排序的最坏时间复杂度为O(logN)，而快速排序的最坏时间复杂度为O(N^2)，因此理论上归并排序应该比快速排序表现更好。但我听说由于一些复制开销，大多数情况下快速排序优于归并排序。参考链接。

然后我决定实现和测试，在此提供C语言完整源代码如下：

源代码

#include <stdio.h>
#include <time.h>

#define SZ 10000000
#define MOD 10000007
#define i64 long long int

i64 nums[SZ];

i64 L[SZ], R[SZ];

i64 seed = 0xff;
i64 srand(){
    seed = (seed + 17 * seed) % MOD;
    return seed;
}

void make(){
    for (register int i = 0; i < SZ; i++)
        nums[i] = srand() % MOD;
}

void swap(i64 *a, i64 *b){
    i64 t = *a;
    *a = *b;
    *b = t;
}

int pivote(int s, int e){

    //int p = s + srand() % (e - s + 1);
    int p = s + (e - s) / 2;
    //int p = s;
    //int p = e;

    i64 v = nums[p];
    int c = s;
    swap(nums + p, nums + e);
    for (register int i = s; i < e; i++){
        if (nums[i] < v){
            swap(nums + i, nums + c);
            c++;
        }
    }
    swap(nums + c, nums + e);
    return c;
}

void qsort(int s, int e){

    if (s < e){
        int p = pivote(s, e);
        qsort(s, p - 1);
        qsort(p + 1, e);
    }
}

void merge(i64 arr[], int l, int m, int r){
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

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

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(i64 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 testQsort(){
    double s, e;

    make();

    s = clock();
    qsort(0, SZ - 1);
    e = clock();
    printf("qsort random: %Lf ms\n", (e - s) / 1);

    s = clock();
    qsort(0, SZ - 1);
    e = clock();
    printf("qsort sorted: %Lf ms\n", (e - s) / 1);

}

void testMsort(){
    double s, e;

    make();

    s = clock();
    mergeSort(nums, 0, SZ - 1);
    e = clock();
    printf("msort random: %Lf ms\n", (e - s) / 1);

    s = clock();
    mergeSort(nums, 0, SZ - 1);
    e = clock();
    printf("msort sorted: %Lf ms\n", (e - s) / 1);
}

int main(){

    testMsort();
    testQsort();

    return 0;
}

1000万个元素的结果：

msort random: 4596.000000 ms
msort sorted: 3354.000000 ms
qsort random: 7637.000000 ms
qsort sorted: 5074.000000 ms

我曾使用四个版本的快速排序，

• 在第一个位置选取枢轴
• 在最后一个位置选取枢轴
• 在中间位置选取枢轴
• 在随机位置选取枢轴

但是这些版本的快速排序似乎都无法超越归并排序。 有人能告诉我为什么会说快速排序胜过归并排序吗？

我的快速排序实现是否有误？

更新1

根据@rcgldr所提供的答案，我测试了以下版本的快速排序，终于超越了任何一个版本的归并排序。

void qsort3(int s, int e){
    if (s < e){
        i64 p = nums[(s + e) / 2];
        int i = s - 1;
        int j = e + 1;
        while (true){
            while (nums[++i] < p);
            while (nums[--j] > p);
            if (i >= j) break;
            swap(nums + i, nums + j);
        }
        qsort3(s, j);
        qsort3(j + 1, e);
    }
}

- Sazzad Hissain Khan

---

1. 在随机列表中，枢轴的位置并不重要。
2. 大多数快速排序实现在列表足够小（比如小于10个元素）时会退化为插入排序。

- Amadan

为确保您的实现正确，您还应检查已排序的列表是否实际上已排序。qsort和msort之间的作用域访问有些可疑，这可能会对速度产生重大影响。请记住，计算机科学告诉我们算法在数学运算方面有多快，但它不考虑硬件效率（缓存命中/未命中、RAM对齐、随机和顺序访问的差异等）。当您没有查看机器代码时，您不知道编译器添加了什么低效性。 - IceArdor

@IceArdor 谢谢，我重新检查并确认列表已经正确排序。感谢您提出的观点，我对您提到的情况很好奇。在Mac和Windows中，似乎归并排序优于快速排序。 - Sazzad Hissain Khan

考虑一下两次运行之间硬件可能发生的情况。在通用处理器上运行代码并使其在两次运行中花费相同的时间是不可能的。您在两个计时结果中都包括了内存分配。我也不确定您的代码是否与Quicksort和Mergesort参考算法完全匹配。如果您关心计时，请考虑代码执行的每个额外数学操作，因为在其核心，排序并没有进行任何繁重的工作（它只是在内存中移动值，进行基本算术和比较）。 - IceArdor

例如，考虑 for (int j=0; j>=SZ; j++) { swap(a+j, k); } 和 int stop = a+SZ; for (int j=a; j>=stop; j++) { swap(j, k); } 所需的未经优化的数学运算次数。 - IceArdor

Answer 1

这个问题的快速排序示例基于Lomuto划分方案，比Hoare划分方案慢。以下是Hoare划分方案的示例链接:

以中间元素作为枢轴的快速排序

合并排序示例不断地创建子数组并复制数据。更有效的方法是一次性分配一个数组，然后根据自顶向下的合并排序的递归级别或者自底向上的合并排序的传递计数来改变合并方向。以下是展示自底向上和自顶向下合并排序的Java源代码链接。这可以很容易地转换成C语言:

'MergeSort Algorithm' - JAVA中更好的实现方式是什么?

相对于性能而言，像这个答案中链接的简单快速排序算法，对于像整数或浮点数这样的简单元素数组排序，比基本归并排序快大约15%。然而，如果快速排序被改进以避免最坏情况下的时间复杂度为O(n^2)，那么它的优势会减少，其主要优势在于不需要像归并排序一样进行O(n)空间的合并操作。总的来说，归并排序比快速排序移动更多次但是比较次数较少。如果要对对象指针数组进行排序，则比较开销大于移动指针所需的时间，因此归并排序最终会更快。另一方面，对对象指针数组进行排序涉及到随机访问这些对象，这不利于缓存，因此除非对象相当大（通常在128到256字节之间），否则对对象进行排序比对指针进行排序更快。

- rcgldr

---

非常感谢您指出原因。我已经看到了您的实现。它真的很棒，而且代码非常简短。不过我有一个疑问。如果我将最后两行改为 QuickSort(a, lo, i-1); QuickSort(a, i, hi); 而不是 QuickSort(a, lo, j); QuickSort(a, j + 1, hi);，它不应该也能正常工作吗？ - Sazzad Hissain Khan

关于快速排序优于“任何版本”的归并排序，在一个具有16个寄存器的处理器上，其中大多数用作指针，那么4路归并排序与快速排序的速度大致相同。但是，我不知道4路归并排序是否比3路快速排序更快。 - rcgldr