实现快速排序似乎比归并排序花费更多时间

Question

我正在尝试实现快速排序（使用中位数三项划分元素和小数组插入排序），并将其与归并排序的实现进行比较，但是即使快速排序的平均时间应该比归并排序更好，每次执行时它似乎需要更多的时间来对一个数组进行排序（即使是随机顺序的数组）。有什么想法为什么会发生这种情况吗？

public class Quick {

    private static final int M = 10;
    private static Random random = new Random();

    public void sort(int[] a) {
        sort(a, 0, a.length - 1);
        insertionSort(a, 0, a.length - 1);
    }

    private void sort(int[] a, int lo, int hi) {
        if (hi - lo <= 10) return;
        swap(a, lo, pivot(a, lo, hi));
        int lt = lo, gt = hi;
        int v = a[lo];
        int i = lo;
        while (i <= gt) {
            if      (a[i] < v) swap(a, lt++, i++);
            else if (a[i] > v) swap(a, i, gt--);
            else              i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }

    private int pivot(int[] a, int lo, int hi) {
        int     r1 = random.nextInt(hi - lo) + lo,
                r2 = random.nextInt(hi - lo) + lo,
                r3 = random.nextInt(hi - lo) + lo;
        return median3(a, r1, r2, r3);
    }

    private void swap(int[] a, int i, int j) {
        if (i == j) return;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static int median3(int[] a, int i, int j, int k) {
        return (a[i] < a[j] ?
                (a[j] < a[k] ? j : a[i] < a[k] ? k : i) :
                (a[k] < a[j] ? j : a[k] < a[i] ? k : i));
    }

    private void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && a[j] < a[j-1]; j--)
                swap(a, j, j-1);
    }
}

MergeSort：

归并排序：

public class Merge {

    public void sort(int[] a) {
        int[] aux = new int[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    private void sort(int[] a, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
        // Merge
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)           a[k] = aux[j++];
            else if (j > hi)            a[k] = aux[i++];
            else if (aux[j] < aux[i])   a[k] = aux[j++];
            else                        a[k] = aux[i++];
        }
    }
}

例如，当我对长度为10^8的10个随机数组运行这些算法时，归并排序平均需要13385.8毫秒才能执行完，而快速排序则平均需要14096.7毫秒。 为了澄清，这是我测量执行时间的方法

public static void main(String[] args) {
    int pow = (int) Math.pow(10, 8);
    int[] a, b;
    double[]    m1 = new double[10],
                m2 = m1.clone(),
    double st, et;
    Merge merge = new Merge();
    Quick quick = new Quick();
    for (int i = 0; i < 10; i++) {
        a = randomArray(pow);
        b = a.clone();
        st = currentTimeMillis();
        merge.sort(a);
        et = currentTimeMillis();
        m1[i] = et - st;
        st = currentTimeMillis();
        quick.sort(b);
        et = currentTimeMillis();
        m2[i] = et - st;
    }
    out.println("MergeSort: " + mean(m1));
    out.println("QuickSort: " + mean(m2));
}
private static int[] randomArray(int n) {
    r = new Random();
    int[] a = new int[n];
    for (int i = 0; i < a.length; i++) a[i] = r.nextInt();
    return a;
}

- Roäc

---

你为什么在第一个“sort”之后调用“insertionSort”？你是如何测量性能的？ - niceman

不查看代码：渐进最差时间复杂度与实际墙钟运行时间并不相同。而且，在非病态情况下，归并排序的预期时间复杂度为O(n log n)，就像快速排序一样。 - Thomas

我没有看到 if a.length<10 insertionSort(a)，我看到的是你对数组进行了两次排序 :) - niceman

请查看以下链接，其中包含归并排序和快速排序的性能测量代码：这个 和 这个。 - pahan

如果pow = (int) Math.pow(10, 6); 我得到以下值： MergeSort: 286.9 QuickSort: 232.9如果pow = (int) Math.pow(10, 7); 我得到以下值： MergeSort: 3622.2 QuickSort: 2414.7很明显，归并排序需要更多时间？"private static double mean(double[] m1) { double total = 0; for(double val: m1) { total += val; } return total/m1.length; }" 是我的平均函数。 - Madhu V Rao

Answer 1

尝试了很多方法来找到问题所在后，我改变了创建随机数组的函数，并且发现QuickSort现在实际上运行得更快了。我不太清楚为什么，但似乎我创建数组的方式对QuickSort的性能产生了负面影响。现在，我所做的是，不再生成随机整数数组，而是生成从1到n的数组，然后打乱它，如下：

public static int[] permutation(int n) {
    int[] a = new int[n];

    for (int i = 0; i < n; ++i)  a[i] = i + 1;

    for (int i = 0; i < n; i++) {
        int r = i + rnd.nextInt(n - i),
            tmp = a[i];

        a[i] = a[r];
        a[r] = tmp;
    }

    return a;
}

- Roäc