对快速排序和合并排序进行基准测试得出合并排序更快

Question

我已经尝试过基准测试，出于某种原因，当在 1M 元素的数组上尝试它们时，Mergesort 在 0.3 秒内对它进行了排序，而 Quicksort 花费了 1.3 秒。

我听说通常快速排序更快，因为它有内存管理，但如何解释这些结果？

我是运行 MacBook Pro 如果这有什么不同的话。输入是一组从 0 到 127 的随机生成的整数。

代码在Java:

合并排序：

static void mergesort(int arr[]) {
    int n = arr.length;
    if (n < 2)
        return;
    int mid = n / 2;
    int left[] = new int[mid];
    int right[] = new int[n - mid];
    for (int i = 0; i < mid; i++)
        left[i] = arr[i];
    for (int i = mid; i < n; i++)
        right[i - mid] = arr[i];
    mergesort(left);
    mergesort(right);
    merge(arr, left, right);
}

public static void merge(int arr[], int left[], int right[]) {
    int nL = left.length;
    int nR = right.length;
    int i = 0, j = 0, k = 0;
    while (i < nL && j < nR) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < nL) {
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < nR) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

快速排序：

public static void quickSort(int[] arr, int start, int end) {
    int partition = partition(arr, start, end);

    if (partition - 1 > start) {
        quickSort(arr, start, partition - 1);
    }
    if (partition + 1 < end) {
        quickSort(arr, partition + 1, end);
    }
}

public static int partition(int[] arr, int start, int end) {
    int pivot = arr[end];

    for (int i = start; i < end; i++) {
        if (arr[i] < pivot) {
            int temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;
            start++;
        }
    }

    int temp = arr[start];
    arr[start] = pivot;
    arr[end] = temp;

    return start;
}

Answer 1

你的实现有点简单：

mergesort 在每次递归调用时分配 2 个新数组，这是昂贵的，但一些 JVM 在优化此类编码模式方面出奇地高效。
quickSort 使用了一个糟糕的枢轴选择，即子数组的最后一个元素，这为排序的子数组提供了二次时间，包括那些具有相同元素的子数组。

数据集，一个小区间伪随机数的数组0..127，导致quickSort实现的缺点比mergesort实现的低效率差很多] 版本。增加数据集大小应该会使这一点更加明显，甚至可能由于太多的递归调用而导致 堆栈溢出。具有相同值、增加或减少集合以及此类序列的组合等常见模式的数据集将导致 quickSort 实现的灾难性性能。

这里是一个稍微修改过的版本，它对枢轴（数组 3/4 处的元素）的病态选择较少，并且有一个循环来检测枢轴值的重复项，以提高具有重复值的数据集的效率。它在我的标准排序基准测试中的表现要好得多（100 倍），数组只有 40k 个元素，但仍然比 radixsort 慢得多（8 倍）：

public static void quickSort(int[] arr, int start, int end) {
    int p1 = partition(arr, start, end);
    int p2 = p1;

    /* skip elements identical to the pivot */
    while (++p2 <= end && arr[p2] == arr[p1])
        continue;

    if (p1 - 1 > start) {
        quickSort(arr, start, p1 - 1);
    }
    if (p2 < end) {
        quickSort(arr, p2, end);
    }
}

public static int partition(int[] arr, int start, int end) {
    /* choose pivot at 3/4 or the array */
    int i = end - ((end - start + 1) >> 2);
    int pivot = arr[i];
    arr[i] = arr[end];
    arr[end] = pivot;

    for (i = start; i < end; i++) {
        if (arr[i] < pivot) {
            int temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;
            start++;
        }
    }

    int temp = arr[start];
    arr[start] = pivot;
    arr[end] = temp;

    return start;
}

对于 OP 的数据集，假设分布具有适当的随机性，扫描重复项有助于提高性能。正如预期的那样，选择不同的枢轴，无论是第一个、最后一个、中间、3/4 或 2/3 甚至中位数 3 几乎没有影响。

对其他非随机分布的进一步测试表明，由于选择了枢轴，此 quickSort 实施的性能非常糟糕。在我的基准测试中，通过选择数组的 3/4 或 2/3 处的元素作为枢轴，可以获得很大的性能改进（50k 样本提高 300 倍，比标准合并排序快 40%，时间与 radix_sort 相当） .

Mergesort 具有对所有分布稳定和可预测的明显优势，但它需要数据集大小的 50% 到 100% 之间的额外内存。
精心实施的快速排序在许多情况下速度稍快，并且就地执行，递归只需要 log(N) 个堆栈 space。然而，它并不稳定，量身定制的发行版将表现出灾难性的性能，可能会崩溃。
基数排序仅适用于特定类型的数据，例如整数和固定长度的字符串。它还需要额外的内存。
Countingsort 对于 OP 的数据集来说是最有效的，因为它只需要一个包含 128 个整数的数组来计算不同值的出现次数，已知值在 0..127 范围内。对于任何分布，它都将在线性时间内执行。

对快速排序和合并排序进行基准测试得出合并排序更快

Benchmarking quicksort and mergesort yields that mergesort is faster

java

benchmarking

mergesort

quicksort